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?

Answer 1

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 incrementer. 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.

Answer 2

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.

Answer 3

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.

Answer 4

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 5

So upon further research, it turns out that what I'm trying to do is called a Cartesian Product. I ended up using a slightly modified version of this code. Just thought I'd update this in case anyone else stumbles on this question looking for the same answer.