0

How to generate all permutations of the flattened list of lists in Python, ... such that the order in the lists is maintained?

Example;

input;

[[1,2], [3]]

output;

[1,2,3]
[1,3,2]
[3,1,2]

1 is always before 2 in the permutations.

CDJB
  • 14,043
  • 5
  • 29
  • 55
owillebo
  • 625
  • 5
  • 9
  • Take a look at [itertools.permutations](https://docs.python.org/3/library/itertools.html#itertools.permutations). – accdias Dec 05 '19 at 11:42
  • Could you please explain better how the output should be generated? – Riccardo Bucco Dec 05 '19 at 11:56
  • All of you thanks very much for thinking with me. 2 solutions filter out of all possible permutations. As the number of permutations run with n! this isn't practical. For instance with the input [[1],[2,3],[4,5,6],[7,8,9,10],[11,12,13,14,15]] we already have 15!=13 biljon permutations. We know that valid permutations must start with either 1,2,4,7,11 rendering already 2/3 of the permutations invalid. The networkx solution produces an iterator very fast. I lack the knowledge to check if it is correct. – owillebo Dec 06 '19 at 07:18
  • 15!=1.3 trillion, sorry – owillebo Dec 06 '19 at 07:33
  • Counting the 37837800 permutations produced by the @RaySteam networkx based algorithm, with [[1,2], [3], [4,5,6], [7,8,9,10], [11,12,13,14,15]] as input, ran for almost 41 minutes. – owillebo Dec 06 '19 at 08:43
  • for index in range(37837800):pass runs in seconds. – owillebo Dec 06 '19 at 08:48

3 Answers3

3

IIUC, you could model this as finding all topological sorts in a DAG, so I suggest you use networkx, for example:

import itertools
import networkx as nx

data = [[1,2], [3]]
edges = [edge for ls in data for edge in zip(ls, ls[1:])]

# this creates a graph from the edges (e.g. [1, 2])
dg = nx.DiGraph(edges)

# add all the posible nodes (e.g. {1, 2, 3})
dg.add_nodes_from(set(itertools.chain.from_iterable(data)))

print(list(nx.all_topological_sorts(dg)))

Output

[[3, 1, 2], [1, 2, 3], [1, 3, 2]]

For the input provided, the following DiGraph is created:

Nodes: [1, 2, 3], Edges: [(1, 2)]

A topological sorting imposes the constraint that 1 is always going to be present before 2. More on all topological sortings can be found, here.

Dani Mesejo
  • 61,499
  • 6
  • 49
  • 76
2

Interesting problem; I'm not sure whether there is a builtin in itertools for this, but this would seem to work:

Code:

l = [[1,2], [3]]

# Create list containing indexes of sublists by the number of elements in that
# sublist - in this case [0, 0, 1]
l2 = [y for i, x in enumerate(l) for y in [i]*len(x)]

rv = []

# For every unique permutation of l2:
for x in set(itertools.permutations(l2)):
    l = [[1,2], [3]]
    perm = []
    # Create a permutation from l popping the first item of a sublist when
    # we come across that sublist's index
    for i in x:
        perm.append(l[i].pop(0))
    rv.append(tuple(perm))

Output:

>>> rv
[(3, 1, 2), (1, 3, 2), (1, 2, 3)]
CDJB
  • 14,043
  • 5
  • 29
  • 55
1

Starting from the permutations generator, filter by checking that all input sublists are sublists of the permutations. Sublist function from here.

l = [[1,2], [3]]

def sublist(lst1, lst2):
   ls1 = [element for element in lst1 if element in lst2]
   ls2 = [element for element in lst2 if element in lst1]
   return ls1 == ls2

[perm for perm in itertools.permutations(itertools.chain.from_iterable(l))
 if all(sublist(l_el, perm) for l_el in l)]

[(1, 2, 3), (1, 3, 2), (3, 1, 2)]
mcsoini
  • 6,280
  • 2
  • 15
  • 38