Generate all permutations from 1 to n in python with recursion

Question

Given a natural number n. We try to generate all permutations from 1 to n in Python without any prebuild method. I used recursion as follows to achieve our desired goal in python

# Generate all permutations in Python with recursion


n = int(input('Enter a number: '))

permutationLst = []
validlst = [0] * (n + 1)


def generate():
    if len(permutationLst) >= n:
        print(permutationLst)
        return None

    for i in range(1, n + 1):
        if validlst[i]:
            continue

        validlst[i] = 1
        permutationLst.insert(i, i)
        generate()
        permutationLst.pop()
        validlst[i] = 0


generate()

But the output of above code is for n=3 is:

Enter a number: 3
[1, 2, 3]

[1, 3, 2]

[2, 1, 3]

[2, 1, 3]

[3, 1, 2]

[3, 1, 2]

How can I resolve this problem that some permutations are not generated and duplicates are generated? Note that I'm a beginner in Python.

I try to analyze the recursion tree of my code but I can't figure out the problem.

Did you googled that question ? https://stackoverflow.com/q/104420 // https://stackoverflow.com/q/8306654 — azro, Jul 29 '23 at 07:58

score 4 · Accepted Answer · answered Jul 29 '23 at 08:04

The issue with your current implementation is that you are not properly handling the state of the validlst list and the permutationLst list when you backtrack after generating a permutation.

To fix this issue, you need to modify your code as follows:

n = int(input('Enter a number: '))
permutationLst = []
validlst = [0] * (n + 1)


def generate():
    if len(permutationLst) == n:
        print(permutationLst)
        return None

    for i in range(1, n + 1):
        if validlst[i]:
            continue

        validlst[i] = 1
        permutationLst.append(i)
        generate()
        permutationLst.pop()
        validlst[i] = 0


generate()

The changes are:

In the if condition, you should check for the length of permutationLst to be equal to n, not greater than or equal to n.
Use the append() method instead of insert() to add an element to permutationLst.
In the backtracking step, you should remove the last element from permutationLst using the pop() method.
You should reset the value of validlst[i] to 0 after backtracking.

With these modifications, your code should generate all permutations of 1 to n without duplicates.

Generate all permutations from 1 to n in python with recursion

1 Answers1