Randomize chain from itertools

Question

I am copying an example from python docs.

def powerset(iterable):
    "powerset([1,2,3]) --> () (1,) (2,) (3,) (1,2) (1,3) (2,3) (1,2,3)"
    s = list(iterable)
    return chain.from_iterable(combinations(s, r) for r in range(len(s)+1))

How could we randomize the order of the values that we get while the result of powerset remains lazily evaluated?

EDIT: The reason I want it is that I would like to compute the sum of the derived sets and stop as soon as I find two sets that have the same sum. If I am not mistaken, the problem is NP-complete.

Answer 1

itertools.combinations() gives us results in a set order from the input. Given this, we can shuffle our input list to produce a random order of elements (obviously, there will be a lot less possible orders for the outcome).

def random_powerset(iterable):
     s = list(iterable)
     lengths = list(range(len(s)+1))
     shuffle(lengths)
     return chain.from_iterable(combinations(s, r) for r in lengths if not shuffle(s))

(This is a bit of an ugly hack - we know shuffle(s) will always return False, so we can add it as a condition to ensure it's run for each call of combinations().)

We pre-generate the list of lengths, so that we can shuffle that too.

It's not perfectly random (there will still be an order - all elements of length n will be clustered together, for example, and those elements will be in an order depending on the random order of the input), but there will be a fair amount of randomness, if that is enough for you.

Example output:

>>> list(random_powerset(range(3)))
[(), (2,), (0,), (1,), (2, 1), (2, 0), (1, 0), (1, 2, 0)]
>>> list(random_powerset(range(3)))
[(), (0, 1), (0, 2), (1, 2), (0, 1, 2), (2,), (0,), (1,)]
>>> list(random_powerset(range(3)))
[(0, 1, 2), (2,), (1,), (0,), (0, 2), (0, 1), (2, 1), ()]
>>> list(random_powerset(range(3)))
[(1, 2, 0), (0,), (2,), (1,), (), (0, 1), (0, 2), (1, 2)]
>>> list(random_powerset(range(3)))
[(), (2, 1), (2, 0), (1, 0), (0,), (2,), (1,), (2, 1, 0)]
>>> list(random_powerset(range(3)))
[(1, 0), (1, 2), (0, 2), (0, 2, 1), (), (1,), (0,), (2,)]

I think that's the best you can do without making it non-lazy.

Answer 2

Here is another idea: Store the combinations generators and yield randomly until you consume all. This randomizes the order of set sizes also.

Edit: I assume you don't care about the order of elements in a single set, since you will be summing them. If you do, you can put a random.shuffle(next_value) before yield.

import itertools
import random

def random_powerset(l):
    combs = [itertools.combinations(l,i) for i in range(len(l)+1)]
    while combs:
        comb_index = random.choice(range(len(combs)))
        try:
            next_value = next(combs[comb_index])
            yield next_value
        except StopIteration:
            combs.pop(comb_index)

Output:

In : list(random_powerset(range(3)))
Out: [(0, 1), (0, 2), (0, 1, 2), (1, 2), (), (0,), (1,), (2,)]

In : list(random_powerset(range(3)))
Out: [(0, 1, 2), (0,), (), (0, 1), (1,), (0, 2), (1, 2), (2,)]

In : list(random_powerset(range(3)))
Out: [(0, 1), (0, 1, 2), (0, 2), (), (0,), (1,), (1, 2), (2,)]

In : list(random_powerset(range(3)))
Out: [(), (0,), (0, 1), (0, 1, 2), (1,), (0, 2), (2,), (1, 2)]

In : list(random_powerset(range(3)))
Out: [(), (0, 1), (0,), (0, 1, 2), (1,), (0, 2), (2,), (1, 2)]

In : list(random_powerset(range(3)))
Out: [(0, 1), (0,), (0, 2), (1, 2), (), (1,), (2,), (0, 1, 2)]

In : list(random_powerset(range(3)))
Out: [(), (0, 1, 2), (0,), (1,), (2,), (0, 1), (0, 2), (1, 2)]