Generate all the ways to intersperse a list of lists, keeping each list in order.
- by dreeves
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!
