Ask Your Question

# Revision history [back]

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)

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

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

# the elements in p2 must be union of elements in p1
for x in d1.keys():
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]


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

# the elements each element in p2 must should be union of elements in p1
for x in d1.keys():
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]