How to turn a combinatory hard coded snippet into a recursive function?

Question

Currently I have this code snippet, which is doing what I want: given some objects, it creates all the possible combinations between them.

In this example, imagining there are 4 objects (0, 1, 2 and 3), all the possible combinations of the 4 objects are created (0, 1, 2, 3, 01 (the combination of 0 and 1), 02, 03, 12, 13, 23, 012, 013, 023, 123 and 0123).

Should be noted that there are 2^4 - 1 = 15 combinations and generally 2^number of objects - 1 combinations.

The order of the created objects with this code is: 0 -> 01 -> 012 -> 0123 -> 013 -> 02 -> 023 -> 03 -> 1 -> 12 -> 123 -> 13 -> 2 -> 23 -> 3

The way I get the initial objects and the number of them is defined somewhere else in the code.

int count = 4; //this is gotten elsewhere
int currPos = 0;
var objects = new Object[(2^count)-1];

for (int i = 0; i < count; i++) //loop that creates combinations of only one object
{
    Object obj = new Object(...);
    objects[currPos] = obj;
    currPos += 1;

    for (int j = i + 1; j < count; j++) //loop that creates combinations of two objects
    {
        Object obj = new Object(...);
        objects[currPos] = obj;
        currPos += 1;

        for (int k = j + 1; k < count; k++) //loop that creates combinations of three objects
        {
            Object obj = new Object(...);
            objects[currPos] = obj;
            currPos += 1;

            for (int l = k + 1; l < count; l++) //loop that creates combinations of four objects
            {
                Object obj = new Object(...);
                objects[currPos] = obj;
                currPos += 1;
            }
        }
    }
}

Despite giving the right results, this is hard coded and therefore I am looking for a way to change it into a recursive function (but maintainig its functionality), with the number of objects (which also determines the maximum combinations, four in the example) passing as a parameter.

I have been trying to do something like the code below but with no result, mainly because I can't seem to go to the "previous" loop when necessary, example going from 0123 to 013.

    int count = 4;
    int currPos = 0;
    var objects = new Object[(2^count)-1];
    combinations(count, 0, currPos, objects); //called elsewhere

    private void combinations(int numberOfObjects, int j, int count, int currPos, Object[] objects)

    {   
        if (numberOfObjects == count)
        {
            for (int k = j; k < count; k++)
            {
                Object obj = new Object(...);
                objects[currPos] = obj;
                currPos += 1;
                generateCombinations(numberOfObjects - 1, j + 1, count, currPos, objects);
            }
        }

        if (numberOfObjects < count)
        {
            for (int l = j; l < count; l++)
            {
                Object obj = new Object(...);
                objects[currPos] = obj;
                currPos += 1;

                (...)

                generateCombinations(..., ..., count, currPos, objects);
             }
        }
    }

Surprising that [search](https://www.bing.com/search?q=c%23%20all%20combinations) did not find any existing solution... like [this](http://stackoverflow.com/questions/774457/combination-generator-in-linq) — Alexei Levenkov, Jul 21 '16 at 00:22
Is `generateCombinations` a different function or a misspelling? — vgru, Jul 21 '16 at 07:34

score 0 · Answer 1 · answered Jul 21 '16 at 00:34

Is this the kind of thing you are after?

public IEnumerable<string> GetCombinations(IEnumerable<string> source)
{
    if (source == null || !source.Any())
    {
        return Enumerable.Empty<string>();
    }
    else if (source.Skip(1).Any())
    {
        return new string[] { null, source.First() }.SelectMany(x => GetCombinations(source.Skip(1)), (x, y) => x + y);
    }
    else
    {
        return new string[] { null, source.First() };
    }
}

I can use it like this:

var combinations = GetCombinations(new[] { "0", "1", "2", });

And I get this result:

How to turn a combinatory hard coded snippet into a recursive function?

1 Answers1