Given a Python list of lists, find all possible flat lists that keeps the order of each sublist?

Question

I have a list of lists. I want to find all flat lists that keeps the order of each sublist. As an example, let's say I have a list of lists like this:

ll = [['D', 'O', 'G'], ['C', 'A', 'T'], ['F', 'I', 'S', 'H']]

It is trivial to get one solution. I managed to write the following code which can generate a random flat list that keeps the order of each sublist.

import random

# Flatten the list of lists
flat = [x for l in ll for x in l]
# Shuffle to gain randomness
random.shuffle(flat)

for l in ll:
    # Find the idxs in the flat list that belongs to the sublist
    idxs = [i for i, x in enumerate(flat) if x in l]
    # Change the order to match the order in the sublist
    for j, idx in enumerate(idxs):
        flat[idx] = l[j]

print(flat)

This can generate flat lists that looks as follows:

['F', 'D', 'O', 'C', 'A', 'G', 'I', 'S', 'T', 'H']
['C', 'D', 'F', 'O', 'G', 'I', 'S', 'A', 'T', 'H']
['C', 'D', 'O', 'G', 'F', 'I', 'S', 'A', 'T', 'H']
['F', 'C', 'D', 'I', 'S', 'A', 'H', 'O', 'T', 'G']

As you can see, 'A' always appears after 'C', 'T' always appears after 'A', 'O' always appears after 'D', and so on...

However, I want to get all possible solutions.

Please note that :

1. I want a general code that works for any given list of lists, not just for "dog cat fish";
2. It does not matter whether there are duplicants or not because every item is distinguishable.

Can anyone suggest a fast Python algorithm for this?

Answer 1

Suppose you are combining the lists by hand. Instead of shuffling and putting things back in order, you would select one list and take its first element, then again select a list and take its first (unused) element, and so on. So the algorithm you need is this: What are all the different ways to pick from a collection of lists with these particular sizes?

In your example you have lists of length 3, 3, 4; suppose you had a bucket with three red balls, three yellow balls and four green balls, which orderings are possible? Model this, and then just pick the first unused element from the corresponding list to get your output.

Say what? For your example, the (distinct) pick orders would be given by

set(itertools.permutations("RRRYYYGGGG"))

For any list of lists, we'll use integer keys instead of letters. The pick orders are:

elements = []
for key, lst in enumerate(ll):
    elements.extend( [ key ] * len(lst))
pick_orders = set(itertools.permutations(elements))

Then you just use each pick order to present the elements from your list of lists, say with pop(0) (from a copy of the lists, since pop() is destructive).

Answer 2

Yet another solution, but this one doesn't use any libraries.

def recurse(lst, indices, total, curr):
    done = True
    for l, (pos, index) in zip(lst, enumerate(indices)):
        if index < len(l): # can increment index
            curr.append(l[index]) # add on corresponding value
            indices[pos] += 1 # increment index
            recurse(lst, indices, total, curr)
            # backtrack
            indices[pos] -= 1
            curr.pop()
            done = False # modification made, so not done

    if done: # no changes made
        total.append(curr.copy())

    return

def list_to_all_flat(lst):
    seq = [0] * len(lst) # set up indexes
    total, curr = [], []
    recurse(lst, seq, total, curr)
    return total

if __name__ == "__main__":
    lst = [['D', 'O', 'G'], ['C', 'A', 'T'], ['F', 'I', 'S', 'H']]
    print(list_to_all_flat(lst))