# find all m-tuples of lists whose union is a given list

I would like a fast way to solve the following problem: given a list (the list can have numbers appearing many times). For example,

```
L=[1, 2, 3, 4, 5, 14, 6, 8, 9, 10, 11, 12, 7, 9, 10, 11, 12, 13]
```

The length of the list is $mk$ for some $m,k$ (k is fixed in the beginning). I would like to find all m-tuples of lists such that all the numbers in each list are different and each list is ordered from small to large, and there is 0 or 1 gap in each list, and the union of the m-tuple of lists is the given list, and all the lists in one m-tuple has length k. For example, [1,2,3,4] does not have gap, and [1,2,5,6] has one gap, and [1,3,6,7] has two gaps. For example,

```
t1=[[1, 2, 3, 4, 5, 14], [6, 8, 9, 10, 11, 12], [7, 9, 10, 11, 12, 13]]
```

is a 3-tuple which satisfies all the conditions and whose union is L. Here k=6, m=3.

In the case of L=[1,2,3,4,5,6] and k=3. The result should be (each line is a 2-tuple):

```
((1, 2, 3), (4, 5, 6)),
((1, 2, 4), (3, 5, 6)),
((1, 2, 5), (3, 4, 6)),
((1, 2, 6), (3, 4, 5)),
((1, 3, 4), (2, 5, 6)),
((1, 4, 5), (2, 3, 6)),
((1, 5, 6), (2, 3, 4))
```

I wrote the following to try to find all m-tuples which satisfies the condition of all numbers in each list are different. But it is not very fast. Is there some fast way to solve the problem? Thank you very much.

```
import itertools
import random
from collections import Counter
def SetDifferenceListDifference(a, b):
diff = Counter(a) - Counter(b)
return list(diff.elements())
def removeDuplicatesListOfLists(l): # very fast
l.sort()
r=list(l for l,_ in itertools.groupby(l))
return r
def number_of_gaps_in_list(L):
r=0
l=sorted(L)
for i in range(len(l)-1):
if abs(l[i+1]-l[i])>1:
r=r+1
return r
L=[1,2,3,4,5,6]
k=3
c1=[]
sn=0
m=len(L)/k
while sn<3000:
l=L
temp=len(c1)
c2=[]
while l!=[]:
t1=removeDuplicatesListOfLists(l)
#print(t1)
if len(t1)<k:
break
t2=sorted(random.sample(t1, k))
#print(t2)
c2.append(t2)
l=SetDifferenceListDifference(l,t2)
if len(c2)==m:
c1.append(sorted(c2))
c1=removeDuplicatesListOfLists(c1)
#print(len(c1))
if len(c1)==temp:
sn=sn+1
len(c1)
c2=[]
for i in c1:
sn=1
for j in i:
if number_of_gaps_in_list(j)>1:
sn=0
break
if sn==1:
c2.append(i)
len(c2)
```

Each list with 1 gap can be split into 2 lists without gaps. So it's worth starting with finding lists without gaps and then combining some nonoverlapping pairs of them into lists with 1 gap.