Given a 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))

Answer 3

Try:

from itertools import permutations, chain

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

x = [[(i1, i2, o) for i2, o in enumerate(subl)] for i1, subl in enumerate(ll)]
l = sum(len(subl) for subl in ll)


def is_valid(c):
    seen = {}
    for i1, i2, _ in c:
        if i2 != seen.get(i1, -1) + 1:
            return False
        else:
            seen[i1] = i2
    return True


for c in permutations(chain(*x), l):
    if is_valid(c):
        print([o for *_, o in c])

Prints:

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

...

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

Answer 4

You can use a recursive generator function:

ll = [['D', 'O', 'G'], ['C', 'A', 'T'], ['F', 'I', 'S', 'H']]
def get_combos(d, c = []):
   if not any(d) and len(c) == sum(map(len, ll)):
       yield c
   elif any(d):
      for a, b in enumerate(d):
         for j, k in enumerate(b):
            yield from get_combos(d[:a]+[b[j+1:]]+d[a+1:], c+[k])

print(list(get_combos(ll)))

Output (first ten permutations):

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

Answer 5

For simplicity, let's start with two list item in a list.

from itertools import permutations

Ls = [['D', 'O', 'G'], ['C', 'A', 'T']]
L_flattened = []
for L in Ls:
    for item in L:
        L_flattened.append(item)

print("L_flattened:", L_flattened)

print(list(permutations(L_flattened, len(L_flattened))))


[('D', 'O', 'G', 'C', 'A', 'T'), ('D', 'O', 'G', 'C', 'T', 'A'), ('D', 'O', 'G', 'A', 'C', 'T'), ('D', 'O', 'G', 'A', 'T', 'C'), ('D', 'O', 'G', 'T', 'C', 'A'), ('D', 'O', 'G', 'T', 'A', 'C'), ('D', 'O', 'C', 'G', 'A', 'T'), 
 ('D', 'O', 'C', 'G', 'T', 'A'), ('D', 'O', 'C', 'A', 'G', 'T'), ('D', 'O', 'C', 'A', 'T', 'G'),
 ...

Beware that permutations grow very quickly in their sizes. In your example there are 10 items and Permutation(10, 10) = 3628800.

I suggest you to calculate permutation here to get an idea before running actual code (which may cause memory error/freeze/crash in system).

Answer 6

You can try verifying all possible permutations:

import random
import itertools
import numpy as np

ll = [['D', 'O', 'G'], ['C', 'A', 'T'], ['F', 'I', 'S', 'H']]
flat = [x for l in ll for x in l]

all_permutations = list(itertools.permutations(flat))
good_permutations = []
count = 0
for perm in all_permutations:
  count += 1
  cond = True
  for l in ll:
    idxs = [perm.index(x) for i, x in enumerate(flat) if x in l]
    # check if ordered
    if not np.all(np.diff(np.array(idxs)) >= 0):
      cond = False
      break
  if cond == True:
    good_permutations.append(perm)
  if count >= 10000:
    break

print(len(good_permutations))

It is only a basic solution as it is really slow to compute (I set the count to limit the number of permutations that are verified).