任意數量的嵌套循環？

Question

我正在尋找採取任意數量的名單（例如[2，1，4 ...]，[8，3，...]，並從每個列表中挑選數字以生成所有的排列。例如：

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

這很容易用嵌套for循環完成，但是因爲我想接受一個任意的列表的數量似乎for循環將不得不被硬編碼。每個列表一個。另外，由於我的程序可能會產生數以萬計的排列，我喜歡一次生成一個排列（而不是一次全部計算它們並將結果存儲到一個向量）。有沒有辦法完成這個編程？

由於在編譯時知道列表的數量，我想也許我可以使用基於模板的元編程。然而，這似乎笨拙，也不符合「一次一個」的要求。有什麼建議麼？

Answer 1

STL沒有現成的功能，但您可以通過修改next_permutation的某些部分來編寫自己的實現。

這個問題類似於實現一個二進制數字加法器。增量array[0]。如果array[0]的新值溢出（意味着它的值大於您所擁有的列表數），則將array[0]設置爲零並遞增array[1]。等等。

Answer 2

使用遞歸，你可能可以「餵養自己」與當前位置，其餘列表等等。這有可能會溢出，但通常遞歸函數可以變成非遞歸函數（就像使用for循環一樣），儘管大部分優雅消失了。

Answer 3

好玩。

你似乎希望的實際上是一種迭代器，它將遍歷給定的範圍，並且在每一步都給出了一個排列。

它通常可以在沒有元編程的情況下編寫，特別是因爲可變參數模板僅在C++ 0x以後才支持。儘管如此，我覺得這是一個非常有趣的挑戰。

我們的第一個幫手在這裏將會很少tuple類。我們還需要一些元模板編程技巧來將一個元組轉換爲另一個元組，但是我將它作爲練習讓讀者編寫必要的元模板函數和執行轉換的實際函數（閱讀：今天下午我太熱了，太熱了）。

這是讓你去的東西。

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

如果你不知道如何去元，更簡單的方法是去遞歸，然後要求用戶表示她希望通過at方法採取N作爲參數來表示訪問哪個容器集裝箱索引。

Answer 4

遞歸方式...

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

所以經過進一步的研究，事實證明，我試圖做的就是所謂的笛卡爾乘積。我最終使用了this代碼的稍微修改版本。只是以爲我會更新這個以防其他人在這個問題上絆倒尋找相同的答案。

Answer 6

非遞歸的方式：

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

} 

Answer 7

，直到它達到最大值，您可以使用計數的基本原則，如增加最後一個數字，然後增加第二個最後一個等等，就像一個倒計時。 下面是一個示例代碼，假設可能有diff列表的diff長度。

​​

嘗試與4 1 1 1 1運行的代碼，它會給0所有4個位數的排列和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 

可以使用二維數組用於獲取號的組合。