# Refinement between Lists of lists

Consider the following lists of lists L1 = [[0,1,2],[1,2],[2,2]] and L2 = [[0,1],,[1,2],[1,2]]. We say that L2 is a refinement of L1. How to check whether a list of lists is a refinement of another list of lists in Sage.

In the case of set partitions, we have the option refinement. But I need to work with the multisets and its multi partitions. So I am using lists and there is no refinement option for lists of lists.

Kindly help me with how to implement this.

Thank you.

edit retag close merge delete

Does the order matter? Is [[0,1]] a refinement of [[1, 0, 2]]?

@John Palmieri No. The order doesn't matter. In your previous comment if you meant [[0,1],] is a refinement of [[1,0,2]] then it is a refinement. Thank you.

In the given link, they are checking whether a list is a sublist of another list or not. I am unable to see how it can be used here. Can you please explain it to me? Thank you.

Surely you care whether each list in L2 is a sublist of a list in L1? Then you also want to know that if you concatenate and sort the two lists, the results are equal. Is that good enough? If not, perhaps the code at the link I provided can be modified to do what you need.

Sort by » oldest newest most voted

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].append(k)
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,1],[0,1],[1,1],,,]
sage: is_refinement(L2, L1)
[[2, 4], [0, 1, 6], [3, 5]]
sage: L2 + L2  # matches L1
[0, 1, 2]
sage: L2 + L2 + L2  # matches L1
[0, 0, 1, 2]
sage: L2 + L2  # matches L1
[1, 1, 2]

more