Ask Your Question
0

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

asked 2023-08-27 18:36:11 +0200

lijr07 gravatar image

updated 2023-08-28 09:54:03 +0200

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 flag offensive close merge delete

Comments

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.

Max Alekseyev gravatar imageMax Alekseyev ( 2023-08-27 19:20:56 +0200 )edit

1 Answer

Sort by ยป oldest newest most voted
1

answered 2023-08-27 20:56:12 +0200

Max Alekseyev gravatar image

updated 2023-08-28 17:20:32 +0200

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.

edit flag offensive delete link more

Comments

@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.

lijr07 gravatar imagelijr07 ( 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.

Max Alekseyev gravatar imageMax Alekseyev ( 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.

lijr07 gravatar imagelijr07 ( 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.

Max Alekseyev gravatar imageMax Alekseyev ( 2023-08-28 16:13:03 +0200 )edit

@max, thank you very much!

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

Your Answer

Please start posting anonymously - your entry will be published after you log in or create a new account.

Add Answer

Question Tools

1 follower

Stats

Asked: 2023-08-27 18:36:11 +0200

Seen: 217 times

Last updated: Aug 28 '23