Python Forum
Recursion and permutations: print all permutations filling a list of length N
Thread Rating:
  • 0 Vote(s) - 0 Average
  • 1
  • 2
  • 3
  • 4
  • 5
Recursion and permutations: print all permutations filling a list of length N
#1
Question 
Hello everyone Big Grin ,

I have written a code and I need to add a condition.

The condition is to give the length of the list, for example, if the output list must be composed of N elements.
In other words, the input must be the length of the final list and the chain of elements that must be permuted in the final result. I leave the statement of the homework and the code that I have to which the length must be implemented.

CODE
# swap ith and jth character of string
def swap(s, i, j):
    q = list(s)
    q[i], q[j] = q[j], q[i]
    return ''.join(q)


# recursive function
def _permute(p, s, permutes):
    if p >= len(s) - 1:
        permutes.append(s)
        return

    for i in range(p, len(s)):
        _permute(p + 1, swap(s, p, i), permutes)


# helper function
def permute(s):
    permutes = []
    _permute(0, s, permutes)
    return permutes


# TEST IT
s = str(input("Write any string to get all the permutations without repetitions: "))
all_permute = permute(s)
print(all_permute)
ASSIGNMENT
Write a program, which reads an integer N and a sequence of distinct symbols (as a string). The
program then prints all ways how to fill a list of the length N by the symbols. The number of symbols
≥ N. Each symbol can occur at most once in a filled list.


Examples:
Input: 2
+x#
Output:
+ x
+ #
x +
x #
# +
# x

Input: 1
^+#/x
Output:
^
+
#
/
x
Reply
#2
Question 
Hello everyone Big Grin ,

I have written a code using recursion, which follows the following rules:

RULES
2 inputs:
  • 1st input: define the length of the output, as an integer.
  • 2nd input: write all elements that user want, as a string, that will be part of the output.

With these two inputs, the program must do the following:
  • 1st. Find all possible substrings of the length entered in the input, [] * 1st input.
  • 2nd. Form all the possible combinations with the elements entered in the 2nd input.
  • 3rd. Print all possible combinations of length [] * 1st input, with the elements of the 2nd input, without repeating.

CODE
My code is as follows and it fails to give the length of the output:

def stringPermutations(string, prefix, permutation_list):
    if len(string) == 0:
        permutation_list.append(prefix)
    else:
        for i in range(len(string)):
            rem = string[0:i] + string[i + 1:]
            stringPermutations(rem, prefix + string[i], permutation_list)
    return sorted(list(dict.fromkeys(permutation_list)))
def main():
    n = int(input("write size: "))
    b = str(input("Write String: "))
    permutation_list = [] * n
    print(stringPermutations(b, " ", permutation_list))

if __name__ == '__main__':
    main()
EXAMPLE OF HOW SHOULD WORK:
Input: 2
+x#
Output:
+ x
+ #
x +
x #
# +
# x

Could someone tell me why it doesn't work?
Thank you very much for the help!
Reply
#3
Your line 12 isn't accomplishing anything. What are you trying to do there?
single_list = []
multiplied_list = [] * 10

print(f'Single: {single_list}')
print(f'Multiplied: {multiplied_list}')
Output:
Single: [] Multiplied: []
Reply
#4
(Apr-08-2021, 08:28 PM)GOTO10 Wrote: Your line 12 isn't accomplishing anything. What are you trying to do there?
single_list = []
multiplied_list = [] * 10

print(f'Single: {single_list}')
print(f'Multiplied: {multiplied_list}')
Output:
Single: [] Multiplied: []

I am trying to give the length of the list using n variable
Reply
#5
(Apr-08-2021, 09:17 PM)SantiagoPB Wrote: I am trying to give the length of the list using n variable

I guess what I mean is, "Why did you think this would work?" Writing the recursive function requires some thought, and you accomplished that, so I'm trying to understand what the logic was behind your approach. What if you start by just assuming that the integer input will be 1 and the string will be 3 characters long, and figure out how you'd code that solution?

(Disclaimer: I haven't tried to code a solution and don't have a specific approach in mind.)
Reply
#6
(Apr-08-2021, 09:47 PM)GOTO10 Wrote:
(Apr-08-2021, 09:17 PM)SantiagoPB Wrote: I am trying to give the length of the list using n variable

I guess what I mean is, "Why did you think this would work?" Writing the recursive function requires some thought, and you accomplished that, so I'm trying to understand what the logic was behind your approach. What if you start by just assuming that the integer input will be 1 and the string will be 3 characters long, and figure out how you'd code that solution?

(Disclaimer: I haven't tried to code a solution and don't have a specific approach in mind.)

I found the solution!!! Anyway thanks for your messages. It works like I did it, was just a problem in the print( ) function.

CODE WORKING
def stringPermutations(string, prefix, permutation_list):
    if len(string) == 0:
        permutation_list.append(prefix)
    else:
        for i in range(len(string)):
            rem = string[0:i] + string[i + 1:]
            stringPermutations(rem, prefix + string[i], permutation_list)
    return sorted(list(dict.fromkeys(permutation_list)))
def main():
    n = int(input("write size: "))
    b = str(input("Write String: "))
    permutation_list = [] * n
    print(stringPermutations(n, b, " ", permutation_list))
 
if __name__ == '__main__':
    main()
As you can see I just put the variable n inside of the print
Reply
#7
(Apr-09-2021, 06:48 AM)SantiagoPB Wrote: I found the solution!!!
CODE WORKING
def stringPermutations(string, prefix, permutation_list):
    if len(string) == 0:
        permutation_list.append(prefix)
    else:
        for i in range(len(string)):
            rem = string[0:i] + string[i + 1:]
            stringPermutations(rem, prefix + string[i], permutation_list)
    return sorted(list(dict.fromkeys(permutation_list)))
def main():
    n = int(input("write size: "))
    b = str(input("Write String: "))
    permutation_list = [] * n
    print(stringPermutations(n, b, " ", permutation_list))
 
if __name__ == '__main__':
    main()
As you can see I just put the variable n inside of the print

Interesting, but your code doesn't run for me. stringPermutations expects 3 arguments but is receiving 4 in line 13, so on my system that is resulting in a TypeError.
Reply


Possibly Related Threads…
Thread Author Replies Views Last Post
  Removing all strings in a list that are of x length Bruizeh 5 740 Aug-27-2021, 03:11 AM
Last Post: naughtyCat
  sorting a list using unicodes acending order, no loops, no sort(), using recursion lrn2codee 14 1,449 Jun-23-2021, 07:33 PM
Last Post: deanhystad
  How to print all iterations of min and max for a 2D list alaina 4 843 Nov-11-2020, 05:53 AM
Last Post: alaina
  Why does this function print empty list? hhydration 1 477 Oct-28-2020, 02:03 AM
Last Post: deanhystad
  GCF function w recursion and helper function(how do i fix this Recursion Error) hhydration 3 883 Oct-05-2020, 07:47 PM
Last Post: deanhystad
  List of Objects print <__main. Problem Kol789 10 1,329 Jul-21-2020, 09:37 AM
Last Post: DeaD_EyE
  How do you find the length of an element of a list? pav1983 13 2,035 Jun-13-2020, 12:06 AM
Last Post: pav1983
  How can I print the number of unique elements in a list? AnOddGirl 5 1,444 Mar-24-2020, 05:47 AM
Last Post: AnOddGirl
  Print name N times using recursion ift38375 7 2,756 Oct-23-2019, 05:33 PM
Last Post: ichabod801
  why is this not filling my empty list? Siylo 4 1,583 Jan-21-2019, 05:27 PM
Last Post: Siylo

Forum Jump:

User Panel Messages

Announcements
Announcement #1 8/1/2020
Announcement #2 8/2/2020
Announcement #3 8/6/2020