3

probably basic, but couldn't find it in any other question. I tried: 

print ["".join(seq) for seq in itertools.permutations("00011")]

but got lots of duplications, seems like itertools doesn't understand all zeroes and all ones are the same...

what am I missing?

EDIT:

oops. Thanks to Gareth I've found out this question is a dup of: permutations with unique values. Not closing it as I think my phrasing of the question is clearer.

Community
  • 1
  • 1
ihadanny
  • 4,377
  • 7
  • 45
  • 76
  • [This answer](http://stackoverflow.com/a/6285203/68063) by ralu contains code for generating unique permutations in Python. – Gareth Rees Feb 17 '12 at 11:03
  • 1
    [This question](http://stackoverflow.com/q/6534430/566644) is relevant, and the [self-answer of the OP](http://stackoverflow.com/a/6571976/566644) contains an efficient algorithm for generating all *distinct* permutations in python. – Lauritz V. Thaulow Feb 17 '12 at 12:12

2 Answers2

2
set("".join(seq) for seq in itertools.permutations("00011"))
  • great! but when I try 2 ones and 13 zeroes (C(15,2)=105 options), it takes python forever to compute those 105 options... why is it so slow? – ihadanny Feb 17 '12 at 10:54
  • 1
    That's because this strategy goes through all 15! = 1,307,674,368,000 permutations of the input. – Gareth Rees Feb 17 '12 at 10:57
  • bah. anything more efficient? probably missing some combinatorial ability of itertools, this can't be right... – ihadanny Feb 17 '12 at 10:59
2
list(itertools.combinations(range(5), 2))

returns a list of 10 positions where the two ones can be within the five-digits (others are zero):

[(0, 1),
 (0, 2),
 (0, 3),
 (0, 4),
 (1, 2),
 (1, 3),
 (1, 4),
 (2, 3),
 (2, 4),
 (3, 4)]

For your case with 2 ones and 13 zeros, use this:

list(itertools.combinations(range(5), 2))

which returns a list of 105 positions. And it is much faster than your original solution.

Now the function:

def combiner(zeros=3, ones=2):
    for indices in itertools.combinations(range(zeros+ones), ones):
        item = ['0'] * (zeros+ones)
        for index in indices:
            item[index] = '1'
        yield ''.join(item)

print list(combiner(3, 2))

['11000',
 '01100',
 '01010',
 '01001',
 '00101',
 '00110',
 '10001',
 '10010',
 '00011',
 '10100']

and this needs 14.4µs.

list(combiner(13, 2))

returning 105 elements needs 134µs.

eumiro
  • 207,213
  • 34
  • 299
  • 261