Revision history [back]

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_partitions(L,k):
    assert len(L) % k == 0
    m = len(L) // k

    # construct digraph on intervals in L, where consecutive intervals are connected with an edge
    D = DiGraph()

    # add vertices
    v_start = (-oo,0)
    v_end = (len(L),oo)
    D.add_vertices([v_start,v_end])
    for i in range(len(L)):
        u = i+1
        D.add_vertex((i,u))
        while u<len(L) and L[u]==L[u-1]+1:
            u += 1
            D.add_vertex((i,u))

    for u,v in Tuples(D.vertices(sort=False),2):
        if u[1]==v[0]:
            D.add_edge(u,v, int(u==v_start or v==v_end or L[v[0]]<=L[u[1]-1]+1) )    # weight is 1 if u,v cannot be concatented into a 1-gap list

    from sage.graphs.path_enumeration import shortest_simple_paths
    for w,P in shortest_simple_paths(D, v_start, v_end, by_weight=True, report_weight=True):
        if w>m+1:
            break       # weight is too large, cannot get m-tuple by concatenation
        c = len(P) - 2 - m      # number of concatenations to perform
        if c<0:
            continue

        G = Graph()
        for i in range(1,len(P)-1):
            if D.edge_label(P[i],P[i+1])==0:    # can concatenate
                G.add_edge(i-1,i)

        # find matchings in G of size c, and concatenate lists according to them
        from sage.graphs.independent_sets import IndependentSets
        for M in IndependentSets(G.line_graph(labels=False)):
            if len(M)==c:
                R = [L[p[0]:p[1]] for p in P[1:-1]]
                for m,_ in M:
                    R[m].extend(R[m+1])
                for m in sorted((m for _,m in M), reverse=True):
                    del R[m]
                yield R

For example:

for p in all_list_partitions([1, 2, 3, 4, 5, 14, 6, 8, 9, 10, 11, 12, 7, 9, 10, 11, 12, 13], 6):
     print(p)

immediately gives:

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

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_partitions(L,k):
    assert len(L) % k == 0
    m = len(L) // k

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

    intervals in L, where consecutive intervals are connected with an edge
    D = DiGraph()

    # add vertices
    v_start = (-oo,0)
    v_end = (len(L),oo)
    D.add_vertices([v_start,v_end])
    for i in range(len(L)):
        u = i+1
        D.add_vertex((i,u))
= []
    for s in M.keys():
        t = s
        l = []
        while u<len(L) and L[u]==L[u-1]+1:
            u s in M:
            l.append(s)
            intervals.append( tuple(l) )
            s += 1
            D.add_vertex((i,u))

    for 
    intervals = sorted(intervals)
    #print('# intervals:', len(intervals) )

    parts = []
    for l1,l2 in Combinations(intervals,2):
        u,v in Tuples(D.vertices(sort=False),2):
= sorted([l1,l2])
        if u[1]==v[0]:
            D.add_edge(u,v, int(u==v_start or v==v_end or L[v[0]]<=L[u[1]-1]+1) )    # weight is 1 len(u)+len(v)==k and u[-1]+1<v[0]:
            parts.append( u+v )

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

    for p in Combinations(parts,m):
        if u,v cannot be concatented into a 1-gap list

    from sage.graphs.path_enumeration import shortest_simple_paths
    for w,P in shortest_simple_paths(D, v_start, v_end, by_weight=True, report_weight=True):
        if w>m+1:
            break       # weight is too large, cannot get m-tuple by concatenation
        c = len(P) - 2 - m      # number of concatenations to perform
        if c<0:
            continue

        G = Graph()
        for i in range(1,len(P)-1):
            if D.edge_label(P[i],P[i+1])==0:    # can concatenate
                G.add_edge(i-1,i)

        # find matchings in G of size c, and concatenate lists according to them
        from sage.graphs.independent_sets import IndependentSets
        for M in IndependentSets(G.line_graph(labels=False)):
            if len(M)==c:
                R = [L[p[0]:p[1]] for p in P[1:-1]]
                for m,_ in M:
                    R[m].extend(R[m+1])
                for m in sorted((m for _,m in M), reverse=True):
                    del R[m]
    sorted(sum( p, tuple() )) == L:
            yield R
p

For example:

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

immediately gives:gives that there are 114 solutions for a given L.

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_partitions(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 s in M:
            l.append(s)
            intervals.append( tuple(l) )
            s += 1

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

    parts = []
    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(intervals) len(parts) )
    #print(parts)

    for p in Combinations(parts,m):
        if sorted(sum( p, tuple() )) == L:
            yield 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 114 solutions for a given L.

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_partitions(L,k):
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 s in M:
            l.append(s)
t in M and len(l)<k:
            l.append(t)
            intervals.append( tuple(l) )
            s t += 1

    intervals = sorted(intervals)
    #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('# #print('# parts:', len(parts) )
    #print(parts)

    for p in Combinations(parts,m):
        if sorted(sum( p, tuple() )) == L:
            yield 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 114 165 solutions for a given L.

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

    intervals = sorted(intervals)
    #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) )
    #print(parts)

    for p in Combinations(parts,m):
        if sorted(sum( p, tuple() )) == L:
            yield p
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.