I can't make permutations using a recursive function in Python

Question

I am trying to make a recursive function which prints all possible permutations of a given set.

perm = []  # list to make permutations
S = {1,2,3,4}  # set of elements which have not used for the permutation yet

def make_perm():
  if not S:
    print(perm)
  else:
    for x in S:
      perm.append(x)
      S.remove(x)
      make_perm()
      perm.pop()
      S.add(x)
      
make_perm()

However, this program doesn't work: it outputs [1,2,3,4] only. What is the cause?

(Add) I want the program to output as follows.

> [1,2,3,4]
> [1,2,4,3]
> [1,3,2,4]
> [1,3,4,2]
      ︙

When it is complied with PyPy3(7.3.0), it outputs [1,2,3,4] only. But when it is complied with Python3(3.8.2), it outputs as follows.

> [1,2,3,4]
> [1,2,4,3]
> [1,3,2,4]
> [1,3,2,4]
> [1,3,4,2]
      ︙

Some outputs are duplicating. I am very confused that these outputs are incorrect and different :(.

Note that any notion of set order is arbitrary - that includes iteration and insertion order. There is no guarantee that removing/adding to the set while iterating has well-defined or even stable behavior; by extension, any algorithm using this has implementation defined behavior. — MisterMiyagi, Jun 20 '21 at 11:40

score 0 · Answer 1 · answered Jun 20 '21 at 11:06

0

Whenever you do perm.append(x) you append an item from S and not a permutation so after 4 times, S is empty and you obtain [1, 2, 3, 4].

See here how to generate all the permutations of a list (very similar in case of set).

answered Jun 20 '21 at 11:06

Tom Ron

5,906
3
22
38

But the original function does work — it prints all permutations. After e.g. `[1, 2, 3, 4]` is obtained, it is printed and the numbers are added back into the set. – L3viathan Jun 20 '21 at 11:07
1

I am not quite following how this answers the question. "after 4 times, S is empty and you obtain ``[1, 2, 3, 4]``" is kind of the point – ``[1, 2, 3, 4]`` is one permutation. Then the function proceeds with the next permutation. – MisterMiyagi Jun 20 '21 at 11:09

Guy · Accepted Answer · 2021-06-20T11:56:07.127

The issue is that you are modifying S while iterating over it. You should iterate over a copy

for x in S.copy():
    perm.append(x)
    S.remove(x)
    make_perm()
    perm.pop()
    S.add(x)

Output

[1, 2, 3, 4]
[1, 2, 4, 3]
[1, 3, 2, 4]
[1, 3, 4, 2]
[1, 4, 2, 3]
[1, 4, 3, 2]
[2, 1, 3, 4]
[2, 1, 4, 3]
[2, 3, 1, 4]
[2, 3, 4, 1]
[2, 4, 1, 3]
[2, 4, 3, 1]
[3, 1, 2, 4]
[3, 1, 4, 2]
[3, 2, 1, 4]
[3, 2, 4, 1]
[3, 4, 1, 2]
[3, 4, 2, 1]
[4, 1, 2, 3]
[4, 1, 3, 2]
[4, 2, 1, 3]
[4, 2, 3, 1]
[4, 3, 1, 2]
[4, 3, 2, 1]

Note that set doesn't guarantee the order, you should use list instead

S = [1, 2, 3, 4]

for x in S[:]:
    perm.append(x)
    S.remove(x)
    make_perm()
    perm.pop()
    S.append(x)

score -1 · Answer 3 · answered Jun 20 '21 at 11:29

not answering the question, but I saw that you use code that does not follow the standards on how such a function should work. Currently, your function requires 2 fields to be set outside your function. You don't want that - functions should only rely on their arguments. Also, instead of printing all permutations, you should return them instead. This allows you to later work with the permutations.

def make_perm(iterable):
  if not iterable: return null
  else:
    permutations = []
    for elem in iterable:
      #push to permutations
    return permutations
      
s = {1, 2, 3, 4}
permutations = make_perm(s)
print(permutations)

If you don't want to reinvent the wheel and are fine with using a module, take a look into itertools.permutations

I can't make permutations using a recursive function in Python

3 Answers3