4

Is there an efficient algorithm for finding all sequences of k non-negative integers that sum to n, while avoiding rotations (completely, if possible)? The order matters, but rotations are redundant for the problem I'm working on.

For example, with k = 3 and n = 3, I would want to get a list like the following:

(3, 0, 0), (2, 1, 0), (2, 0, 1), (1, 1, 1).

The tuple (0, 3, 0) should not be on the list, since it is a rotation of (3, 0, 0). However, (0, 3, 0) could be in the list instead of (3, 0, 0). Note that both (2, 1, 0) and (2, 0, 1) are on the list -- I do not want to avoid all permutations of a tuple, just rotations. Additionally, 0 is a valid entry -- I am not looking for partitions of n.

My current procedure is to loop from over 1 <= i <= n, set the first entry equal to i, and then recursively solve the problem for n' = n - i and k' = k - 1. I get some speed-up by mandating that no entry is strictly greater than the first, but this approach still generate a lot of rotations -- for example, given n = 4 and k = 3, both (2,2,0) and (2,0,2) are in the output list.

Edit: Added clarifications in bold. I apologize for not making these issues as clear as I should have in the original post.

Seth
  • 772
  • 5
  • 13
  • You **ARE** looking for partitions of n, but with size **up to** k. And inserting zeros to fill up k spaces – Dr. belisarius Sep 17 '10 at 05:39
  • I think you'd be best off if you calculated all unordered sets that sum to n, and then find all unique sequences avoiding rotations for those sets. – Kirk Broadhurst Sep 17 '10 at 05:55
  • @belisarius: Finding all the partitions of _n_ up to size _k_ is part of the problem, but not all of it. Strictly speaking, two partitions are the same if the order of the summands are permuted. I am not having difficulty computing partitions, or even all permutations of the summands -- the problem is finding all the permutations up to rotation. – Seth Sep 17 '10 at 06:08
  • @Kirk -- Exactly. It's just that I haven't been able to find an efficient way to do the second half of that. – Seth Sep 17 '10 at 06:15

3 Answers3

3

You can first generate the partitions (which ignore order completely) as a tuple (x_1, x_2, ..., x_n)

where x_i = number of times i occurs.

So Sum i* x_i = n.

I believe you already know how to do this (from your comments).

Once you have a partition, you can now generate the permutations for this (viewing it as a multiset {1,1,...,2,2...,...n}, where i occurs x_i times) which ignore rotations, using the answer to this question:

Is there an algorithm to generate all unique circular permutations of a multiset?

Hope that helps.

Community
  • 1
  • 1
  • @seth or Aryabhatta, can you show or link to your algorithm for finding all partition of length k where each rotation matters? That's needed for others to work with this answer, and I want all the rotations for my application. Thanks! – nealmcb Dec 22 '14 at 01:58
1

You could just sort your solutions and eliminate rotations that way.
OR
you can try to make your recursive solution build tuples that will only ever be sorted

how? here's something I made up quickly 

static list<tuple> tups;
void recurse(tuple l, int n, int k, int m)
{
  if (k == 0 && n == 0)
  {
    tups.add(l);
    return;
  }
  if (k == 0)
    return;

  if (k*m > n) //prunes out tuples that could not possibly be sorted
    return;
  else
    for(int x = m; x <= n; x++)
      recurse(l.add(x), n-x, k-1, x); //try only tuples that are increasing
}

call this with m = 0 and an empty list for the initial step.

here's a C# console app implementation : http://freetexthost.com/b0i05jkb4e

Oh, I see my mistake in the assumption of rotation, I thought you just meant permutations, not an actual rotation. However, you can extend my solution to create non-rotational permutations of the unique increasing tuples. I'm working on it now

Jean-Bernard Pellerin
  • 12,556
  • 10
  • 57
  • 79
  • 1
    Thanks for your response. If I'm reading it correctly, I don't think the "try only tuples that are increasing" part is valid. For example, for k = 4, n = 6, the tuple (1, 2, 1, 2) should be part of the output, but no rotation of this tuple is increasing. – Seth Sep 17 '10 at 00:19
1

You need to generate Integer Partitions in lexicographical order.

Here is a very good paper with fast algorithms.

HTH.

Note that CAS programs usually implement these functions. For example in Mathematica:

Innput: IntegerPartitions[10, {3}]
Output: {{8, 1, 1}, {7, 2, 1}, {6, 3, 1}, 
         {6, 2, 2}, {5, 4, 1}, {5, 3, 2}, 
         {4, 4, 2}, {4, 3, 3}}
Dr. belisarius
  • 60,527
  • 15
  • 115
  • 190