ASKSAGE: Sage Q&A Forum - RSS feedhttps://ask.sagemath.org/questions/Q&A Forum for SageenCopyright Sage, 2010. Some rights reserved under creative commons license.Sat, 10 Oct 2020 14:07:10 +0200Refinement between Lists of listshttps://ask.sagemath.org/question/53797/refinement-between-lists-of-lists/ 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.Fri, 09 Oct 2020 05:38:52 +0200https://ask.sagemath.org/question/53797/refinement-between-lists-of-lists/Comment by John Palmieri for <p>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.</p>
<p>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. </p>
<p>Kindly help me with how to implement this. </p>
<p>Thank you.</p>
https://ask.sagemath.org/question/53797/refinement-between-lists-of-lists/?comment=53799#post-id-53799Do the answers at https://stackoverflow.com/questions/35964155/checking-if-list-is-a-sublist help?Fri, 09 Oct 2020 06:53:03 +0200https://ask.sagemath.org/question/53797/refinement-between-lists-of-lists/?comment=53799#post-id-53799Comment by vdelecroix for <p>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.</p>
<p>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. </p>
<p>Kindly help me with how to implement this. </p>
<p>Thank you.</p>
https://ask.sagemath.org/question/53797/refinement-between-lists-of-lists/?comment=53808#post-id-53808The problem is much harder for multisets!Sat, 10 Oct 2020 12:41:15 +0200https://ask.sagemath.org/question/53797/refinement-between-lists-of-lists/?comment=53808#post-id-53808Comment by John Palmieri for <p>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.</p>
<p>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. </p>
<p>Kindly help me with how to implement this. </p>
<p>Thank you.</p>
https://ask.sagemath.org/question/53797/refinement-between-lists-of-lists/?comment=53798#post-id-53798Does the order matter? Is [[0,1]] a refinement of [[1, 0, 2]]?Fri, 09 Oct 2020 06:49:48 +0200https://ask.sagemath.org/question/53797/refinement-between-lists-of-lists/?comment=53798#post-id-53798Comment by GA3165 for <p>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.</p>
<p>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. </p>
<p>Kindly help me with how to implement this. </p>
<p>Thank you.</p>
https://ask.sagemath.org/question/53797/refinement-between-lists-of-lists/?comment=53800#post-id-53800@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.Fri, 09 Oct 2020 07:55:29 +0200https://ask.sagemath.org/question/53797/refinement-between-lists-of-lists/?comment=53800#post-id-53800Comment by GA3165 for <p>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.</p>
<p>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. </p>
<p>Kindly help me with how to implement this. </p>
<p>Thank you.</p>
https://ask.sagemath.org/question/53797/refinement-between-lists-of-lists/?comment=53801#post-id-53801In 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.Fri, 09 Oct 2020 07:57:33 +0200https://ask.sagemath.org/question/53797/refinement-between-lists-of-lists/?comment=53801#post-id-53801Comment by John Palmieri for <p>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.</p>
<p>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. </p>
<p>Kindly help me with how to implement this. </p>
<p>Thank you.</p>
https://ask.sagemath.org/question/53797/refinement-between-lists-of-lists/?comment=53805#post-id-53805Surely 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.Fri, 09 Oct 2020 18:36:25 +0200https://ask.sagemath.org/question/53797/refinement-between-lists-of-lists/?comment=53805#post-id-53805Comment by vdelecroix for <p>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.</p>
<p>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. </p>
<p>Kindly help me with how to implement this. </p>
<p>Thank you.</p>
https://ask.sagemath.org/question/53797/refinement-between-lists-of-lists/?comment=53810#post-id-53810I don't understand in your example why L2 is a refinement of L1. Namely, the number 2 appears 4 times in L1 and only 3 times in L2.Sat, 10 Oct 2020 12:50:55 +0200https://ask.sagemath.org/question/53797/refinement-between-lists-of-lists/?comment=53810#post-id-53810Answer by vdelecroix for <p>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.</p>
<p>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. </p>
<p>Kindly help me with how to implement this. </p>
<p>Thank you.</p>
https://ask.sagemath.org/question/53797/refinement-between-lists-of-lists/?answer=53811#post-id-53811Here is a solution using integral linear programming. To understand the code, you could have a look at the [Thematic Tutorial Linear Programming (Mixed Integer)](https://doc.sagemath.org/html/en/thematic_tutorials/linear_programming.html).
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]Sat, 10 Oct 2020 13:04:21 +0200https://ask.sagemath.org/question/53797/refinement-between-lists-of-lists/?answer=53811#post-id-53811Comment by rburing for <p>Here is a solution using integral linear programming. To understand the code, you could have a look at the <a href="https://doc.sagemath.org/html/en/thematic_tutorials/linear_programming.html">Thematic Tutorial Linear Programming (Mixed Integer)</a>.</p>
<pre><code>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
</code></pre>
<p>The result of the function is either <code>False</code> or a list telling how to recover the elements of <code>p2</code> by concatenation of the elements from <code>p1</code>. Here is an example</p>
<pre><code>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]
</code></pre>
https://ask.sagemath.org/question/53797/refinement-between-lists-of-lists/?comment=53813#post-id-53813Nice one! :)Sat, 10 Oct 2020 14:07:10 +0200https://ask.sagemath.org/question/53797/refinement-between-lists-of-lists/?comment=53813#post-id-53813