4

Im having some issues with trying to update a nested for loop to use recursion instead. Is it possible to access the a,b and c variables from the earlier for loops when using recursion? Below is a simple example of what im trying to convert into a recursive call.

for(int a= 0; a < 10; a++)
{
    for(int b = 0; b < 20; b++)
    {
        for(int c = 0; c < 10; c++)
        {
            int[] indexes = new int[3]{a,b,c}
            collection.add(indexes);
        }
    }
}

EDIT: The solution needs to be able to be adjusted at runtime, such that a user can select how many levels are required.

Improve this question
9
  • 3
    In recursion, you usually have to pass the counters in as well as the inputs. Can you show your best attempt at a recursive function? Commented Sep 20, 2013 at 10:19
  • So i would need some sort of collection like a List<int> which i would need to use to hold each parameter of each nested for loop? Would appreciate it if you could be a little more specific, as im fairly new to recursion, thanks. Commented Sep 20, 2013 at 10:21
  • The problem you are trying to solve is not recursive. Commented Sep 20, 2013 at 10:23
  • 1
    @AlexandreVinçon could you suggest a possible solution then, apart from hard coding the for loops. Commented Sep 20, 2013 at 10:23
  • Not clear (at least to me) what you are looking to do, you could explain it with more details? Commented Sep 20, 2013 at 10:27

6 Answers 6

Reset to default
10

Here's a recursive solution (using a functional programming style):

public static IEnumerable<IEnumerable<int>> GetCombinations(IEnumerable<int> limits)
{
    if (limits.Any() == false)
    {
        // Base case.
        yield return Enumerable.Empty<int>();
    }
    else
    {
        int first = limits.First();
        IEnumerable<int> remaining = limits.Skip(1);
        IEnumerable<IEnumerable<int>> tails = GetCombinations(remaining);

        for (int i = 0; i < first; ++i)
            foreach (IEnumerable<int> tail in tails)
                yield return Yield(i).Concat(tail);
    }
}

// Per http://stackoverflow.com/q/1577822
public static IEnumerable<T> Yield<T>(T item)
{
    yield return item;
}

Sample use:

var sequences = GetCombinations(new [] { 5, 3, 2, 4 /* ... */ });
foreach (var sequence in sequences)
    Console.WriteLine(string.Join(", ", sequence));

/* Output:
0, 0, 0, 0
0, 0, 0, 1
0, 0, 0, 2
0, 0, 0, 3
0, 0, 1, 0
0, 0, 1, 1
0, 0, 1, 2
0, 0, 1, 3
0, 1, 0, 0
0, 1, 0, 1
0, 1, 0, 2
... */

For OP's specific scenario (adding arrays to collection):

var sequences = GetCombinations(new [] { 10, 20, 10 });
collection.AddRange(sequences.Select(s => s.ToArray()));
Improve this answer
Sign up to request clarification or add additional context in comments.

Comments

5

Ok, try with this

static void AddToCollectionRecursive(
    List<int[]> collection,
    params int[] counts)
{
    AddTo(collection, new List<int>(), counts, counts.Length - 1);
}

static void AddTo(
    List<int[]> collection,
    IEnumerable<int> value,
    IEnumerable<int> counts,
    int left)
{
    for (var i = 0; i < counts.First(); i++)
    {
        var list = value.ToList();

        list.Add(i);

        if (left == 0)
        {
            collection.Add(list.ToArray());
        }
        else
        {
            AddTo(collection, list, counts.Skip(1), left - 1);
        }
    }
}

Usage is like this AddToCollectionRecursive(collection, 10, 20, 10);.

Improve this answer

1 Comment

I believe this is what i was looking for. Slightly different, dare i say it, better than what i came up with. Thanks.
2

something like this will work:

public void CreateIndexes(int a, int b, int c, Collection collection)
{
    if(c == 10) {b++; c = 0;}
    if(b == 20) {a++; b = 0;}
    if(a == 10) return;

    int[] indexes = new int[3]{a,b,c}
    collection.add(indexes);
    c++;

    CreateIndexes(a, b, c, collection);
}
Improve this answer

Comments

1

Off the top of my head, i.e. not tested, something like this might work:

    List<int[]> collection = new List<int[]>();
    private void AddValues(int a, int b, int c)
    {

        collection.Add(new[] { a, b, c });

        if (c < 10)
        {
            c++;
            AddValues(a, b, c);
        }

        if (b < 20)
        {
            b++;
            c = 0;
            AddValues(a, b, c);   
        }

        if (a < 10)
        {
            a++;
            b = 0;
            c = 0;
            AddValues(a, b, c);
        }
    }

Start it by calling:

AddValues(0, 0, 0);
Improve this answer

6 Comments

Need to reset b and c in a branch and c in b branch.
Also, this code is not exactly good to the stack. In our case recursion should be ideally there levels deep, but with this code it will be 9+19+9=37 levels deep.
This requires that i know there are 3 inputs though. If the number of inputs were changed to 4 at runtime, then it wouldnt produce the correct results.
That wasn't in your original spec. You sound like the sales guys I work with. Instead of taking 3 parameters, take a list<int>, then foreach item in that list increment the current, reset the previous values, do some magic, call the method again with the current values and then hope for best.
DaveDev, sorry to inform you but just ran a quick test and your code produces doubles. Made the test with a, b and c < 1 which gives 41 items in the collection. Leaving the resets out of the respective branch still produces 8 items instead of 4. Don't have a solution for it at the moment.
|
1

Well, i think that if u resolve this problem using recursion, it will consume more memory and other resources!

But there is my suggestion:

private void FunctionName(int a, int b, int c, List<int[]> list)
{
    if (a<10)
    { 
       if (b<20)
       {
           if (c<10)
           {
               list.Add(new[] { a, b, c });
               c++;
               FunctionName(a,b,c,list);
            }
            else
            {
                 c=0;
                 b++;
                 FunctionName(a,b,c,list);
            }
       }
       else
       {
          b=0;
          a++;
          FunctionName(a,b,c,list);
       }
    }
 }

You call like this : FunctionName(0,0,0,list).

Hope it works! ^^

Improve this answer

Comments

0

This solution takes an Action for the work to be done at the leafs:

void ForEachCombo(int from, int to, int nrLevels, Action<int[]> action)
{
    int[] d = new int[nrLevels];
    InnerFor(from, to, 0);
    void InnerFor(int from, int to, int level)
    {
        if (level == nrLevels)
            action(d);
        else
            for (d[level] = from; d[level] <= to - nrLevels + level + 1; d[level]++)
                InnerFor(d[level] + 1, to, level + 1);
    }
}

Use like this:

ForEachCombo(0, 9, 3, (d) =>
{
    Console.WriteLine(string.Join(", ", d));
});

// Output
0, 1, 2
0, 1, 3
0, 1, 4
0, 1, 5
...
6, 7, 9
6, 8, 9
7, 8, 9
//

If you want to you can save a level of recursion by writing like this:

void ForEachCombo(int from, int to, int nrLevels, Action<int[]> action)
{
    int[] d = new int[nrLevels];
    InnerFor(from, to, 0);
    void InnerFor(int from, int to, int level)
    {
        if (level == nrLevels - 1)
            for (d[level] = from; d[level] <= to - nrLevels + level + 1; d[level]++)
                action(d);
        else
            for (d[level] = from; d[level] <= to - nrLevels + level + 1; d[level]++)
                InnerFor(d[level] + 1, to, level + 1);
    }
}
Improve this answer

Comments

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.