Generate all the ways to intersperse a list of lists, keeping each list in order.

Question

Given a list of lists like this

[[1,2,3],[a,b,c,d],[x,y]]

generate all permutations of the flattened list, [1,2,3,a,b,c,d,x,y], such that the elements of each sublist occur in the same order. For example, this one is okay

[a,1,b,2,x,y,3,c,d]

but this one is not

[y,1,2,3,a,b,c,x,d]

because y must occur after x, that being how x and y are ordered in the original sublist.

I believe the number of such lists is determined by the multinomial coefficient. I.e., if there are k sublists, n_i is the length of the ith sublist, and n is the sum of the n_i's then the number of such permutations is n!/(n_1! * ... * n_k!).

The question is how to generate those sublists. Pseudocode is great. An actual implementation in your language of choice is even better!

PS: This is a generalization of this question:
http://stackoverflow.com/questions/2944590/generate-all-permutations-with-sort-constraint

Answer 1

I'd think of it as a variation on a merge sort. In a merge sort, you start with N inputs, and merge them by choosing the smallest item among those at the heads of the individual lists.

The difference is that in this case, instead of always choosing the smallest element, you choose an element from a list regardless of how it compares to the elements in the other lists (in fact, it doesn't have to be comparable at all).

One (slightly inefficient) way to do this would be to create an array of numbers, where each number signifies a list, and is repeated exactly as many times as there are elements in that list. For the example above, this would be { 1 1 1 2 2 2 2 3 3 }. Generate the unique permutations of that array, and for each generate an output by choosing head elements from the lists as signified by the numbers.

Answer 2

Haskell

First, map each element of the sublist with a the same unique symbol

lst = [['1', '2', '3'], ['a','b','c','d'], ['x','y']]
-- # ["123","abcd","xy"]

slst = zip [0..] $ map length lst
-- # [(0,3),(1,4),(2,2)] 
-- # This means [0,0,0,1,1,1,1,2,2,2]

then, evaluate all unique permutations on the list [0,0,0,1,1,1,1,2,2,2].

import Math.Combinatorics.Multiset   -- # :p
perms = permutations $ fromCounts slst
-- # [[0,0,0,1,1,1,1,2,2],[0,0,0,1,1,1,2,2,1],[0,0,0,1,1,1,2,1,2],...]

finally, replace each symbol to a sublist element, in order.

replaceSymbol :: [[a]] -> [Int] -> [a]
replaceSymbol lst [] = []
replaceSymbol lst (i:r) = let (above, (x:xs):below) = splitAt i lst in
                          x : replaceSymbol (above ++ xs:below) r

result = map (replaceSymbol lst) perms
-- # ["123abcdxy","123abcxyd","123abcxdy","123abxycd",...]

---

Edit: perms can also be generated with Math.Combinat.Permutations.permuteMultiset:

perms = permuteMultiset $ zipWith replicate (map length lst) [0..]

Answer 3

Mathematica

The idea is to first turn the input into something like this

{1,1,1,1,2,2,2,3,3}

where all the elements of each sublist are the same. We can generate the unique permutations of that and then swap back in the elements of the sublists in order.

First a helper function to do the swapping back in:

(* Given a list x like {1,1,2,2,1} and list of sublists like {{a,b,c},{x,y}}, 
   swap in the a,b,c's where the 1's are and the x,y's where the 2's are, like 
   this: {a,b,x,y,c}. 
   Note that the number of i's in x must equal the length of the ith sublist. *)
swapback[x_, sublists_] := Module[{result = x},
  MapIndexed[(result= ReplacePart[result, Thread[Position[x, First[#2]]-> #1]])&,
             sublists];
  result]

And this generates the list of permutations needed:

f[sublists_] := swapback[#, sublists]& /@ 
  Permutations@Flatten@MapIndexed[ConstantArray[First[#2], Length[#1]]&, 
                                  sublists]

Key of course is the built-in Permutations function.

Answer 4

This practically screams for a solution in Prolog :-)

solve(ListOfLists, Result):-
        findall(I, intersperse(ListOfLists, [], I), Result).

intersperse([], Accumulator, Result):-
        reverse(Accumulator, Result).

intersperse([[]|L], Accumulator, Result):-
        intersperse(L, Accumulator, Result), !.

intersperse(ListOfLists, Accumulator, Result):-
        one_head(ListOfLists, H, ListOfLists2),
        intersperse(ListOfLists2, [H|Accumulator], Result).

one_head([[H|T]|Rest], H, [T|Rest]).

one_head([H|T0], X, [H|T1]) :-
        one_head(T0, X, T1).

Answer 5

Python

Version with a generator:

def suPerm(L):
    if any(L):
        for i in xrange(len(L)):
            if L[i]:
                for p in suPerm( L[:i]+[L[i][1:]]+L[i+1:] ):
                    yield [L[i][0]] + p
    else:
        yield [] 

and now we test it:

>>> len([i for i in suPerm(['123','abcd','xy'])])
1260
>>> [''.join(i) for i in suPerm(['123','abcd','xy'])]
['123abcdxy', '123abcxdy', '123abcxyd', '123abxcdy', '123abxcyd', '123abxycd', '123axbcdy', '123axbcyd', '123axbycd', '123axybcd', '123xabcdy', '123xabcyd', '123xabycd', '123xaybcd', '123xyabcd', '12a3bcdxy', '12a3bcxdy', '12a3bcxyd', '12a3bxcdy', '12a3bxcyd', '12a3bxycd', '12a3xbcdy', '12a3xbcyd', '12a3xbycd', '12a3xybcd', '12ab3cdxy', '12ab3cxdy', '12ab3cxyd', '12ab3xcdy', '12ab3xcyd', '12ab3xycd', '12abc3dxy', '12abc3xdy', '12abc3xyd', '12abcd3xy', '12abcdx3y', '12abcdxy3', '12abcx3dy', '12abcx3yd', '12abcxd3y', '12abcxdy3', '12abcxy3d', '12abcxyd3', '12abx3cdy', '12abx3cyd', '12abx3ycd', '12abxc3dy', '12abxc3yd', '12abxcd3y', '12abxcdy3', '12abxcy3d', '12abxcyd3', '12abxy3cd', '12abxyc3d', '12abxycd3', '12ax3bcdy', '12ax3bcyd', '12ax3bycd', '12ax3ybcd', '12axb3cdy', '12axb3cyd', '12axb3ycd', '12axbc3dy', '12axbc3yd', '12axbcd3y', '12axbcdy3', '12axbcy3d', '12axbcyd3', '12axby3cd', '12axbyc3d', '12axbycd3', '12axy3bcd', '12axyb3cd', '12axybc3d', '12axybcd3', '12x3abcdy', '12x3abcyd', '12x3abycd', '12x3aybcd', '12x3yabcd', '12xa3bcdy', '12xa3bcyd', '12xa3bycd', '12xa3ybcd', '12xab3cdy', '12xab3cyd', '12xab3ycd', '12xabc3dy', '12xabc3yd', '12xabcd3y', '12xabcdy3', '12xabcy3d', '12xabcyd3', '12xaby3cd', '12xabyc3d', '12xabycd3', '12xay3bcd', '12xayb3cd', '12xaybc3d', '12xaybcd3', '12xy3abcd', '12xya3bcd', '12xyab3cd', '12xyabc3d', '12xyabcd3', '1a23bcdxy', '1a23bcxdy', '1a23bcxyd', '1a23bxcdy', '1a23bxcyd', '1a23bxycd', '1a23xbcdy', '1a23xbcyd', '1a23xbycd', '1a23xybcd', '1a2b3cdxy', '1a2b3cxdy', '1a2b3cxyd', '1a2b3xcdy', '1a2b3xcyd', '1a2b3xycd', '1a2bc3dxy', '1a2bc3xdy', '1a2bc3xyd', '1a2bcd3xy', '1a2bcdx3y', '1a2bcdxy3', '1a2bcx3dy', '1a2bcx3yd', '1a2bcxd3y', '1a2bcxdy3', '1a2bcxy3d', '1a2bcxyd3', '1a2bx3cdy', '1a2bx3cyd', '1a2bx3ycd', '1a2bxc3dy', '1a2bxc3yd', '1a2bxcd3y', '1a2bxcdy3', '1a2bxcy3d', '1a2bxcyd3', '1a2bxy3cd', '1a2bxyc3d', '1a2bxycd3', '1a2x3bcdy', '1a2x3bcyd', '1a2x3bycd', '1a2x3ybcd', '1a2xb3cdy', '1a2xb3cyd', '1a2xb3ycd', '1a2xbc3dy', '1a2xbc3yd', '1a2xbcd3y', '1a2xbcdy3', '1a2xbcy3d', '1a2xbcyd3', '1a2xby3cd', '1a2xbyc3d', '1a2xbycd3', '1a2xy3bcd', '1a2xyb3cd', '1a2xybc3d', '1a2xybcd3', '1ab23cdxy', '1ab23cxdy', '1ab23cxyd', '1ab23xcdy', '1ab23xcyd', '1ab23xycd', '1ab2c3dxy', '1ab2c3xdy', '1ab2c3xyd', '1ab2cd3xy', '1ab2cdx3y', '1ab2cdxy3', '1ab2cx3dy', '1ab2cx3yd', '1ab2cxd3y', '1ab2cxdy3', '1ab2cxy3d', '1ab2cxyd3', '1ab2x3cdy', '1ab2x3cyd', '1ab2x3ycd', '1ab2xc3dy', '1ab2xc3yd', '1ab2xcd3y', '1ab2xcdy3', '1ab2xcy3d', '1ab2xcyd3', '1ab2xy3cd', '1ab2xyc3d', '1ab2xycd3', '1abc23dxy', '1abc23xdy', '1abc23xyd', '1abc2d3xy', '1abc2dx3y', '1abc2dxy3', '1abc2x3dy', '1abc2x3yd', '1abc2xd3y', '1abc2xdy3', '1abc2xy3d', '1abc2xyd3', '1abcd23xy', '1abcd2x3y', '1abcd2xy3', '1abcdx23y', '1abcdx2y3', '1abcdxy23', '1abcx23dy', '1abcx23yd', '1abcx2d3y', '1abcx2dy3', '1abcx2y3d', '1abcx2yd3', '1abcxd23y', '1abcxd2y3', '1abcxdy23', '1abcxy23d', '1abcxy2d3', '1abcxyd23', '1abx23cdy', '1abx23cyd', '1abx23ycd', '1abx2c3dy', '1abx2c3yd', '1abx2cd3y', '1abx2cdy3', '1abx2cy3d', '1abx2cyd3', '1abx2y3cd', '1abx2yc3d', '1abx2ycd3', '1abxc23dy', '1abxc23yd', '1abxc2d3y', '1abxc2dy3', '1abxc2y3d', '1abxc2yd3', '1abxcd23y', '1abxcd2y3', '1abxcdy23', '1abxcy23d', '1abxcy2d3', '1abxcyd23', '1abxy23cd', '1abxy2c3d', '1abxy2cd3', '1abxyc23d', '1abxyc2d3', '1abxycd23', '1ax23bcdy', '1ax23bcyd', '1ax23bycd', '1ax23ybcd', '1ax2b3cdy', '1ax2b3cyd', '1ax2b3ycd', '1ax2bc3dy', '1ax2bc3yd', '1ax2bcd3y', '1ax2bcdy3', '1ax2bcy3d', '1ax2bcyd3', '1ax2by3cd', '1ax2byc3d', '1ax2bycd3', '1ax2y3bcd', '1ax2yb3cd', '1ax2ybc3d', '1ax2ybcd3', '1axb23cdy', '1axb23cyd', '1axb23ycd', '1axb2c3dy', '1axb2c3yd', '1axb2cd3y', '1axb2cdy3', '1axb2cy3d', '1axb2cyd3', '1axb2y3cd', '1axb2yc3d', '1axb2ycd3', '1axbc23dy', '1axbc23yd', '1axbc2d3y', '1axbc2dy3', '1axbc2y3d', '1axbc2yd3', '1axbcd23y', '1axbcd2y3', '1axbcdy23', '1axbcy23d', '1axbcy2d3', '1axbcyd23', '1axby23cd', '1axby2c3d', '1axby2cd3', '1axbyc23d', '1axbyc2d3', '1axbycd23', '1axy23bcd', '1axy2b3cd', '1axy2bc3d', '1axy2bcd3', '1axyb23cd', '1axyb2c3d', '1axyb2cd3', '1axybc23d', '1axybc2d3', '1axybcd23', '1x23abcdy', '1x23abcyd', '1x23abycd', '1x23aybcd', '1x23yabcd', '1x2a3bcdy', '1x2a3bcyd', '1x2a3bycd', '1x2a3ybcd', '1x2ab3cdy', '1x2ab3cyd', '1x2ab3ycd', '1x2abc3dy', '1x2abc3yd', '1x2abcd3y', '1x2abcdy3', '1x2abcy3d', '1x2abcyd3', '1x2aby3cd', '1x2abyc3d', '1x2abycd3', '1x2ay3bcd', '1x2ayb3cd', '1x2aybc3d', '1x2aybcd3', '1x2y3abcd', '1x2ya3bcd', '1x2yab3cd', '1x2yabc3d', '1x2yabcd3', '1xa23bcdy', '1xa23bcyd', '1xa23bycd', '1xa23ybcd', '1xa2b3cdy', '1xa2b3cyd', '1xa2b3ycd', '1xa2bc3dy', '1xa2bc3yd', '1xa2bcd3y', '1xa2bcdy3', '1xa2bcy3d', '1xa2bcyd3', '1xa2by3cd', '1xa2byc3d', '1xa2bycd3', '1xa2y3bcd', '1xa2yb3cd', '1xa2ybc3d', '1xa2ybcd3', '1xab23cdy', '1xab23cyd', '1xab23ycd', '1xab2c3dy', '1xab2c3yd', '1xab2cd3y', '1xab2cdy3', '1xab2cy3d', '1xab2cyd3', '1xab2y3cd', '1xab2yc3d', '1xab2ycd3', '1xabc23dy', '1xabc23yd', '1xabc2d3y', '1xabc2dy3', '1xabc2y3d', '1xabc2yd3', '1xabcd23y', '1xabcd2y3', '1xabcdy23', '1xabcy23d', '1xabcy2d3', '1xabcyd23', '1xaby23cd', '1xaby2c3d', '1xaby2cd3', '1xabyc23d', '1xabyc2d3', '1xabycd23', '1xay23bcd', '1xay2b3cd', '1xay2bc3d', '1xay2bcd3', '1xayb23cd', '1xayb2c3d', '1xayb2cd3', '1xaybc23d', '1xaybc2d3', '1xaybcd23', '1xy23abcd', '1xy2a3bcd', '1xy2ab3cd', '1xy2abc3d', '1xy2abcd3', '1xya23bcd', '1xya2b3cd', '1xya2bc3d', '1xya2bcd3', '1xyab23cd', '1xyab2c3d', '1xyab2cd3', '1xyabc23d', '1xyabc2d3', '1xyabcd23', 'a123bcdxy', 'a123bcxdy', 'a123bcxyd', 'a123bxcdy', 'a123bxcyd', 'a123bxycd', 'a123xbcdy', 'a123xbcyd', 'a123xbycd', 'a123xybcd', 'a12b3cdxy', 'a12b3cxdy', 'a12b3cxyd', 'a12b3xcdy', 'a12b3xcyd', 'a12b3xycd', 'a12bc3dxy', 'a12bc3xdy', 'a12bc3xyd', 'a12bcd3xy', 'a12bcdx3y', 'a12bcdxy3', 'a12bcx3dy', 'a12bcx3yd', 'a12bcxd3y', 'a12bcxdy3', 'a12bcxy3d', 'a12bcxyd3', 'a12bx3cdy', 'a12bx3cyd', 'a12bx3ycd', 'a12bxc3dy', 'a12bxc3yd', 'a12bxcd3y', 'a12bxcdy3', 'a12bxcy3d', 'a12bxcyd3', 'a12bxy3cd', 'a12bxyc3d', 'a12bxycd3', 'a12x3bcdy', 'a12x3bcyd', 'a12x3bycd', 'a12x3ybcd', 'a12xb3cdy', 'a12xb3cyd', 'a12xb3ycd', 'a12xbc3dy', 'a12xbc3yd', 'a12xbcd3y', 'a12xbcdy3', 'a12xbcy3d', 'a12xbcyd3', 'a12xby3cd', 'a12xbyc3d', 'a12xbycd3', 'a12xy3bcd', 'a12xyb3cd', 'a12xybc3d', 'a12xybcd3', 'a1b23cdxy', 'a1b23cxdy', 'a1b23cxyd', 'a1b23xcdy', 'a1b23xcyd', 'a1b23xycd', 'a1b2c3dxy', 'a1b2c3xdy', 'a1b2c3xyd', 'a1b2cd3xy', 'a1b2cdx3y', 'a1b2cdxy3', 'a1b2cx3dy', 'a1b2cx3yd', 'a1b2cxd3y', 'a1b2cxdy3', 'a1b2cxy3d', 'a1b2cxyd3', 'a1b2x3cdy', 'a1b2x3cyd', 'a1b2x3ycd', 'a1b2xc3dy', 'a1b2xc3yd', 'a1b2xcd3y', 'a1b2xcdy3', 'a1b2xcy3d', 'a1b2xcyd3', 'a1b2xy3cd', 'a1b2xyc3d', 'a1b2xycd3', 'a1bc23dxy', 'a1bc23xdy', 'a1bc23xyd', 'a1bc2d3xy', 'a1bc2dx3y', 'a1bc2dxy3', 'a1bc2x3dy', 'a1bc2x3yd', 'a1bc2xd3y', 'a1bc2xdy3', 'a1bc2xy3d', 'a1bc2xyd3', 'a1bcd23xy', 'a1bcd2x3y', 'a1bcd2xy3', 'a1bcdx23y', 'a1bcdx2y3', 'a1bcdxy23', 'a1bcx23dy', 'a1bcx23yd', 'a1bcx2d3y', 'a1bcx2dy3', 'a1bcx2y3d', 'a1bcx2yd3', 'a1bcxd23y', 'a1bcxd2y3', 'a1bcxdy23', 'a1bcxy23d', 'a1bcxy2d3', 'a1bcxyd23', 'a1bx23cdy', 'a1bx23cyd', 'a1bx23ycd', 'a1bx2c3dy', 'a1bx2c3yd', 'a1bx2cd3y', 'a1bx2cdy3', 'a1bx2cy3d', 'a1bx2cyd3', 'a1bx2y3cd', 'a1bx2yc3d', 'a1bx2ycd3', 'a1bxc23dy', 'a1bxc23yd', 'a1bxc2d3y', 'a1bxc2dy3', 'a1bxc2y3d', 'a1bxc2yd3', 'a1bxcd23y', 'a1bxcd2y3', 'a1bxcdy23', 'a1bxcy23d', 'a1bxcy2d3', 'a1bxcyd23', 'a1bxy23cd', 'a1bxy2c3d', 'a1bxy2cd3', 'a1bxyc23d', 'a1bxyc2d3', 'a1bxycd23', 'a1x23bcdy', 'a1x23bcyd', 'a1x23bycd', 'a1x23ybcd', 'a1x2b3cdy', 'a1x2b3cyd', 'a1x2b3ycd', 'a1x2bc3dy', 'a1x2bc3yd', 'a1x2bcd3y', 'a1x2bcdy3', 'a1x2bcy3d', 'a1x2bcyd3', 'a1x2by3cd', 'a1x2byc3d', 'a1x2bycd3', 'a1x2y3bcd', 'a1x2yb3cd', 'a1x2ybc3d', 'a1x2ybcd3', 'a1xb23cdy', 'a1xb23cyd', 'a1xb23ycd', 'a1xb2c3dy', 'a1xb2c3yd', 'a1xb2cd3y', 'a1xb2cdy3', 'a1xb2cy3d', 'a1xb2cyd3', 'a1xb2y3cd', 'a1xb2yc3d', 'a1xb2ycd3', 'a1xbc23dy', 'a1xbc23yd', 'a1xbc2d3y', 'a1xbc2dy3', 'a1xbc2y3d', 'a1xbc2yd3', 'a1xbcd23y', 'a1xbcd2y3', 'a1xbcdy23', 'a1xbcy23d', 'a1xbcy2d3', 'a1xbcyd23', 'a1xby23cd', 'a1xby2c3d', 'a1xby2cd3', 'a1xbyc23d', 'a1xbyc2d3', 'a1xbycd23', 'a1xy23bcd', 'a1xy2b3cd', 'a1xy2bc3d', 'a1xy2bcd3', 'a1xyb23cd', 'a1xyb2c3d', 'a1xyb2cd3', 'a1xybc23d', 'a1xybc2d3', 'a1xybcd23', 'ab123cdxy', 'ab123cxdy', 'ab123cxyd', 'ab123xcdy', 'ab123xcyd', 'ab123xycd', 'ab12c3dxy', 'ab12c3xdy', 'ab12c3xyd', 'ab12cd3xy', 'ab12cdx3y', 'ab12cdxy3', 'ab12cx3dy', 'ab12cx3yd', 'ab12cxd3y', 'ab12cxdy3', 'ab12cxy3d', 'ab12cxyd3', 'ab12x3cdy', 'ab12x3cyd', 'ab12x3ycd', 'ab12xc3dy', 'ab12xc3yd', 'ab12xcd3y', 'ab12xcdy3', 'ab12xcy3d', 'ab12xcyd3', 'ab12xy3cd', 'ab12xyc3d', 'ab12xycd3', 'ab1c23dxy', 'ab1c23xdy', 'ab1c23xyd', 'ab1c2d3xy', 'ab1c2dx3y', 'ab1c2dxy3', 'ab1c2x3dy', 'ab1c2x3yd', 'ab1c2xd3y', 'ab1c2xdy3', 'ab1c2xy3d', 'ab1c2xyd3', 'ab1cd23xy', 'ab1cd2x3y', 'ab1cd2xy3', 'ab1cdx23y', 'ab1cdx2y3', 'ab1cdxy23', 'ab1cx23dy', 'ab1cx23yd', 'ab1cx2d3y', 'ab1cx2dy3', 'ab1cx2y3d', 'ab1cx2yd3', 'ab1cxd23y', 'ab1cxd2y3', 'ab1cxdy23', 'ab1cxy23d', 'ab1cxy2d3', 'ab1cxyd23', 'ab1x23cdy', 'ab1x23cyd', 'ab1x23ycd', 'ab1x2c3dy', 'ab1x2c3yd', 'ab1x2cd3y', 'ab1x2cdy3', 'ab1x2cy3d', 'ab1x2cyd3', 'ab1x2y3cd', 'ab1x2yc3d', 'ab1x2ycd3', 'ab1xc23dy', 'ab1xc23yd', 'ab1xc2d3y', 'ab1xc2dy3', 'ab1xc2y3d', 'ab1xc2yd3', 'ab1xcd23y', 'ab1xcd2y3', 'ab1xcdy23', 'ab1xcy23d', 'ab1xcy2d3', 'ab1xcyd23', 'ab1xy23cd', 'ab1xy2c3d', 'ab1xy2cd3', 'ab1xyc23d', 'ab1xyc2d3', 'ab1xycd23', 'abc123dxy', 'abc123xdy', 'abc123xyd', 'abc12d3xy', 'abc12dx3y', 'abc12dxy3', 'abc12x3dy', 'abc12x3yd', 'abc12xd3y', 'abc12xdy3', 'abc12xy3d', 'abc12xyd3', 'abc1d23xy', 'abc1d2x3y', 'abc1d2xy3', 'abc1dx23y', 'abc1dx2y3', 'abc1dxy23', 'abc1x23dy', 'abc1x23yd', 'abc1x2d3y', 'abc1x2dy3', 'abc1x2y3d', 'abc1x2yd3', 'abc1xd23y', 'abc1xd2y3', 'abc1xdy23', 'abc1xy23d', 'abc1xy2d3', 'abc1xyd23', 'abcd123xy', 'abcd12x3y', 'abcd12xy3', 'abcd1x23y', 'abcd1x2y3', 'abcd1xy23', 'abcdx123y', 'abcdx12y3', 'abcdx1y23', 'abcdxy123', 'abcx123dy', 'abcx123yd', 'abcx12d3y', 'abcx12dy3', 'abcx12y3d', 'abcx12yd3', 'abcx1d23y', 'abcx1d2y3', 'abcx1dy23', 'abcx1y23d', 'abcx1y2d3', 'abcx1yd23', 'abcxd123y', 'abcxd12y3', 'abcxd1y23', 'abcxdy123', 'abcxy123d', 'abcxy12d3', 'abcxy1d23', 'abcxyd123', 'abx123cdy', 'abx123cyd', 'abx123ycd', 'abx12c3dy', 'abx12c3yd', 'abx12cd3y', 'abx12cdy3', 'abx12cy3d', 'abx12cyd3', 'abx12y3cd', 'abx12yc3d', 'abx12ycd3', 'abx1c23dy', 'abx1c23yd', 'abx1c2d3y', 'abx1c2dy3', 'abx1c2y3d', 'abx1c2yd3', 'abx1cd23y', 'abx1cd2y3', 'abx1cdy23', 'abx1cy23d', 'abx1cy2d3', 'abx1cyd23', 'abx1y23cd', 'abx1y2c3d', 'abx1y2cd3', 'abx1yc23d', 'abx1yc2d3', 'abx1ycd23', 'abxc123dy', 'abxc123yd', 'abxc12d3y', 'abxc12dy3', 'abxc12y3d', 'abxc12yd3', 'abxc1d23y', 'abxc1d2y3', 'abxc1dy23', 'abxc1y23d', 'abxc1y2d3', 'abxc1yd23', 'abxcd123y', 'abxcd12y3', 'abxcd1y23', 'abxcdy123', 'abxcy123d', 'abxcy12d3', 'abxcy1d23', 'abxcyd123', 'abxy123cd', 'abxy12c3d', 'abxy12cd3', 'abxy1c23d', 'abxy1c2d3', 'abxy1cd23', 'abxyc123d', 'abxyc12d3', 'abxyc1d23', 'abxycd123', 'ax123bcdy', 'ax123bcyd', 'ax123bycd', 'ax123ybcd', 'ax12b3cdy', 'ax12b3cyd', 'ax12b3ycd', 'ax12bc3dy', 'ax12bc3yd', 'ax12bcd3y', 'ax12bcdy3', 'ax12bcy3d', 'ax12bcyd3', 'ax12by3cd', 'ax12byc3d', 'ax12bycd3', 'ax12y3bcd', 'ax12yb3cd', 'ax12ybc3d', 'ax12ybcd3', 'ax1b23cdy', 'ax1b23cyd', 'ax1b23ycd', 'ax1b2c3dy', 'ax1b2c3yd', 'ax1b2cd3y', 'ax1b2cdy3', 'ax1b2cy3d', 'ax1b2cyd3', 'ax1b2y3cd', 'ax1b2yc3d', 'ax1b2ycd3', 'ax1bc23dy', 'ax1bc23yd', 'ax1bc2d3y', 'ax1bc2dy3', 'ax1bc2y3d', 'ax1bc2yd3', 'ax1bcd23y', 'ax1bcd2y3', 'ax1bcdy23', 'ax1bcy23d', 'ax1bcy2d3', 'ax1bcyd23', 'ax1by23cd', 'ax1by2c3d', 'ax1by2cd3', 'ax1byc23d', 'ax1byc2d3', 'ax1bycd23', 'ax1y23bcd', 'ax1y2b3cd', 'ax1y2bc3d', 'ax1y2bcd3', 'ax1yb23cd', 'ax1yb2c3d', 'ax1yb2cd3', 'ax1ybc23d', 'ax1ybc2d3', 'ax1ybcd23', 'axb123cdy', 'axb123cyd', 'axb123ycd', 'axb12c3dy', 'axb12c3yd', 'axb12cd3y', 'axb12cdy3', 'axb12cy3d', 'axb12cyd3', 'axb12y3cd', 'axb12yc3d', 'axb12ycd3', 'axb1c23dy', 'axb1c23yd', 'axb1c2d3y', 'axb1c2dy3', 'axb1c2y3d', 'axb1c2yd3', 'axb1cd23y', 'axb1cd2y3', 'axb1cdy23', 'axb1cy23d', 'axb1cy2d3', 'axb1cyd23', 'axb1y23cd', 'axb1y2c3d', 'axb1y2cd3', 'axb1yc23d', 'axb1yc2d3', 'axb1ycd23', 'axbc123dy', 'axbc123yd', 'axbc12d3y', 'axbc12dy3', 'axbc12y3d', 'axbc12yd3', 'axbc1d23y', 'axbc1d2y3', 'axbc1dy23', 'axbc1y23d', 'axbc1y2d3', 'axbc1yd23', 'axbcd123y', 'axbcd12y3', 'axbcd1y23', 'axbcdy123', 'axbcy123d', 'axbcy12d3', 'axbcy1d23', 'axbcyd123', 'axby123cd', 'axby12c3d', 'axby12cd3', 'axby1c23d', 'axby1c2d3', 'axby1cd23', 'axbyc123d', 'axbyc12d3', 'axbyc1d23', 'axbycd123', 'axy123bcd', 'axy12b3cd', 'axy12bc3d', 'axy12bcd3', 'axy1b23cd', 'axy1b2c3d', 'axy1b2cd3', 'axy1bc23d', 'axy1bc2d3', 'axy1bcd23', 'axyb123cd', 'axyb12c3d', 'axyb12cd3', 'axyb1c23d', 'axyb1c2d3', 'axyb1cd23', 'axybc123d', 'axybc12d3', 'axybc1d23', 'axybcd123', 'x123abcdy', 'x123abcyd', 'x123abycd', 'x123aybcd', 'x123yabcd', 'x12a3bcdy', 'x12a3bcyd', 'x12a3bycd', 'x12a3ybcd', 'x12ab3cdy', 'x12ab3cyd', 'x12ab3ycd', 'x12abc3dy', 'x12abc3yd', 'x12abcd3y', 'x12abcdy3', 'x12abcy3d', 'x12abcyd3', 'x12aby3cd', 'x12abyc3d', 'x12abycd3', 'x12ay3bcd', 'x12ayb3cd', 'x12aybc3d', 'x12aybcd3', 'x12y3abcd', 'x12ya3bcd', 'x12yab3cd', 'x12yabc3d', 'x12yabcd3', 'x1a23bcdy', 'x1a23bcyd', 'x1a23bycd', 'x1a23ybcd', 'x1a2b3cdy', 'x1a2b3cyd', 'x1a2b3ycd', 'x1a2bc3dy', 'x1a2bc3yd', 'x1a2bcd3y', 'x1a2bcdy3', 'x1a2bcy3d', 'x1a2bcyd3', 'x1a2by3cd', 'x1a2byc3d', 'x1a2bycd3', 'x1a2y3bcd', 'x1a2yb3cd', 'x1a2ybc3d', 'x1a2ybcd3', 'x1ab23cdy', 'x1ab23cyd', 'x1ab23ycd', 'x1ab2c3dy', 'x1ab2c3yd', 'x1ab2cd3y', 'x1ab2cdy3', 'x1ab2cy3d', 'x1ab2cyd3', 'x1ab2y3cd', 'x1ab2yc3d', 'x1ab2ycd3', 'x1abc23dy', 'x1abc23yd', 'x1abc2d3y', 'x1abc2dy3', 'x1abc2y3d', 'x1abc2yd3', 'x1abcd23y', 'x1abcd2y3', 'x1abcdy23', 'x1abcy23d', 'x1abcy2d3', 'x1abcyd23', 'x1aby23cd', 'x1aby2c3d', 'x1aby2cd3', 'x1abyc23d', 'x1abyc2d3', 'x1abycd23', 'x1ay23bcd', 'x1ay2b3cd', 'x1ay2bc3d', 'x1ay2bcd3', 'x1ayb23cd', 'x1ayb2c3d', 'x1ayb2cd3', 'x1aybc23d', 'x1aybc2d3', 'x1aybcd23', 'x1y23abcd', 'x1y2a3bcd', 'x1y2ab3cd', 'x1y2abc3d', 'x1y2abcd3', 'x1ya23bcd', 'x1ya2b3cd', 'x1ya2bc3d', 'x1ya2bcd3', 'x1yab23cd', 'x1yab2c3d', 'x1yab2cd3', 'x1yabc23d', 'x1yabc2d3', 'x1yabcd23', 'xa123bcdy', 'xa123bcyd', 'xa123bycd', 'xa123ybcd', 'xa12b3cdy', 'xa12b3cyd', 'xa12b3ycd', 'xa12bc3dy', 'xa12bc3yd', 'xa12bcd3y', 'xa12bcdy3', 'xa12bcy3d', 'xa12bcyd3', 'xa12by3cd', 'xa12byc3d', 'xa12bycd3', 'xa12y3bcd', 'xa12yb3cd', 'xa12ybc3d', 'xa12ybcd3', 'xa1b23cdy', 'xa1b23cyd', 'xa1b23ycd', 'xa1b2c3dy', 'xa1b2c3yd', 'xa1b2cd3y', 'xa1b2cdy3', 'xa1b2cy3d', 'xa1b2cyd3', 'xa1b2y3cd', 'xa1b2yc3d', 'xa1b2ycd3', 'xa1bc23dy', 'xa1bc23yd', 'xa1bc2d3y', 'xa1bc2dy3', 'xa1bc2y3d', 'xa1bc2yd3', 'xa1bcd23y', 'xa1bcd2y3', 'xa1bcdy23', 'xa1bcy23d', 'xa1bcy2d3', 'xa1bcyd23', 'xa1by23cd', 'xa1by2c3d', 'xa1by2cd3', 'xa1byc23d', 'xa1byc2d3', 'xa1bycd23', 'xa1y23bcd', 'xa1y2b3cd', 'xa1y2bc3d', 'xa1y2bcd3', 'xa1yb23cd', 'xa1yb2c3d', 'xa1yb2cd3', 'xa1ybc23d', 'xa1ybc2d3', 'xa1ybcd23', 'xab123cdy', 'xab123cyd', 'xab123ycd', 'xab12c3dy', 'xab12c3yd', 'xab12cd3y', 'xab12cdy3', 'xab12cy3d', 'xab12cyd3', 'xab12y3cd', 'xab12yc3d', 'xab12ycd3', 'xab1c23dy', 'xab1c23yd', 'xab1c2d3y', 'xab1c2dy3', 'xab1c2y3d', 'xab1c2yd3', 'xab1cd23y', 'xab1cd2y3', 'xab1cdy23', 'xab1cy23d', 'xab1cy2d3', 'xab1cyd23', 'xab1y23cd', 'xab1y2c3d', 'xab1y2cd3', 'xab1yc23d', 'xab1yc2d3', 'xab1ycd23', 'xabc123dy', 'xabc123yd', 'xabc12d3y', 'xabc12dy3', 'xabc12y3d', 'xabc12yd3', 'xabc1d23y', 'xabc1d2y3', 'xabc1dy23', 'xabc1y23d', 'xabc1y2d3', 'xabc1yd23', 'xabcd123y', 'xabcd12y3', 'xabcd1y23', 'xabcdy123', 'xabcy123d', 'xabcy12d3', 'xabcy1d23', 'xabcyd123', 'xaby123cd', 'xaby12c3d', 'xaby12cd3', 'xaby1c23d', 'xaby1c2d3', 'xaby1cd23', 'xabyc123d', 'xabyc12d3', 'xabyc1d23', 'xabycd123', 'xay123bcd', 'xay12b3cd', 'xay12bc3d', 'xay12bcd3', 'xay1b23cd', 'xay1b2c3d', 'xay1b2cd3', 'xay1bc23d', 'xay1bc2d3', 'xay1bcd23', 'xayb123cd', 'xayb12c3d', 'xayb12cd3', 'xayb1c23d', 'xayb1c2d3', 'xayb1cd23', 'xaybc123d', 'xaybc12d3', 'xaybc1d23', 'xaybcd123', 'xy123abcd', 'xy12a3bcd', 'xy12ab3cd', 'xy12abc3d', 'xy12abcd3', 'xy1a23bcd', 'xy1a2b3cd', 'xy1a2bc3d', 'xy1a2bcd3', 'xy1ab23cd', 'xy1ab2c3d', 'xy1ab2cd3', 'xy1abc23d', 'xy1abc2d3', 'xy1abcd23', 'xya123bcd', 'xya12b3cd', 'xya12bc3d', 'xya12bcd3', 'xya1b23cd', 'xya1b2c3d', 'xya1b2cd3', 'xya1bc23d', 'xya1bc2d3', 'xya1bcd23', 'xyab123cd', 'xyab12c3d', 'xyab12cd3', 'xyab1c23d', 'xyab1c2d3', 'xyab1cd23', 'xyabc123d', 'xyabc12d3', 'xyabc1d23', 'xyabcd123']

---

With list comprehensions this can be reduced literally to a one-liner (formated below for legibility):

def suPerm(L):
    return [ [L[i][0]] + p
                for i in xrange(len(L)) if L[i]
                    for p in suPerm( L[:i]+[L[i][1:]]+L[i+1:] )
           ] if any(L) else [[]]

and example of usage:

>>> suPerm([[1,2],[30,40]])
[[1, 2, 30, 40], [1, 30, 2, 40], [1, 30, 40, 2], [30, 1, 2, 40], [30, 1, 40, 2], [30, 40, 1, 2]]