combinations of variable length nested lists

[Terry Reedy]

You are asking for multiple crossconcatenation: l[0] * l[1] * ...
*l[n-1]
(using * loosely here).  Grouping this as l[0] * (l[1] *
(...(l[n-2]*l[n-1])...) puts the combos in 'lexicographic' order: l[0]
varies slowest, l[n-1] varies fastest.  The recursive formulation
cc(ll) = ll[0] * cc(ll[1:]) leads directly to Just's program.

An alternative to building the output more or less in parallel is to
build each combo one at a time in a worklist:

def crosscat(lseq):
  if not lseq: return []
  n = len(lseq)
  worklist = [0]*n
  func = ''.join           # return combos as string if all seqs are,
else tuple
  for seq in lseq:
    if type(seq) != type(''):
      func = tuple; break
  result = []
  global _cc_ # delete with nested scoping
  def
_cc_(k,lseq=lseq,n=n,worklist=worklist,func=func,respend=result.append
):
    global _cc_
    if k == n:
      respend(func(worklist))
    else:
      for item  in lseq[k]:
        worklist[k] = item
        _cc_(k+1)
  _cc_(0)
  return result

This version is trivially turned into generator by replacing first
return and respend with yield and removing result and second return.
This pattern of initializing and then defining and calling an inner
function for the actual recursion is fairly common.  I also used it
for the partition problem of a few weeks ago.  Based on my experience
with that problem, I would expect an iterative version to be about 30%
faster.

Terry J. Reedy