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_i! * ... * n_k!).

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