# 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)

edit retag close merge delete

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.

( 2023-08-27 19:20:56 +0200 )edit

Sort by ยป oldest newest most voted

UPDATED. Here is a solutions that first builds partition of a given list into 0-gap lists and then concatenates some pairs of them into 1-gap lists:

def all_list_partitions2(L,k):
assert len(L) % k == 0
m = len(L) // k

L = sorted(L)
M = {l:L.count(l) for l in set(L)}          # multiset: e -> multiplicity of e

intervals = []
for s in M.keys():
t = s
l = []
while t in M and len(l)<k:
l.append(t)
intervals.append( tuple(l) )
t += 1

#print('# intervals:', len(intervals) )

parts = [l for l in intervals if len(l)==k]
for l1,l2 in Combinations(intervals,2):
u,v = sorted([l1,l2])
if len(u)+len(v)==k and u[-1]+1<v[0]:
parts.append( u+v )

#print('# parts:', len(parts) )

for p in Combinations(parts,m):
if sorted(sum( p, tuple() )) == L:
yield sorted(p)


For example:

L = [1, 2, 3, 4, 5, 6, 7, 8, 9, 9, 10, 10, 11, 11, 12, 12, 13, 14]
sum(1 for _ in all_list_partitions(L,6) )


gives that there are 165 solutions for a given L.

more

@max, thank you very much for your answer! I am sorry I forgot to say that the lists in each m-tuple has the same length k.

( 2023-08-27 21:28:57 +0200 )edit

I do not understand what's the trouble then - just cut a given list into pieces of length $k$, and check that each piece satisfies the required conditions.

( 2023-08-27 22:12:33 +0200 )edit

@max, there many ways to cut a given list of length $mk$ into $m$ pieces. I would like to find a fast way to find all possible $m$-tuples of lists (each list in one m-tuple has length $k$) which satisfy the conditions.

( 2023-08-28 09:21:41 +0200 )edit

@lijr07: Your given example is confusing since it looks like the order in L does matter, while in fact it represents a multiset with an arbitrary order of elements. Anyway, I've updated the code in my answer - check it out.

( 2023-08-28 16:13:03 +0200 )edit

@max, thank you very much!

( 2023-08-28 21:57:07 +0200 )edit