Find every possible disposition of elements in a list keeping elements and list length

Question

I would like to find every combination of elements in a list, by switching the order of the elements, while keeping their count and the length of the list.

For example, for the list:

[1,2,1,3]

I would like to obtain the following:

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

Be aware that same elements, such as the two 1 in the original list, are not seen as separate ones, so the two possibilities [1a,1b,2,3] and [1b,1a,2,3] must be counted as one

isn't that exactly what `itertools.permutations` do ? but permutations return 24 elements, you have only 12 elements there. — Jean-François Fabre, Dec 15 '18 at 15:53
@Jean-FrançoisFabre I think `set(itertools.permutations)` will do it. — RuthC, Dec 15 '18 at 15:57
`permutations` AFAIK does not treat repeated elements in list as requested in the last sentence. One working solution would be `set(permutations([...]))`, but something more performant may exist — rrobby86, Dec 15 '18 at 15:58

Jean-François Fabre · Accepted Answer · 2018-12-15T16:00:12.507

you want permutations with duplicates removed (since there are 2 identical elements), using a set and converting to list each element (or leave as tuples)

import itertools

s = [1,2,1,3]
for x in set(itertools.permutations(s)):
    print(list(x))

result:

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

this yields 12 elements, against 24 when using permutations but since there are 2 identical elements, the number is divided by 2.

as comprehension:

result = [list(x) in set(itertools.permutations(s))]

note that in general, using set to drop duplicates from combinations or permutations isn't the most performant solution. Here it's easy and not so lossy since the result/computation ratio isn't exponential (I had tried this technique here and that was too wasteful: List all combinations of combinations, computing 720 permutations to get a list of 15 groups).

it's already a duplicate (I should have known) and easy but yes one-liners aren't always the most efficient, when complexity matters — Jean-François Fabre, Dec 15 '18 at 16:54

Find every possible disposition of elements in a list keeping elements and list length

1 Answers1