An algorithm thats gives all possible distinct arrays whose positive integer elements sum to a given number

Question

An algorithm which for any input positive integer, gives all possible distinct arrays of positive non-zero integers that can sum to it.

e.g Inputting 4 returns (1,1,1,1), (1,1,2), (1,2,1), (2,1,1), (1,3), (3,1), (2,2), (4)

Not homework, but "research". I just get lost trying.

Someone good at combinatorics would probably know this one.

• dmckee --- ex-moderator kitten: Exact repost of: stackoverflow.com/questions/3688625/… from only a few minutes ago.
• dmckee --- ex-moderator kitten: @Stephen: [homework] is a problem, and you can find a number of discussion of it on meta. Questions about homework are allowed, but there is a consensus that they should come with indications of effort on the part of the poster and should receive good leading but not complete answers. On top of that some posters don't like to have their questions tagged as [homework] (which is the case here, see the edit history of the previous question) if they aren't per se homework. Finally, there is some argument concerning the degree to which that tag is or is not a "meta" tag.

Answer 1

Here is some idea.

If I'm not mistaken the number of the arrays is 2N-1 and the arrays map to bit patterns codding integers form 0 to 2N-1-1 as follows:

I'll show an example for N = 4

The first array is all ones. Imagine every bit in the bit pattern corresponds to the boundary between two array cells

1 1 1 1 <- array elements
 | | | <- sections
 0 0 0 <- bit pattern

Every 1 in the bit pattern means merging two neighbouring cells

1 (1+1) 1 <- array elements (1 2 1)
 | | | <- sections
 0 1 0 <- bit pattern
1 (1+1+1) <- array elements (1 3)
 | | | <- sections
 0 1 1 <- bit pattern
(1+1) (1+1)<- array elements (2 2)
 | | | <- sections
 1 0 1 <- bit pattern
(1+1+1+1) <- array elements (4)
 | | | <- sections
 1 1 1 <- bit pattern

To enumerate all arrays you can generate integers from 0 to 2N-1-1 and for every bit pattern you get, generate the corresponding array. It might be helpful to convert the integer to the string of zeros and ones of length N-1. You decode the pattern as follows:

First cell contains 1 initially. Going through the pattern from left to right, for every bit, if it's 1 add 1 to the current cell, if it's 0 create new cell containing 1.

The pattern 1 1 0 0 1 0 1 for N = 8 would be decoded to an array

(3 1 2 2)

Here is some C++ code without argument validation and processing the pattern from right to left. It just changes the order of arrays produced and is simpler to code.

std::vector<std::vector<int> > generateArrays(unsigned int N)
{
 //validate the argument before processing
 // N > 0 and N <= numeric_limits<unsigned int>::digits
 unsigned int numOfArrays = (1U << (N-1));
 std::vector<std::vector<int> > result(numOfArrays);
 for(unsigned int i = 0; i < numOfArrays; ++i)
 {
 result[i].push_back(1);
 unsigned int mask = 1U;
 while(mask < numOfArrays)
 {
 if((i & mask) != 0)
 {
 result[i].back()++;
 }
 else
 {
 result[i].push_back(1);
 }
 mask <<= 1;
 }
 }
 return result;
}

• Christoffer: I like this approach. This means that the "algorithm" to generate all arrays is a simple loop, and the formatting of bit pattern -> array should be possible to write quite efficiently.
• Etaoin: Sweet! Much more elegant than mine.

Answer 2

Recurse! The first entry (call it a[0]) could be any integer from 1 to N. Then you just need to find all the distinct arrays of positive nonzero integers that add up to N - a[0]...

• edvz: Thanks Etaoin. I shall try it.

Answer 3

Recursive approach

# Pseudo code, not any real language
function all_arrays_summing_to(int N) {
 array_of_arrays All_solutions = ();
 if (N == 1) return { [[1]] }; # This is array of one array containing 1 element with value 1
 for each number x in (1 .. N-1) {
 array_of_arrays AA = all_arrays_summing_to(N - x);
 for each array A in (AA) {
 push x onto array A;
 Add A to All_solutions;
 }
 }
 return All_solutions;
}

• edvz: Excellent DVK. Practical, since I only need up to N=20 or so.

Answer 4

Maybe this isn't the most elegant solution since I'm using "Distinct" to filter out duplicate results but here is one way in C#.

The general idea is that you split the number into an array of 1's then you just combine each node side-by-side together like a tree and select distinct combinations. I pictured it like this:

 [1,1,1]
 / \
[2,1] [1,2]
 \ /
 [3]
class Program
{
 static void Main(string[] args)
 {
 Console.Write("Enter an integer value: ");
 int num = int.Parse(Console.ReadLine());
 var y = new int[num];
 for (int x = 0; x < num; x++)
 y[x] = 1;
 var results = Combine(y, num)
 .Distinct(new ArrayComparer())
 .OrderByDescending(r => r.Length)
 .ToArray();
 foreach (var result in results)
 {
 Console.Write('[');
 for (int x = 0; x < result.Length; x++)
 {
 if (x > 0)
 Console.Write(", ");
 Console.Write(result[x]);
 }
 Console.WriteLine(']');
 }
 Console.ReadKey(true);
 }
 public class ArrayComparer : IEqualityComparer<int[]>
 {
 bool IEqualityComparer<int[]>.Equals(int[] x, int[] y)
 {
 if (x.Length == y.Length)
 {
 for (int z = 0; z < x.Length; z++)
 if (x[z] != y[z])
 return false;
 return true;
 }
 return false;
 }
 int IEqualityComparer<int[]>.GetHashCode(int[] obj)
 {
 return 0;
 }
 }
 public static IEnumerable<int[]> Combine(int[] values, int num)
 {
 int val = 0;
 for (int x = 0; x < values.Length; x++)
 val += values[x];
 if (val == num)
 {
 yield return values;
 if (values.Length - 1 > 0)
 {
 for (int x = 0; x < values.Length; x++)
 {
 int[] combined = new int[values.Length - 1];
 for (int y = 0; y < x; y++)
 combined[y] = values[x];
 if (values.Length > x + 1)
 combined[x] = values[x] + values[x + 1];
 for (int y = x + 2; y < values.Length; y++)
 combined[y - 1] = values[y];
 foreach (var result in Combine(combined, num))
 yield return result;
 }
 }
 }
 }
}

Outputs:

Enter an integer value: 4
[1, 1, 1, 1]
[2, 1, 1]
[1, 2, 1]
[1, 1, 2]
[3, 1]
[2, 2]
[1, 3]
[4]