Need help on refactoring a deeply nested code

Question

#include <iostream>
using namespace std;

int main()
{
    int range = 20;
    int totalCombinations = 0;

    for(int i=1; i<=range-2; i++)
    {
        if(range>i)
        {
            for(int j=1; j<=range-1; j++)
                if(j>i)
                {
                    for(int k=1; k<=range-1; k++)
                        if(k>j)
                        {
                            for(int l=1; l<=range-1; l++)
                                if(l>k)
                                {
                                    for(int m=1; m<=range-1; m++)
                                        if(m>l)
                                        {
                                            for(int f=1; f<=range; f++)
                                                if(f>m)
                                                {
                                                    cout << " " <<i<< " " <<j<< " " <<k<< " " <<l<< " " <<m<< " " <<f;
                                                    cin.get(); //pause
                                                    totalCombinations++;
                                                }
                                        }
                                }
                        }
                }
        }
    }
    cout << "TotalCombinations:" << totalCombinations;
}

Answer 1

if(range>i)

Why not just start i at range and avoid the problem? Oh, I had that backwards, but the point stands -- you can easily refactor this to be part of the for condition. No need for an extra conditional.

if(j>i)

Why not just start j at i?

... (Repeat for the other two loops)

That gets rid of half your nesting. As far as the loops themselves go, I would suggest using Extract Method on them.

Answer 2

The first thing you can do is using continue:

for(int i=1; i<=range-2; i++) {
{
    if(range<=i) {
       continue;
    }

    for(int j=1; j<=range-1; j++) {
        if(j<=i) {
           continue;
        }
        //etc for all inner loops
    }
}

This will greatly reduce nesting and IMO improve readability.

Answer 3

The same way you refactor anything. You first have to figure out what the code is doing. In this case, many of the tests are irrelevant, and each of the loops does basically the same thing. You've solved one very specific case (very sloppily) of a more general problem. Working out the general algorithm for the problem will result in a cleaner, simpler solution, and one that is more general. Something like this:

class Combin
{
    int m;
    int n;
    int total;
    std::vector<int> values;

    void calc();
    void dumpVector() const;
public:
    Combin( int m, int n ) : m(m), n(n), total(0) {}
    int operator()() { total = 0; values.clear(); calc(); return total; }
};

void 
Combin::calc()
{
    if ( values.size() == m ) {
        dumpVector();
        ++ total;
    } else {
        values.push_back( values.empty() ? 0 : values.back() + 1 );
        int limit = n - (m - values.size());
        while ( values.back() < limit ) {
            calc();
            ++ values.back();
        }
        values.pop_back();
    }
}

void
Combin::dumpVector() const
{
    for (std::vector<int>::const_iterator iter = values.begin(); iter != values.end(); ++ iter )
        std::cout << ' ' << *iter + 1;
    std::cout << '\n';
}

int main()
{
    Combin c( 6, 20 );
    std::cout << "TotalCombinations:" << c() << std::endl;
    return 0;
}

The only thing really worthy of comment in the above is the calculation of limit in calc, and that's really just an optimization; you could use n and get the same results (but you'd recurse a bit more).

You'll note that in your original versions, the end conditions of the loops are more or less arbitrary: using range systematically would work, or you could work out the formula which I use for limit (which would result in a different end condition for each loop.

Also, my code uses the half open intervals which are ubiquious in C and C++. I think that once you get used to them, you'll find them much easier to reason about.

Answer 4

My C++ is rusty, so let me give you a C# example. Any number of nested loops can be replaced with just one, as follows:

    public void ManyNestedLoopsTest()
    {
        var limits = new[] {2, 3, 4};
        var permutation = new[] {1, 1, 0};
        const int lastDigit = 2;
        var digitToChange = lastDigit;
        while(digitToChange >= 0)
        {
            if (permutation[digitToChange] < limits[digitToChange])
            {
                permutation[digitToChange]++;
                digitToChange = lastDigit;
                PrintPermutation(permutation);
                continue;
            }
            permutation[digitToChange--] = 1;
        }
    }

    private void PrintPermutation(int[] permutation)
    {
        for(int i=0;i<3;i++)
        {
            Console.Write(permutation[i]);
            Console.Write(" ");
        }
        Console.WriteLine(" ");
    }