need a variation algorithm for Lists in Dictionaries

[Alex Martelli]

Marc Stuart <marc.stuart.risney at gmail.com> wrote:

> Hi, I am trying to create a function, where I pass a dictionary with a
> lits of strings, and try to return a
> a list of strings, for all variations, any ideas ?
> Thanks
> 
> def getAllVariants(someDict):
>       keys = someDict.keys()
>       for x in keys:
>                       print len(someDict[x])

Note that .keys() returns a somewhat random permutation of the keys
depending on their hash values (though you don't see that effect when
the keys are a few small integers;-); you may want keys =
sorted(someDict) to use the keys in sorted order, or some variant of
that.

Also, it's not clear what you mean by "return" here, while you use a
print statement and later you say "output".  I'm going to use neither
return nor print, but the flexible yield (you can make a list by calling
list(allVariants(someDict)), or print each string by looping
    for v in allVariants(someDict): print v
and so forth), technically making this "a generator".

> x = {1:['a','b'],2:['b','c'],3:['d','e','f','g']}
> getAllVariants(x)
> 
> """ I need to get a list of strings that render all possible variants,
> this is what my output should be based on the
> x dictionary:
> abd
> abe

(etc, snipped).

Such problems are most often easiest to solve recursively: for each
value in the list corresponding to the first key, yield that value
followed by all variants of the _rest_ of the dictionary's keys.  Any
recursion needs a "base case" or terminating condition: simplest though
not fastest here is to use the empty string as the only value yielded
when there are no more keys (i.e., the argument's empty).

def allVariants(someDict):
    if not someDict: yield ''
    d = dict(someDict)
    k = min(d)
    v = d.pop(k)
    for i in v:
            for rest in allVariants(d):
                yield v+rest

the copy at the second statement is needed only to avoid destroying the
original dict passed by the "real" caller; you can optimize things a
bit, if need be, by making the recursive function a private auxiliary
one (which allVariants itself calls appropriately).  I'm not going to
explore optimization possibilities (including recursion elimination,
which is often the strongest optimization you can to do a recursive
function but may well obscure its essential simplicity:-).


Alex