An efficient, pythonic way to calculate result sets

[Raymond Hettinger]

On Oct 25, 8:31 am, happyhon... at gmail.com wrote:
> I've got a little issue, both programming and performance-wise. I have
> a set, containing objects that refer to other sets. For example, in a
> simple notation: (<a, b, c>, <d, e>) (or in a more object-like
> display: set(obj1.choices=set(a, b, c) ). There may be obj1..objN
> objects in the outer set, and the amount of items in the choices sets
> could also reach a high number. The objects in the choices sets might
> overlap.
>
> Now I want to have all possible combinations, like this: (a, d), (b,
> d), (c, d), (a, e), (b, e), (c, e).
>
> However, I've got a few catches that make an already (icky) recursive
> function worse to use.
>
> First of all, I want to be able to only choose things so that the
> outer 'result sets' have the same length. For example, if you'd have
> (<a, b>, <a, c>), you might pick (a, a) with a simple algorythm, the
> basic behaviour of sets reducing it to (a) and thus having an improper
> length. I could add yet another loop after calculating everything to
> throw out any result sets with the improper length, but that would be
> highly inefficient.
>
> Second, I'd hope to be able to say that objX should be assumed to have
> made the choice z. In the first example I mentioned, if I said that
> 'obj1 == a', the only result sets that would come out would be (a, d)
> and (a, e).

def cross_nodups(*args):
    'Cross product after eliminating repeat elements, keeping constant
size'
    ans = [[]]
    for arg in args:
        ans = [x+[y] for x in ans for y in arg if y not in x]
    return ans

def choose_first(obj1, *args):
    'Assume a choice of a first object'
    return cross_nodups(obj1, *args[1:])


>>> print cross_nodups('ab', 'acd', 'fg')
[['a', 'c', 'f'], ['a', 'c', 'g'], ['a', 'd', 'f'], ['a', 'd', 'g'],
['b', 'a', 'f'], ['b', 'a', 'g'], ['b', 'c', 'f'], ['b', 'c', 'g'],
['b', 'd', 'f'], ['b', 'd', 'g']]

>>> print choose_first('a', s1,s2,s3)
[['a', 'c', 'f'], ['a', 'c', 'g'], ['a', 'd', 'f'], ['a', 'd', 'g']]



> (and hopefully not rely on
> recursion

Easy exercise of transforming recursion to iteration left to the
reader.


Raymond