Arbitrary number of nested-loops? [duplicate]
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?
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;
}
精彩评论