Home > Mobile >  I want to implement the nested loop as a recursive function in c#
I want to implement the nested loop as a recursive function in c#

Time:08-05

List<string> post = new List<string>();
    
for(int i0= 0; i0 < 4; i0  )
    for(int i1 = 0; i1 < 4; i1  )
        for(int i2 = 0; i2 < 4; i2  )
            for(int i3 = 0; i3 < 4; i3  )
                for(int i4 = 0; i4 < 4; i4  )
                    for(int i5 = 0; i5 < 4; i5  )
                    {
                        post.Add(Convert.ToString(i0)   ","   Convert.ToString(i1)   ","   Convert.ToString(i2)   ","   Convert.ToString(i3)   ","   Convert.ToString(i4)   ","   Convert.ToString(i5));
                    }

It would be nice to implement it simply as a recursive function, but I haven't found a great way yet.

CodePudding user response:

As noted above, changing your iterations to recuresion is not advisable, because it will fill your stack with 4096 call frames.

My answer below is an alternative way to do it, based on @MrSmith42's comment above.

The idea:

Since all your indices have the values 0..3, you can see each combination of them as a number in base 4. i0 will be the least significant digit, and i5 will be the most significant one.

If you need 6 indices, there will be 4^6 combinations of them. There's a one-to-one match between these combinations, and the numbers 0..(4^6-1).

The code below demonstrates this approach. You can also change the number of indiced by changing the constant NUM_INDICES, or the number of values via NUM_VALUES.

Code example:

List<string> post = new List<string>();

const int NUM_VALUES = 4;
const int NUM_INDICES = 6;

int numCobinations = (int)Math.Pow(NUM_VALUES, NUM_INDICES); // Better use an integer exponentiation. I used `Pow` to keep the code short.
int[] indices = new int[NUM_INDICES];   // will hold your indices i0..i5 but in reverse order

// Iterate over all combinations:
for (int iComb=0; iComb<numCobinations;   iComb)
{
    // Create the values for the indices (in reverse order):
    int combination = iComb;
    for (int iIdx=0; iIdx < NUM_INDICES;   iIdx)
    {
        indices[iIdx] = combination % NUM_VALUES;
        combination /= NUM_VALUES;
    }
    // Create the final string. Note that the indices above was created in a reverse order so we reverse again now.
    string str = "";
    for (int iIdx = NUM_INDICES-1; iIdx >= 0; --iIdx)
    {
        str  = indices[iIdx].ToString();
        if (iIdx != 0) str  = ",";
    }
    post.Add(str);
}

// Print the final strings:
foreach (var s in post)
{
    Console.WriteLine(s);
}

Output:

0,0,0,0,0,0
0,0,0,0,0,1
0,0,0,0,0,2
...
3,3,3,3,3,1
3,3,3,3,3,2
3,3,3,3,3,3

CodePudding user response:

You could also do it with just one for-loop. i0 .. i5 have values 0..3 so you can see i0,i1,..i5 as a 6-digit number base 4 (so you could count in one loot from 0 to 4^6-1) and than extract the values for i0 .. i5 from it. – MrSmith42

List<string> post = new List<string>();
for(int count= 0; count < 4096; count  ){
  int i0=(count / 1024) % 4;  // same as "count / 1024"  // same as "count >> 10"
  int i1=(count /  256) % 4;  // same as "(count >> 8)& 3"
  int i2=(count /   64) % 4;  // same as "(count >> 6)& 3"
  int i3=(count /   16) % 4;  // same as "(count >> 4)& 3"
  int i4=(count /    4) % 4;  // same as "(count >> 2)& 3"
  int i5=(count /    1) % 4;  // same as "count % 4"   // same as "count & 3"
  post.Add(Convert.ToString(i0)   ","
           Convert.ToString(i1)   "," 
           Convert.ToString(i2)   "," 
           Convert.ToString(i3)   "," 
           Convert.ToString(i4)   "," 
           Convert.ToString(i5));
 }

Remark instead of deivision and modulo you could also mask the wanted bits and shift them afterwards. (see comments in the code)

CodePudding user response:

A recursive function would receive the nesting level and the current values of the i's (say as an array). If would either perform a for loop on the index of the current level, calling itself with the next level, or just output the i's.

Pseudocode:

Nested(Level, I[6]):
  if Level < 6:
    for I[Level]= 0 to 3:
      Nested(Level 1, I)
  else
    Output(I)

Call with

Nested(0, I)

CodePudding user response:

I agree that a recursive solution is not the best solution. But it works.

var post = new List<string>();

CombineRecursively(Array.Empty<int>(), post);

static int[] CombineRecursively(int[] currentCombination, List<string> results)
{
    const int positionsCount = 6;
    const int maxNumber = 4;

    if (currentCombination.Length > 0 && currentCombination.Last() < maxNumber)
    {
        var newPositions = currentCombination.ToArray();
        newPositions[^1]  = 1;
        CombineRecursively(newPositions, results);
    }

    if (currentCombination.Length < positionsCount)
    {
        return CombineRecursively(currentCombination.Append(0).ToArray(), results);
    }

    results.Add(string.Join(", ", currentCombination));

    return currentCombination;
}

CodePudding user response:

    static void Main(string[] args)
    {
        permute("", "123");
    }

    static void permute(string result, string now)
    {
        if (now == "")
        {
            Console.WriteLine(result);
        }
        else
        {
            for (int i = 0; i < now.Length; i  )
            {
                permute(result   now[i], now.Substring(0, i)   now.Substring(i   1));
            }
        }
    }
  • Related