Arbitrary number of nested-loops?

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?

I believe, generally an unknown number of for loops are nested with simple recursion. — UncleBens, Aug 21 '10 at 10:06

score 6 · Answer 1 · answered Jul 20 '13 at 04:54

You can use fundamental principal of counting, like incrementing the last digit till it reaches its max value, then increment the second last one and so on, like a countdown does Here is a sample code, assuming there might be diff length of diff lists.

#include <iostream>
using namespace std;
int main() {
    int n;
    cin>>n;
    int a[n], len[n],i,j;
    for(i = 0 ; i < n ; i++)
    {
        cin>>len[i];
        a[i]=0;
    }
    while(1)
    {
        for(i = 0 ; i< n;i++)
            cout<<a[i]<<" ";
        cout<<endl;
        for(j = n-1 ; j>=0 ; j--)
        {
            if(++a[j]<=len[j])
                break;
            else
                a[j]=0;
        }
        if(j<0)
            break;
    }    
    return 0;
}

Try to run the code with 4 1 1 1 1 and it will give all 4 digit permutations of 0 and 1.

You can use 2d arrays for getting combinations of nos.

This has an infinite loop. – user1876508 Apr 17 '14 at 22:47 — user1876508, Apr 17 '14 at 22:47

score 4 · Answer 2 · answered Aug 21 '10 at 16:49

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);
}

rwong · Answer 3 · 2011-04-28T14:49:34.413

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.

edited Apr 28 '11 at 14:49

answered Aug 21 '10 at 08:37

rwong

6,062
1
23
51

score 2 · Answer 4 · answered Aug 21 '10 at 16:01

Amusing.

What you seem to wish for is actually a kind of iterator, that would iterate over the given ranges, and at each step gives you a permutation.

It can, typically, be written without metaprogramming, especially since variadic templates are only supported since C++0x. Nonetheless it's a very interesting challenge I feel.

Our first helper here is going to be little tuple class. We are also going to need a number of meta-template programming trick to transform one tuple into another, but I'll let it as an exercise for the reader to write both the meta-template functions necessary and the actual functions to execute the transformation (read: it's much too hot this afternoon for me to get to it).

Here is something to get you going.

template <class... Containers>
class permutation_iterator
{
public:
  // tuple of values
  typedef typename extract_value<Containers...>::type value_type;

  // tuple of references, might be const references
  typedef typename extract_reference<Containers...>::type reference;

  // tuple of pointers, might be const pointers
  typedef typename extract_pointer<Containers...>::type pointer;

  permutation_iterator(Containers&... containers) { /*extract begin and end*/ }

  permutation_iterator& operator++()
  {
    this->increment<sizeof...(Containers)-1>();
    return *this;
  }

private:
  typedef typename extract_iterator<Containers...>::type iterator_tuple;

  template <size_t N>
  typename std::enable_if_c<N < sizeof...(Containers) && N > 0>::type
  increment()
  {
    assert(mCurrent.at<N>() != mEnd.at<N>());
    ++mCurrent.at<N>();
    if (mCurrent.at<N>() == mEnd.at<N>())
    {
      mCurrent.at<N>() = mBegin.at<N>();
      this->increment<N-1>();
    }
  }

  template <size_t N>
  typename std::enable_if_c<N == 0>::type increment()
  {
    assert(mCurrent.at<0>() != mEnd.at<0>());
    ++mCurrent.at<0>();
  }

  iterator_tuple mBegin;
  iterator_tuple mEnd;
  iterator_tuple mCurrent;
};

If you don't know how to go meta, the easier way is to go recursive, then require the user to indicate which container she wishes to access via a at method taking a N as parameter to indicate the container index.

score 0 · Answer 5 · answered Dec 07 '12 at 13:01

The non recursive way:

#include <vector>
#include <iostream>

// class to loop over space
// no recursion is used
template <class T>
class NLoop{

public:

    // typedefs for readability
    typedef std::vector<T> Dimension;
    typedef std::vector< Dimension > Space;
    typedef std::vector< typename Dimension::iterator > Point;

    // the loop over space and the function-pointer to call at each point
    static void loop(Space space, void (*pCall)(const Point&))
    {

        // get first point in N-dimensional space
        Point current;
        for ( typename Space::iterator dims_it = space.begin() ; dims_it!=space.end() ; ++dims_it )
        {
            current.push_back( (*dims_it).begin() );
        }

        bool run = true;
        while ( run )
        {

            // call the function pointer for current point
            (*pCall)(current);

            // go to next point in space
            typename Space::iterator dims_it = space.begin();
            typename Point::iterator cur_it = current.begin();
            for (  ; dims_it!=space.end() ; ++dims_it, ++cur_it )
            {
                // check if next in dimension is at the end
                if ( ++(*cur_it) == (*dims_it).end() )
                {
                    // check if we have finished whole space
                    if ( dims_it == space.end() - 1 )
                    {
                        // stop running now
                        run = false;
                        break;
                    }
                    // reset this dimension to begin
                    // and go to next dimension
                    *cur_it = (*dims_it).begin();
                }
                else
                {
                    // next point is okay
                    break;
                }
            }

        }
    }
};


// make typedef for readability
// this will be a loop with only int-values in space
typedef NLoop<int> INloop;

// function to be called for each point in space
// do here what you got to do
void call(const INloop::Point &c)
{
    for ( INloop::Point::const_iterator it = c.begin() ; it!=c.end() ; ++it)
    {
        std::cout << *(*it) << " ";
    }
    std::cout << std::endl;
}

int main()
{

    // fill dimension
    INloop::Dimension d;
    d.push_back(1);
    d.push_back(2);
    d.push_back(3);

    // fill space with dimensions
    INloop::Space s;
    s.push_back(d);
    s.push_back(d);
    s.push_back(d);

    // loop over filled 'space' and call 'call'
    INloop::loop(s,call);

    return 0;

}

score 0 · Answer 6 · answered Aug 21 '10 at 11:26

Using recursion you could probably "feed yourself" with the current position, the remaining lists and so forth. This has the potential to overflow, but often a recursive function can be made into a non-recursive one (like with a for loop), although much of the elegance disappears.

Arbitrary number of nested-loops?

6 Answers6

Linked