3

I want to make a combination of 1's and 0's in a 2d array like the following:

[[ 1, 1, 1, 1, 0, 0, 0, 0 ],
 [ 1, 1, 1, 0, 1, 0, 0, 0 ],
 [ 1, 1, 1, 0, 0, 1, 0, 0 ],
 [ 1, 1, 1, 0, 0, 0, 1, 0 ],
 [ 1, 1, 1, 0, 0, 0, 0, 1 ],
 .
 .
 .
]

That means a combination of four 1's and four 0's. I have looked at the itertools module's permutations() and combinations(), but couldn't find any suitable functions to perform this combination.

sevko
  • 1,402
  • 1
  • 18
  • 37
user3812253
  • 33
  • 3
  • related http://stackoverflow.com/questions/6534430/why-does-pythons-itertools-permutations-contain-duplicates-when-the-original – wim Jul 07 '14 at 12:10

2 Answers2

7

You can also use combinations to generate unique combinations directly:

n = 8
n1 = 4
for x in itertools.combinations( xrange(n), n1 ) :
    print [ 1 if i in x else 0 for i in xrange(n) ] 

[1, 1, 1, 1, 0, 0, 0, 0]
[1, 1, 1, 0, 1, 0, 0, 0]
[1, 1, 1, 0, 0, 1, 0, 0]
[1, 1, 1, 0, 0, 0, 1, 0]
...
[0, 0, 0, 1, 1, 1, 0, 1]
[0, 0, 0, 1, 1, 0, 1, 1]
[0, 0, 0, 1, 0, 1, 1, 1]
[0, 0, 0, 0, 1, 1, 1, 1]

This is more efficient than permutations because you don't iterate over unwanted solutions.

The intuition is that you're trying to find all possible ways to fit four "1"s in a sequence of length 8; that's the exact definition of combinations. That number is C(8,4)=8! / (4! * 4!) = 70. In contrast, the solution using permutations iterates over 8! = 40,320 candidate solutions.

usual me
  • 8,338
  • 10
  • 52
  • 95
1

You are producing a permutation of a multiset.

The simple but naive approach is to use itertools.permutations(), with a set to filter out repeated combinations:

>>> from itertools import permutations
>>> seen = set()
>>> for combo in permutations([1] * 4 + [0] * 4):
...     if combo not in seen:
...         seen.add(combo)
...         print combo
...
(1, 1, 1, 1, 0, 0, 0, 0)
(1, 1, 1, 0, 1, 0, 0, 0)
(1, 1, 1, 0, 0, 1, 0, 0)
(1, 1, 1, 0, 0, 0, 1, 0)
(1, 1, 1, 0, 0, 0, 0, 1)
(1, 1, 0, 1, 1, 0, 0, 0)
# ...
(0, 0, 1, 0, 1, 0, 1, 1)
(0, 0, 1, 0, 0, 1, 1, 1)
(0, 0, 0, 1, 1, 1, 1, 0)
(0, 0, 0, 1, 1, 1, 0, 1)
(0, 0, 0, 1, 1, 0, 1, 1)
(0, 0, 0, 1, 0, 1, 1, 1)
(0, 0, 0, 0, 1, 1, 1, 1)

or, producing the whole sequence in one go:

set(permutations([1] * 4 + [0] * 4))

but this loses the order that permutations produced.

The set is needed as permutations() sees the 4 1 and 4 0 as individual characters and one 1 swapped with another is considered a unique permutation.

You could also use the ordering in the sequence to avoid having to use a set:

last = (1,) * 8
for combo in permutations([1] * 4 + [0] * 4):
    if combo < last:
        last = combo
        print combo

The approach is naive in that 2n! permutations are produced where we only want (2n choose n) elements. For your case that's 40320 permutations where we only need to produce 70.

Martijn Pieters
  • 1,048,767
  • 296
  • 4,058
  • 3,343