combinations of variable length nested lists

[David C. Ullrich]

On 07 Aug 2001 18:17:33 +0100 (BST), andrew-usenet at lexical.org.uk
(Andrew Walkingshaw) wrote:

>In article <3b6ff692.1462602 at nntp.sprynet.com>, David C. Ullrich wrote:
>>Well there's an obvious "just do it" recursive version. 
>
>Which is much nicer than the following non-recursive one, which makes
>hideously many assumptions about the nature of everything
>(specifically, any more than one depth of nesting in the input and it
>utterly breaks):
>
>from __future__ import nested_scopes
>
>input = [[1,2,3],[4,5],[6,7,8,9],[10],[11,12]]
>
>def permute(list):
>    totlists = 1
>    for x in xrange(len(list)): totlists *= len(list[x])
>    result = [ [] for x in xrange(0, totlists) ]
>    for x in xrange(0, len(list)):
>        for y in xrange(0, len(list[x])):
>            for z in filter(lambda a: divmod(a+y, len(list[x]))[1]==0, 
>                            xrange(0, totlists)):
>                result[z].append(list[x][y])
>        result.sort()
>    return result
>
>if __name__ == "__main__":
>    for line in permute(input):
>        print repr(line)
>
>
>I apologise for how vile this is. :)
>
>This does actually work, but I'd be amazed if the sort didn't do nasty
>things to performance; however, if recursion really bothers you, it's
>yet another answer.

It's been determined in many examples that if recursion really bothers
you when you're writing Python it shouldn't. Or at least it's wrong
to jump to the conclusion that there's anything wrong with it, it
has often come out to be the best solution or close to it.

(There's not all that much recursion in the "obvious" 
recursive approach, if we apply it to a list containing
n lists there will be only n calls. As opposed to the 
first way I wrote it: there's a big difference between

for x in alist[0]:
  for t in CartesianProduct(alist[1:]):

and

tails = CartesianProduct(alist[1:]);
for x in alost[0]:
  for t in tails:

The first version entails hideously many
recursive calls.)

>#!/usr/bin/env python
>#97.110.100.114.101.119.64.108.101.120.105.99.97.108.46.111.114.103.46.117.107
>import sys; print("".join([chr(int(r)) for r in open(sys.argv[0],"r").
>readlines()[1][1:].split('.')])) #needs python 2; adw27 at cam.ac.uk(academic) 


David C. Ullrich