Generate all permutations with sort constraint

Question

Hi!

I have a list consisting of other lists and some zeroes, for example:

x = [[1, 1, 2], [1, 1, 1, 2], [1, 1, 2], 0, 0, 0]

I would like to generate all the combinations of this list while keeping the order of the inner lists unchanged, so

[[1, 1, 2], 0, 0, [1, 1, 1, 2], [1, 1, 2], 0]

is fine, but

[[1, 1, 1, 2], [1, 1, 2], 0, 0, [1, 1, 2], 0]

isn't. I've got the feeling that this should be fairly easy in Python, but I just don't see it. Could somebody help me out?

Answer 1

In python 2.6,

import itertools

def intersperse(x, numzeroes):
    for indices in itertools.combinations(range(len(x) + numzeroes), numzeroes):
        y = x[:]
        for i in indices:
            y.insert(0, i)
        yield y

x = [[1, 1, 2], [1, 1, 1, 2], [1, 1, 2]]
list(intersperse(x, 3))

Answer 2

One hint: If there are z zeros and t lists then the number of combinations you describe is choose(z+t, z). (The stars and bars trick will help to see why that's true.)

To generate those combinations, you could generate all the length-z subsets of {1,...,z+t}. Each of those would give the positions of the zeros.

Even better, here's a generalization of your question:

http://stackoverflow.com/questions/2944987/all-the-ways-to-intersperse

Your input x can be converted into a form y suitable for the above generalization as follows:

x = [[1,1,2], [1,1,1,2], [1,1,2], 0, 0, 0]
lists = [i for i in x if i != 0]
zeros = [i for i in x if i == 0]
y = [lists, zeros]

Answer 3

I'd do something like...:

>>> import itertools
>>> x = [[1, 1, 2], [1, 1, 1, 2], [1, 1, 2], 0, 0, 0]
>>> numzeros = x.count(0)
>>> listlen = len(x)
>>> where0s = itertools.combinations(range(listlen), numzeros)
>>> nonzeros = [y for y in x if y != 0]
>>> for w in where0s:
...   result = [0] * listlen
...   picker = iter(nonzeros)
...   for i in range(listlen):
...     if i not in w:
...       result[i] = next(picker)
...   print result
... 
[0, 0, 0, [1, 1, 2], [1, 1, 1, 2], [1, 1, 2]]
[0, 0, [1, 1, 2], 0, [1, 1, 1, 2], [1, 1, 2]]
[0, 0, [1, 1, 2], [1, 1, 1, 2], 0, [1, 1, 2]]
[0, 0, [1, 1, 2], [1, 1, 1, 2], [1, 1, 2], 0]
[0, [1, 1, 2], 0, 0, [1, 1, 1, 2], [1, 1, 2]]
[0, [1, 1, 2], 0, [1, 1, 1, 2], 0, [1, 1, 2]]
[0, [1, 1, 2], 0, [1, 1, 1, 2], [1, 1, 2], 0]
[0, [1, 1, 2], [1, 1, 1, 2], 0, 0, [1, 1, 2]]
[0, [1, 1, 2], [1, 1, 1, 2], 0, [1, 1, 2], 0]
[0, [1, 1, 2], [1, 1, 1, 2], [1, 1, 2], 0, 0]
[[1, 1, 2], 0, 0, 0, [1, 1, 1, 2], [1, 1, 2]]
[[1, 1, 2], 0, 0, [1, 1, 1, 2], 0, [1, 1, 2]]
[[1, 1, 2], 0, 0, [1, 1, 1, 2], [1, 1, 2], 0]
[[1, 1, 2], 0, [1, 1, 1, 2], 0, 0, [1, 1, 2]]
[[1, 1, 2], 0, [1, 1, 1, 2], 0, [1, 1, 2], 0]
[[1, 1, 2], 0, [1, 1, 1, 2], [1, 1, 2], 0, 0]
[[1, 1, 2], [1, 1, 1, 2], 0, 0, 0, [1, 1, 2]]
[[1, 1, 2], [1, 1, 1, 2], 0, 0, [1, 1, 2], 0]
[[1, 1, 2], [1, 1, 1, 2], 0, [1, 1, 2], 0, 0]
[[1, 1, 2], [1, 1, 1, 2], [1, 1, 2], 0, 0, 0]
>>> 

Can be micro-optimized in many ways, of course, but I hope the general idea is clear: identify all the set of indices that could have zeros, and put the non-zero items of the original list in the other places in order.