I got the following problem. Given a word (a binary one) I want to generate all the combinations with length n, and the given word can not be a prefix of any of the combinations.
For instance, with n = 3 and the word is 00 I would like to generate:
010
011
100
101
110
111
Is there any pythonic way to do this?
Edit: Sorry, I am trying modifications of this standard pseudo-code
combinations:
if depth = 0 return result
for i in start..size
out+=combinations(depth-1, i+1, result)
return out
I can't figure out how to add the restriction of not starting by the given word. By "pythonic" I mean with something like comprehension lists, or a beautiful one-liner :D
You can do all the work in a one-liner, but it takes a bit of setup. This takes advantage of the fact that you basically want all the binary numbers within a range of 0 to 2**n, except if their leftmost bits represent a particular binary number. Note that in general you will be keeping most of the numbers in the range (all but 1/2**len(word)), so it's reasonably efficient just to generate all the numbers and then filter out the ones you don't want.
word = '00'
word_int = int(word, base=2)
m = len(word)
n = 3
results = ['{0:b}'.format(num).zfill(n) for num in range(2**n) if num >> (n-m) != word_int]
print('\n'.join(results))
# 010
# 011
# 100
# 101
# 110
# 111
You can eliminate some of the setup, but the one-liner gets harder to read:
word = '00'
n = 3
[
num
for num in ('{0:b}'.format(p).zfill(n) for p in range(2**n))
if not num.startswith(word)
]
Or you can use itertools.product
word = '00'
n = 3
[
num
for num in (''.join(p) for p in itertools.product('01', repeat=n))
if not num.startswith(word)
]