Arbitrary number of nested-loops? [duplicate]

Question

I'm looking to take an arbitrary number of lists (e.g. [2, 1, 4 . . .], [8, 3, ...], . . .) and pick numbers from each list in order to generate all permutations. E.g.:

[2, 8, ...], [2, 3, ...], [1, 8, ...], [1, 3, ...], [4, 8, ...], [4, 3, ...], ...

This is easily accomplished using nested for-loops, but since I'd like to it accept an arbitrary number of lists it seems that the for-loops would have to be hard coded. One for each list. Also, as my program will likely generate many tens of thousands of permutations, I'l like to generate a single permutation at a time (instead of computing them all in one go and storing the result to a vector). Is there a way to accomplish this programatically?

Since the number of lists is know at compile time, I thought maybe I could use template based meta-programming. However that seems clumsy and also doesn't meet the "one at a time" requirement. Any suggestions?

Answer 1

The recursive way ...

void Recurse(const vector<vector<int>>& v, 
             size_t listToTwiddle, 
             vector<int>& currentPermutation)
{
    // terminate recursion
    if (listToTwiddle == v.size())
    {
        for(auto i = currentPermutation.cbegin(); i != currentPermutation.cend(); ++i)
        {
            cout << *i << " ";
        }
        cout << endl;
        return;
    }

    for(size_t i = 0; i < v[listToTwiddle].size(); ++i)
    {
        // pick a number from the current list
        currentPermutation.push_back(v[listToTwiddle][i]);

        // get all permutations having fixed this number
        Recurse(v, listToTwiddle + 1, currentPermutation);

        // restore back to original state
        currentPermutation.pop_back();
    }
}

void Do(const vector<vector<int>>& v)
{
    vector<int> permutation;
    Recurse(v, 0, permutation);
}

Answer 2

The STL did not have a ready-made function for this, but you may be able to write your own implementation by modifying some parts of next_permutation.

The problem is analogous to implement a binary digit adder. Increment array[0]. If the new value of array[0] overflows (meaning that its value is greater than the number of lists you have) then set array[0] to zero and increment array[1]. And so on.