Search code examples
mathcombinationspseudocode

Generate Unique Combinations of Integers

I am looking for help with pseudo code (unless you are a user of Game Maker 8.0 by Mark Overmars and know the GML equivalent of what I need) for how to generate a list / array of unique combinations of a set of X number of integers which size is variable. It can be 1-5 or 1-1000.

For example:

IntegerList{1,2,3,4}

1,2

1,3

1,4

2,3

2,4

3,4

I feel like the math behind this is simple I just cant seem to wrap my head around it after checking multiple sources on how to do it in languages such as C++ and Java. Thanks everyone.

Solution

  • As there are not many details in the question, I assume:

    • Your input is a natural number n and the resulting array contains all natural numbers from 1 to n.
    • The expected output given by the combinations above, resembles a symmetric relation, i. e. in your case [1, 2] is considered the same as [2, 1].
    • Combinations [x, x] are excluded.
    • There are only combinations with 2 elements.
    • There is no List<> datatype or dynamic array, so the array length has to be known before creating the array.
    • The number of elements in your result is therefore the binomial coefficient m = n over 2 = n! / (2! * (n - 2)!) (which is 4! / (2! * (4 - 2)!) = 24 / 4 = 6 in your example) with ! being the factorial.

    First, initializing the array with the first n natural numbers should be quite easy using the array element index. However, the index is a property of the array elements, so you don't need to initialize them in the first place.

    You need 2 nested loops processing the array. The outer loop ranges i from 1 to n - 1, the inner loop ranges j from 2 to n. If your indexes start from 0 instead of 1, you have to take this into consideration for the loop limits. Now, you only need to fill your target array with the combinations [i, j]. To find the correct index in your target array, you should use a third counter variable, initialized with the first index and incremented at the end of the inner loop.

    I agree, the math behind is not that hard and I think this explanation should suffice to develop the corresponding code yourself.