Marc Stuart <[EMAIL PROTECTED]> 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
--
http://mail.python.org/mailman/listinfo/python-list
