Refinement between Lists of lists

edit

Here is a solution using integral linear programming. To understand the code, you could have a look at the Thematic Tutorial Linear Programming (Mixed Integer).

def is_refinement(p1, p2):
    from sage.numerical.mip import MIPSolverException
    n1 = len(p1)
    n2 = len(p2)
    elements = set().union(*p1).union(*p2)

    M = MixedIntegerLinearProgram()
    a = M.new_variable(binary=True)

    # each element in p1 should be used exactly once 
    for i in range(n1):
        M.add_constraint(M.sum(a[i,j] for j in range(n2)) == 1)

    # each element in p2 should be union of elements in p1
    for x in elements:
        for j in range(n2):
            M.add_constraint(M.sum(a[i,j] * p1[i].count(x) for i in range(n1)) == p2[j].count(x))

    try:
        M.solve()
    except MIPSolverException:
        return False
    d = M.get_values(a)
    result = [[] for _ in range(n2)]
    for k in d:
        if d[k]:
            result[k[1]].append(k[0])
    return result

The result of the function is either False or a list telling how to recover the elements of p2 by concatenation of the elements from p1. Here is an example

sage: L1 = [[0,1,2],[0,0,1,2],[1,1,2]]
sage: L2 = [[0],[0,1],[0,1],[1,1],[2],[2],[2]]                                                                                                                                                                      
sage: is_refinement(L2, L1)
[[2, 4], [0, 1, 6], [3, 5]]
sage: L2[2] + L2[4]  # matches L1[0]
[0, 1, 2]
sage: L2[0] + L2[1] + L2[6]  # matches L1[1]
[0, 0, 1, 2]
sage: L2[3] + L2[5]  # matches L1[2]
[1, 1, 2]