Arbitrary number of nested-loops? [duplicate]

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.

0 0 0 0 0 0 0 1 0 0 1 0 0 0 1 1 0 1 0 0 0 1 0 1 0 1 1 0 0 1 1 1 1 0 0 0 1 0 0 1 1 0 1 0 1 0 1 1 1 1 0 0 1 1 0 1 1 1 1 0 1 1 1 1 

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

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

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.

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.

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.

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