Revision history [back]

I would like a fast way to solve the following problem: given a list (the order of the elements in the list does not matter but the list cannot 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. 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. Here k=6, m=3.

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 

L00=[[1, 2, 3, 4, 5, 14], [6, 8, 9, 10, 11, 12], [7, 9, 10, 11, 12, 13]]
k=len(L00[0])
L=sorted(flatten(L00))
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)

I would like a fast way to solve the following problem: given a list (the order of the elements in the list does not matter but the list cannot 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. 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. Here k=6, m=3.

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 

L00=[[1, 2, 3, 4, 5, 14], [6, 8, 9, 10, 11, 12], [7, 9, 10, 11, 12, 13]]
k=len(L00[0])
L=sorted(flatten(L00))
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)

I would like a fast way to solve the following problem: given a list (the order of the elements in the list does not matter but the list cannot 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. 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. conditions and whose union is L. Here k=6, m=3.

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 

L00=[[1, 2, 3, 4, 5, 14], [6, 8, 9, 10, 11, 12], [7, 9, 10, 11, 12, 13]]
k=len(L00[0])
L=sorted(flatten(L00))
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)

I would like a fast way to solve the following problem: given a list (the order of the elements in the list does not matter but the list cannot 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. 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.

[[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, 3, 5], [2, 4, 6]],
[[1, 3, 6], [2, 4, 5]],
[[1, 4, 5], [2, 3, 6]],
[[1, 4, 6], [2, 3, 5]],
[[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 

L00=[[1, 2, 3, 4, 5, 14], [6, 8, 9, 10, 11, 12], [7, 9, 10, 11, 12, 13]]
k=len(L00[0])
L=sorted(flatten(L00))
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)

I would like a fast way to solve the following problem: given a list (the order of the elements in the list does not matter but the list cannot 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]. 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, 3, 5], [2, 4, 6]],
[[1, 3, 6], [2, 4, 5]],
[[1, 4, 5], [2, 3, 6]],
[[1, 4, 6], [2, 3, 5]],
[[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 

L00=[[1, 2, 3, 4, 5, 14], [6, 8, 9, 10, 11, 12], [7, 9, 10, 11, 12, 13]]
k=len(L00[0])
L=sorted(flatten(L00))
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)

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]. 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, 3, 5], [2, 4, 6]],
[[1, 3, 6], [2, 4, 5]],
[[1, 4, 5], [2, 3, 6]],
[[1, 4, 6], [2, 3, 5]],
[[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 

L00=[[1, 2, 3, 4, 5, 14], [6, 8, 9, 10, 11, 12], [7, 9, 10, 11, 12, 13]]
k=len(L00[0])
L=sorted(flatten(L00))
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)

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, ((1, 2, 3), (4, 5, 6)),
((1, 2, 4), (3, 5, 6)),
((1, 2, 5), (3, 4, 6]],
[[1, 2, 6], [3, 6)),
((1, 2, 6), (3, 4, 5]],
[[1, 5)),
((1, 3, 4], [2, 5, 6]],
[[1, 4), (2, 5, 6)),
((1, 4, 5), (2, 3, 5], [2, 4, 6]],
[[1, 6)),
((1, 5, 6), (2, 3, 6], [2, 4, 5]],
[[1, 4, 5], [2, 3, 6]],
[[1, 4, 6], [2, 3, 5]],
[[1, 5, 6], [2, 3, 4]]
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 

L00=[[1, 2, 3, 4, 5, 14], [6, 8, 9, 10, 11, 12], [7, 9, 10, 11, 12, 13]]
k=len(L00[0])
L=sorted(flatten(L00))
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)

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 

L00=[[1, 2, 3, 4, 5, 14], [6, 8, 9, 10, 11, 12], [7, 9, 10, 11, 12, 13]]
k=len(L00[0])
L=sorted(flatten(L00))
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)