9
$\begingroup$

A partition of an integer $n$ is a non-decreasing list of positive integers summing to $n$. For example, $3$ can be partitioned as $1 + 1 + 1$, $1 + 2$ or just $3$, but $2 + 1$ is indistinct from $1 + 2$ (e.g., order does not matter).

A refinement of a partition $P$ of $n$ is (I hope I'm using this term correctly) another partition of $n$ obtained by further partitioning the elements of $P$. That definition is a little loose, but I hope an example will clarify. The partitions $(1,1,1,3)$ and $(1,1,2,2)$ both refine $(3,3)$, since they are each obtained by partitioning the elements of $(3,3)$. By contrast, $(2,4)$ is also a partition of $6$, but it does not refine $(3,3)$. (Notice refinement induces a poset structure on the collection of partitions of an integer.)

Given a particular partition $P$ of $n$, is there a built-in function in Sage to iterate over all refinements of $P$? For example, iterating over the refinements of $(2,3)$ should produce something like the list $(2,3)$, $(1,2,2)$, $(1,1,3)$, $(1,1,1,2)$, $(1,1,1,1,1)$.

I see how one could build such a function "from scratch" (list all partitions for each entry and just stitch them together), but I wonder if there is something hidden in a number theory or lattice/poset theory package that I'm not aware of.

Alternate Goal: For my purposes, I would even be happy with the ability to efficiently check whether one integer partition refines another (as opposed to returning the list of all such refinements).

Update: Some evidence that this problem is hard in general and a suggested solution via integer linear programming.

$\endgroup$
  • $\begingroup$ There seems to be a function here that returns a list of all refinements of a partition. Is that the sort of thing you're looking for? $\endgroup$ – pjs36 May 31 '16 at 21:00
  • $\begingroup$ @pjs36 That function generates the refinements of a set partition. I'm interested in integer partitions. Perhaps a canonical labeling of the elements of the $n$-element set would let me leverage it toward my purpose. Thanks for the idea. $\endgroup$ – Austin Mohr May 31 '16 at 21:15
  • $\begingroup$ Not once have I remembered that there are two different kinds of partitions (and consequently, remembered to pay attention to what kind of partition we're dealing with). D'oh :) $\endgroup$ – pjs36 May 31 '16 at 21:21
  • 1
    $\begingroup$ @pjs36 No problem. After scribbling out a couple examples, I'm afraid connecting set partitions to integer partitions is going to involve trying lots of relabeling of the elements, which is computationally expensive. $\endgroup$ – Austin Mohr May 31 '16 at 21:23
3
+100
$\begingroup$

I don't currently have Sage installed but browsing the documentation seems to indicate that taking a closed interval (with one end of the interval being your partition in question and the other end being the finest, all-ones partition) of the IntegerPartitions poset should do the trick.

EDIT: I just tested it on SageMathCell, an online Sage interface, and it seems to work fine.

> P = Posets.IntegerPartitions(6);
> print(P.closed_interval((3,2,1), P.top()));
> P = Posets.IntegerPartitions(7);
> print(P.closed_interval((4,3), P.top()));

[(3, 2, 1), (3, 1, 1, 1), (2, 2, 1, 1), (2, 1, 1, 1, 1), (1, 1, 1, 1, 1, 1)]
[(4, 3), (4, 2, 1), (4, 1, 1, 1), (3, 3, 1), (3, 2, 2), (3, 2, 1, 1), (3, 1, 1, 1, 1), (2, 2, 2, 1), (2, 2, 1, 1, 1), (2, 1, 1, 1, 1, 1), (1, 1, 1, 1, 1, 1, 1)]

EDIT #2: You can also use is_gequal() to test if one partition is a refinement of another.

> P = Posets.IntegerPartitions(6);
> P.is_gequal((2,2,1,1), (3,3));

True

> P = Posets.IntegerPartitions(6);
> P.is_gequal((4,2), (3,3));

False
$\endgroup$
2
$\begingroup$

Good question. But the list of refinements of a composition is implemented. Thus you can do the following:

def finer(p):
    # Return the list of all partitions refining the given partition ``p``.
    # 
    # EXAMPLES::
    # 
    #     sage: finer(Partition([3,2,1]))
    #     [[1, 1, 1, 1, 1, 1], [2, 1, 1, 1, 1], [2, 2, 1, 1], [3, 1, 1, 1], [3, 2, 1]]
    P = Partitions() # just the constructor
    c = Compositions()(p) # make p into a composition
    return uniq([P(sorted(d, reverse=True)) for d in c.finer()])

This is probably not a very fast method, though... (The uniq is a blunt weapon.)

$\endgroup$
0
$\begingroup$

As you have mentioned before in your own comments the problem is NP-complete. However there are still some simple tricks that might make writing your version of an algorithm easier. Like this one:

If $A = \{a_1,a_2,...,a_p\}$ and $B = \{b_1,b_2,...,b_q\}$ are partitions of the same number $n$ then $A$ is refinement of $B$ if and only if $A'$ is refinement of $B'$ where $A'$ and $B'$ are obtained from $A$ and $B$ respectively by discarding (one by one) identical terms.

An example: $A = \{6 5 5 5 2 2 1\}$, $B = \{7 6 5 3 2 1 1 1\}$. Then $A'=\{552\}$, $B'=\{7311\}$ and we can immediately see that $A'$ is not a refinement of $B'$.

Another one: if for some natural number $k$ the sum of terms in $A$ which are greater than $k$ is greater than the corresponding sum in $B$ then $A$ is not a refinement of $B$. And if those sums are equal then the subpartition of $A$ that contains all those terms must be a refinement of the corresponding subpartition of $B$.

Or more formally, let us denote by $A^{(k)}$ the subpartition of $A$ formed by all terms in $A$ greater than or equal to $k$ where $k$ is any integer. Then the following lemma is obviously true:

LEMMA: If $A$ is a refinement of $B$ then for any $k$ partition $A^{(k)}$ is a subpartition of a refinement of $B^{(k)}$.

The proof is easy because all the terms in $A^{(k)}$ must be "refined" from terms in $B^{(k)}$.

The natural question is whether this is a sufficient condition. Of course if we are allowed to use $k=1$ then yes - we will immediately get what we want, since $A^{(1)} = A$ and $B^{(1)} = B$. Is it sufficient if we restrict this to $k>1$ or some other bound $k>d$? I suspect that the answer is negative.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.