[Tutor] Permutations

[Kristoffer Erlandsson]

On Fri, Sep 19, 2003 at 05:26:24PM +0200, Kristoffer Erlandsson wrote:
> On Fri, Sep 19, 2003 at 08:50:59AM -0400, Carlo Bifulco wrote:
> > Hi folks,
> > 
> > I have a small computing problem that I solved in an extremely ugly and 
> > ad hoc way. I am submitting it here since I am sure that there must be 
> > much better ways to address  it  (and I am obviously not able to find 
> > them).
> > 
> > Here is what I would like to be able to do:
> > >>> permute(["a"])
> > [['a']]
> > >>> permute(["a","b"])
> > [['a'], ['a', 'b'], ['b']]
> > >>> permute(["a","b","c"])
> > [['a'], ['a', 'b'], ['a', 'c'], ['a', 'b', 'c'], ['b'], ['b', 'c'], ['c']]
> > >>> permute (["a","b","c","d"])
> > [['a'], ['a', 'b'], ['a', 'c'], ['a', 'd'], ['a', 'b', 'c'], ['a', 'b', 
> > 'd'], ['a', 'c', 'd'], ['a', 'b', 'c', 'd'], ['b'], ['b', 'c'], ['b', 
> > 'd'], ['b', 'c', 'd'], ['c'], ['c', 'd'], ['d']]
> 
> [snip]
> 
> Check this out:
> http://aspn.activestate.com/ASPN/Cookbook/Python/Recipe/190465
> 
> especially the xuniqueCombinations function, which seems to be exactly
> what you are looking for:
> 
> >>> for i in range(len(l)):
> ...     for a in xuniqueCombinations(l, i):
> ...             print a
> ... 
> []
> ['a']
> ['b']
> ['c']
> ['d']
> ['a', 'b']
> ['a', 'c']
> ['a', 'd']
> ['b', 'c']
> ['b', 'd']
> ['c', 'd']
> ['a', 'b', 'c']
> ['a', 'b', 'd']
> ['a', 'c', 'd']
> ['b', 'c', 'd']

Argh, there I get for not proof reading as I should :P. My example got
messed up, here's a working one:

>>> l = list('abcd')
>>> for i in range(len(l)+1):
...     for a in xuniqueCombinations(l, i):
...             print a
... 
[]
['a']
['b']
['c']
['d']
['a', 'b']
['a', 'c']
['a', 'd']
['b', 'c']
['b', 'd']
['c', 'd']
['a', 'b', 'c']
['a', 'b', 'd']
['a', 'c', 'd']
['b', 'c', 'd']
['a', 'b', 'c', 'd']

As you can guess, you can do other things besides only printing the elements.

-- 
Kristoffer Erlandsson                               http://errl.info