2
$\begingroup$

I'm searching for an algorithm to determine a list of all integer partitions of a number $n$ into a fixed number $m$ of summands (say $n=6$ and $m=4$), for instance to be stored into a list of (vectors-of-length $m$), but with the additional restriction that simple rotations are omitted.

I've already managed the algorithm for the list of vectors, but it still contains rotations. For instance for $n=4$ and $m=6$ :

  list         index and marker for occurence of rotations
  -------------------------------------------
  0  0  0  6  |   1
  0  0  1  5  |   2
  0  1  0  5  |   3
  1  0  0  5  |   4
  0  0  2  4  |   5
  0  1  1  4  |   6
  1  0  1  4  |   7
  0  2  0  4  |   8
  1  1  0  4  |   9
  2  0  0  4  |  10
  0  0  3  3  |  11 = 20
  0  1  2  3  |  12
  1  0  2  3  |  13
  0  2  1  3  |  14
  1  1  1  3  |  15
  2  0  1  3  |  16
  0  3  0  3  |  17
  1  2  0  3  |  18
  2  1  0  3  |  19
  3  0  0  3  |  20 = 11
  0  2  2  2  |  21 = 23 = 26
  1  1  2  2  |  22 = 25
  2  0  2  2  |  23 = 21 = 26
  1  2  1  2  |  24
  2  1  1  2  |  25 = 22
  2  2  0  2  |  26 = 21 = 23

Q1: How could I identify (and remove) the rotations?
Q2: Is there a mathematical model which allows to identify such rotations?

One idea, to use instead of an entry $e$ the primenumber $p_e = \text{primes}(e)$ and then to compare the numbers which are builded from the product over a row, is intriguing at first sight, but removes the information of the order along the rows.

I think the most practically idea might be to

1) identify first all vectors which have exactly one maximum. They cannot be rotations by construction of the list.

2) Then of the remaining do a list_1 of the first differences along the rows (circular over the borders).
Find all with one maximum and rotate them such that the maximum is in the first position, then compare.

3) Then find all with two maxima and do the second difference.

4),5),... Proceed analoguously.

But this is merely an idea and I do not really know whether this will be working at all. A mathematical model would really help here, but I could not imagine one...

Disclaimer: I've searched MSE and MO for "integer partitions" but none found which deals with the problem of rotations of summands

[Update] I've found the numbers for the numbers $n$ and number of summands $m$ in the OEIS as A241926. We find there:

The number of necklaces with n black beads and k white beads.
{Turning over the necklace is not allowed (the group is cyclic not dihedral)}
Table of list-lengthes for *n* in *m* summands

But this does not provide/I don't find a solution for the population of the actual lists. [\update]


$\endgroup$
  • $\begingroup$ Since the order of summands distinguishes solutions (up to rotation), the term composition might be better than partition. $\endgroup$ – hardmath Aug 13 '14 at 14:18
  • $\begingroup$ @hardmath: hmm, a quick view into your link let's it ambiguous for me. Compositions seem to give longer lists, while my list is based on partitions and then furtherly reduced. Don't know yet whether I can make compositions properly restricted. But thanks for the hint! $\endgroup$ – Gottfried Helms Aug 13 '14 at 14:33
  • $\begingroup$ If you start with partitions (order does not matter), then already simple rotations are eliminated. $\endgroup$ – hardmath Aug 13 '14 at 14:52
  • $\begingroup$ @hardmath: Possibly I should say better "cyclic shift" instead "order" which does not matter. So [1,2,0,3] is different from [2,1,0,3] but not from [3,1,2,0] $\endgroup$ – Gottfried Helms Aug 13 '14 at 16:39
  • $\begingroup$ As a technique to remove rotations I can suggest storing the lexicographically least form of a summation. One discards the sums which are not least among their rotated forms, i.e. for which some rotation reduces the lexicographic order. $\endgroup$ – hardmath Aug 13 '14 at 19:10

Your Answer

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

Browse other questions tagged or ask your own question.