0

I need to find all number subset to get a number N by summing its elements. I don't know how to get through this type of combination problem. In this combination, order matters for different numbers.

example for the number N=4

1 + 1 + 1 + 1
2 + 1 + 1
1 + 2 + 1
1 + 1 + 2
2 + 2
3 + 1
1 + 3

Zeros are not important for me. So how can I get such number sets as an array for an exact number?

Ali Tor
  • 2,772
  • 2
  • 27
  • 58
  • Please clarify your specific problem or add additional details to highlight exactly what you need. As it's currently written, it’s hard to tell exactly what you're asking. Also show us what you've done so far – Roman Marusyk Oct 19 '16 at 21:55
  • 1
    Looks suspiciously like homework. Regardless, you should provide what you have tried so far, SO isn't too keep on solving your algorithms without some attempt on part. – GEEF Oct 19 '16 at 21:56
  • It is unkind to say such things. I am trying to develop a Turkish game called 101 OKEY. The game has 21 tiles, so I gave an exact number because of this reason. And I need the combinations to calculate the best point separating the tile serie from different points. – Ali Tor Oct 19 '16 at 22:00
  • 1
    You could [start with this answer](http://stackoverflow.com/a/15048737/4270650), which gives you all the unique results. Some small modifications to that answer should do what you need. – Will Ray Oct 19 '16 at 22:35
  • 2
    Also have a look at [partitioning (number theory)](https://en.wikipedia.org/wiki/Partition_(number_theory))—you'll find several C# implementations and ways to go about it on google. – trashr0x Oct 19 '16 at 22:53

2 Answers2

1

What you're looking for are called integer compositions, or ordered partitions.

Compositions can be generated recursively (in lexicographic order, if I'm not mistaken) as follows:

public static IEnumerable<List<int>> Compositions(int n)
{
    if (n < 0)
        throw new ArgumentOutOfRangeException(nameof(n));

    return GenerateCompositions(n, new List<int>());
}

private static IEnumerable<List<int>> GenerateCompositions(int n, List<int> comp)
{
    if (n == 0)
    {
        yield return new List<int>(comp); // important: must make a copy here
    }
    else
    {
        for (int k = 1; k <= n; k++)
        {
            comp.Add(k);

            foreach (var c in GenerateCompositions(n - k, comp)) 
                yield return c;

            comp.RemoveAt(comp.Count - 1);
        }
    }
}

Not tested! This was transcribed from a Python implementation. If anyone would like to make corrections or update the code with more idiomatic C#, feel free.

Also, as @aah noted, the number of compositions of n is 2^(n-1), so this becomes unwieldy even for modest n.

Community
  • 1
  • 1
0

If order doesn't matter, there are simply 2^(N-1) possibilities. (Your example doesn't have 2 + 2 or 4)

You can then represent any sequence by its binary representation. To generate, imagine N 1's in a row, so there are N-1 "spaces" between them. Choosing any subset of spaces, you merge any 1's that are adjacent via a chosen space. You can verify this is 1-1 to all possible sets by expanding any such sequence and inserting these spaces.

aah
  • 81
  • 6