all permutations of a binary sequence x bits long

Question

I would like to find a clean and clever way (in python) to find all permutations of strings of 1s and 0s x chars long. Ideally this would be fast and not require doing too many iterations...

So, for x = 1 I want: ['0','1'] x =2 ['00','01','10','11']

etc..

Right now I have this, which is slow and seems inelegant:

    self.nbits = n
    items = []
    for x in xrange(n+1):
        ones = x
        zeros = n-x
        item = []
        for i in xrange(ones):
            item.append(1)
        for i in xrange(zeros):
            item.append(0)
        items.append(item)
    perms = set()
    for item in items:
        for perm in itertools.permutations(item):
            perms.add(perm)
    perms = list(perms)
    perms.sort()
    self.to_bits = {}
    self.to_code = {}
    for x in enumerate(perms):
        self.to_bits[x[0]] = ''.join([str(y) for y in x[1]])
        self.to_code[''.join([str(y) for y in x[1]])] = x[0]

Note that you're not actually describing permutations. – Glenn Maynard Feb 08 '11 at 00:32 — Glenn Maynard, Feb 08 '11 at 00:32
I'm feeling a code-golf answer stream coming on. :-) – payne Feb 08 '11 at 00:33 — payne, Feb 08 '11 at 00:33

score 73 · Accepted Answer · answered Feb 08 '11 at 00:31

itertools.product is made for this:

>>> import itertools
>>> ["".join(seq) for seq in itertools.product("01", repeat=2)]
['00', '01', '10', '11']
>>> ["".join(seq) for seq in itertools.product("01", repeat=3)]
['000', '001', '010', '011', '100', '101', '110', '111']

score 9 · Answer 2 · answered Feb 08 '11 at 00:29

9

There's no need to be overly clever for something this simple:

def perms(n):
    if not n:
        return

    for i in xrange(2**n):
        s = bin(i)[2:]
        s = "0" * (n-len(s)) + s
        yield s

print list(perms(5))

answered Feb 08 '11 at 00:29

Glenn Maynard

55,829
10
121
131

score 7 · Answer 3 · answered Feb 08 '11 at 00:29

7

You can use itertools.product() for doing this.

import itertools
def binseq(k):
    return [''.join(x) for x in itertools.product('01', repeat=k)]

answered Feb 08 '11 at 00:29

Sebastian Paaske Tørholm

49,493
11
100
118

Note that you can make this even faster using `map` as the looping construct: `map(''.join, itertools.product('01', repeat=k))` – ncoghlan Feb 08 '11 at 03:55
@ncoghlan They don't do the same thing, though. – AMC Mar 31 '20 at 19:31
Given the time (early 2011), I was probably talking about Python 2, where it still would have produced a list. In Py3, indeed, the `map`-based version would produce a lazy iterator instead of a concrete list (which may or may not be what you want). – ncoghlan Apr 07 '20 at 04:26

score 6 · Answer 4 · answered Feb 08 '11 at 00:32

6

Python 2.6+:

['{0:0{width}b}'.format(v, width=x) for v in xrange(2**x)]

answered Feb 08 '11 at 00:32

Ignacio Vazquez-Abrams

776,304
153
1,341
1,358

Clever, but (at least in my machine, with modest size 2**(16...20)) ~3 slower than Josh's answer. – eat Feb 08 '11 at 01:45

score 3 · Answer 5 · answered Feb 08 '11 at 00:36

Kudos to all the clever solutions before me. Here is a low-level, get-you-hands-dirty way to do this:

def dec2bin(n):
    if not n:
        return ''
    else:
        return dec2bin(n/2) + str(n%2)

def pad(p, s):
    return "0"*(p-len(s))+s

def combos(n):
    for i in range(2**n):
        print pad(n, dec2bin(i))

That should do the trick

all permutations of a binary sequence x bits long

5 Answers5

Linked

Related