So I wrote this code that attempts to return all the permutations of a number in range (1, lst).

def permutation(lst):
    if isinstance(lst, int):
        lst = list(range(1, lst   1))
    if len(lst) == 0:
        return []
    if len(lst) == 1:
        return ({(1,)})
    if len(lst) == 2:
        return ({(1,2),(2,1)})
    l = []
    for i in range(len(lst)):
        m = lst[i]
        remLst = lst[:i]   lst[i   1:]
        for p in permutation(remLst):
            l.append(tuple([m]   list(p)))
    return set(l)

However, the output that I got seems to be incorrect.. because when I put in

permutation(3)

I get...

{(1, 2, 1), (1, 1, 2), (3, 2, 1), (2, 1, 2), (2, 2, 1), (3, 1, 2)}

but I'm supposed to get

{(1,2,3), (1,3,2), (2,1,3), (2,3,1), (3,1,2), (3,2,1)}

and when my input is permutation(4) my output is

{(4, 1, 2, 1), (1, 4, 1, 2), (4, 1, 1, 2), (3, 1, 2, 1), (4, 3, 2, 1), (3, 2, 2, 1), (4, 3, 1, 2), (3, 4, 2, 1), (3, 2, 1, 2), (4, 2, 2, 1), (3, 1, 1, 2), (3, 4, 1, 2), (2, 3, 2, 1), (4, 2, 1, 2), (2, 4, 1, 2), (2, 4, 2, 1), (2, 3, 1, 2), (1, 2, 1, 2), (1, 2, 2, 1), (1, 3, 2, 1), (2, 1, 1, 2), (2, 1, 2, 1), (1, 4, 2, 1), (1, 3, 1, 2)}

but I'm supposed to get this...

{(4, 3, 1, 2), (3,4, 1, 2), (3, 1, 4, 2), (3, 1, 2,4), (4, 1, 3, 2), (1, 4, 3, 2), (1, 3, 4, 2), (1, 3, 2, 4), (4, 1, 2, 3), (1, 4, 2, 3), (1, 2, 4, 3), (1, 2, 3, 4), (4, 3, 2, 1), (3, 4, 2, 1), (3, 2, 4, 1), (3, 2, 1, 4), (4, 2, 3, 1), (2, 4, 3, 1), (2, 3, 4, 1), (2, 3, 1, 4), (4, 2, 1, 3), (2, 4, 1, 3), (2, 1, 4, 3), (2, 1, 3, 4)}

What changes should I make so that my code returns the correct output??

CodePudding user response：

You can use itertools.permutations: it does exactly what you want to do.

from itertools import permutations

lst = 3
p = permutations(range(lst))
print(p)

See the docs here

CodePudding user response：

I don't think you can do this

if len(lst) == 1:
    return ({(1,)})
if len(lst) == 2:
    return ({(1,2),(2,1)})

If the length of the list is 1, it doesn't necessarily mean that all its permutations will be 1. I think this messes up your recursion, try this instead:

if len(lst) == 1:
    return ({(lst[0],)})
if len(lst) == 2:
    return ({(lst[0],lst[1]),(lst[1],lst[0])})

Full code becomes:

def permutation(lst):
    if isinstance(lst, int):
        lst = list(range(1, lst   1))
    if len(lst) == 0:
        return []
    if len(lst) == 1:
        return ({(lst[0],)})
    if len(lst) == 2:
        return ({(lst[0],lst[1]),(lst[1],lst[0])})
    l = []
    for i in range(len(lst)):
        m = lst[i]
        remLst = lst[:i]   lst[i   1:]
        for p in permutation(remLst):
            l.append(tuple([m]   list(p)))
    return set(l)

CodePudding user response：

Here is an alternative implementation of the permutations function:

def permutations(lst):
    if len(lst) <= 1:
        return [lst]

    results = []

    for idx, item in enumerate(lst):
        sub_perms = permutations(lst[:idx]   lst[idx 1:])
        results.extend([item]   sub_perm for sub_perm in sub_perms)

    return results

Output for permutations([1,2,3]):

>>> permutations([1,2,3])
[[1, 2, 3], [1, 3, 2], [2, 1, 3], [2, 3, 1], [3, 1, 2], [3, 2, 1]]

CodePudding user response：

You can use simple list comprehension, which might be a bit more pythonic.

def permutation(M):
    def permutation_set(S):
        if not S:
            return [[]]
        else:
            return [[x]   p for x in S for p in permutation_set(S - {x})] 
    return permutation_set(set(range(1, M 1)))

permutation(3)
# ==> [[1, 2, 3], [1, 3, 2], [2, 1, 3], [2, 3, 1], [3, 1, 2], [3, 2, 1]]

The interpretation of this code is:

• Given a number M, compose a set S = {1, 2, ..., M} -- set(range(1, M 1))
• For each item x in set S, recursively generate permutations of a subset S - {x}
• Adjoin x to the front of each one of the permutations of the subset -- [x] p for p in permutation_set(S - {x})

This yields for each x in S, the sequence of permutations of S that begin with x.

Traversing through all x gives all permutations of S -- [x] p for x in S