First time here? Check out the FAQ!

Ask Your Question
2

Refinement between Lists of lists

asked 4 years ago

GA3165 gravatar image

Consider the following lists of lists L1 = [[0,1,2],[1,2],[2,2]] and L2 = [[0,1],[2],[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.

Preview: (hide)

Comments

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

John Palmieri gravatar imageJohn Palmieri ( 4 years ago )
John Palmieri gravatar imageJohn Palmieri ( 4 years ago )

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

GA3165 gravatar imageGA3165 ( 4 years ago )

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.

GA3165 gravatar imageGA3165 ( 4 years ago )

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.

John Palmieri gravatar imageJohn Palmieri ( 4 years ago )

1 Answer

Sort by » oldest newest most voted
3

answered 4 years ago

vdelecroix gravatar image

updated 4 years ago

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]
Preview: (hide)
link

Comments

Nice one! :)

rburing gravatar imagerburing ( 4 years ago )

Your Answer

Please start posting anonymously - your entry will be published after you log in or create a new account.

Add Answer

Question Tools

1 follower

Stats

Asked: 4 years ago

Seen: 403 times

Last updated: Oct 10 '20