Ask Your Question
2

Refinement between Lists of lists

asked 2020-10-08 22:38:52 -0500

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.

edit retag flag offensive close merge delete

Comments

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

John Palmieri gravatar imageJohn Palmieri ( 2020-10-08 23:49:48 -0500 )edit
John Palmieri gravatar imageJohn Palmieri ( 2020-10-08 23:53:03 -0500 )edit

@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 ( 2020-10-09 00:55:29 -0500 )edit

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 ( 2020-10-09 00:57:33 -0500 )edit

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 ( 2020-10-09 11:36:25 -0500 )edit

1 answer

Sort by ยป oldest newest most voted
3

answered 2020-10-10 06:04:21 -0500

vdelecroix gravatar image

updated 2020-10-10 14:42:21 -0500

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]
edit flag offensive delete link more

Comments

Nice one! :)

rburing gravatar imagerburing ( 2020-10-10 07:07:10 -0500 )edit

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: 2020-10-08 22:38:52 -0500

Seen: 115 times

Last updated: Oct 10