0

I've been trying to do something but can't wrap my head around :

I want to generate all possible permutations of n elements in m slots.

To be more precise, I have a 8x8 two-dimensional array, but to make it more simple, let's say it's a 64 slot list (I will transform it back to a two-dimension array later), all filled with 0. I want to place 4 1 in this list, and generate all possible permutations, with no duplicates.

For example, if I wanted to place 2 elements in a list of 4 slots, if would give those 6 lists:

0 0 1 1
0 1 0 1
1 0 0 1
0 1 1 0
1 0 1 0
1 1 0 0

I've tried using itertools, but neither of the functions there seem to do the job, or I don't really understand them enough to find the right way to use them this way.

martineau
  • 119,623
  • 25
  • 170
  • 301
Hexalyse
  • 369
  • 1
  • 4
  • 14

1 Answers1

3

IF YOU HAVE A BIG NUMBER

from sympy.utilities.iterables import multiset_permutations
# for 64 list with 4X1
l = [0]*64
for i in range(4):
    l[i] =  1

perm = multiset_permutations(l) 
# for i in perm:
#     print(i)
allPerms = list(perm)
print("Total permuations found: ", len(allPerms)) 

Total permuations found:  635376

ALTERNATE SOLUTION FOR SMALL NUMBERS

# permutations using itertools
from itertools import permutations 

# Get all permutations
perm = permutations([1, 1, 0, 0]) 
print(list(set(perm)))

Output

[(1, 0, 1, 0), (1, 1, 0, 0), (1, 0, 0, 1), (0, 1, 1, 0), (0, 1, 0, 1), (0, 0, 1, 1)]
Kuldeep Singh Sidhu
  • 3,748
  • 2
  • 12
  • 22
  • Actually, this solution is not feasible, because permutations() would first generate 64! (yes, factorial) permutations for 64 elements, before set() filters out almost everything... because the real number of elements I should get is around 635,000. – Hexalyse Apr 26 '20 at 07:37
  • I get it, please check I have updated the solution @Hexalyse – Kuldeep Singh Sidhu Apr 26 '20 at 07:45
  • Yep, I found in another answer (https://stackoverflow.com/questions/6284396/permutations-with-unique-values/6285203#6285203) that it was called permutations of multiset and that sympy supports it. Thanks for the update, I'll mark it as correct answer. – Hexalyse Apr 27 '20 at 08:11