Arbitralna liczba zagnieżdżonych pętli?

Question

Czekam na pobranie dowolnej liczby list (np. [2, 1, 4 ...], [8, 3, ...], ...) i wybieranie liczb z każdej listy w celu wygenerowania wszystkie permutacje. Np

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

to łatwo osiągnąć za pomocą zagnieżdżonych pętli for-, ale ponieważ chciałbym, aby go zaakceptować arbitralne liczba list wydaje się, że pętle for musiałyby być mocno zakodowane. Jeden dla każdej listy. Ponadto, ponieważ mój program prawdopodobnie wygeneruje dziesiątki tysięcy permutacji, chciałbym wygenerować pojedynczą permutację jednocześnie (zamiast przeliczać je za jednym razem i zapisywać wynik do wektora). Czy istnieje sposób, aby to osiągnąć programowo?

Ponieważ liczba list jest znana podczas kompilacji, pomyślałem, że mógłbym użyć meta-programowania opartego na szablonach. Wydaje się to jednak nieporęczne i nie spełnia wymogu "jeden na raz". Jakieś sugestie?

Answer 1

STL nie ma do tego gotowej funkcji, ale możesz napisać własną implementację modyfikując niektóre części next_permutation.

Problem jest analogiczny do realizacji binarnego dodania cyfr. Przyrost array[0]. Jeśli nowa wartość array[0] przepełnienia (co oznacza, że ​​jego wartość jest większa niż liczba list), ustaw array[0] na zero i zwiększ array[1]. I tak dalej.

Answer 2

Używając rekursji, prawdopodobnie "nakarmisz się" aktualną pozycją, pozostałymi listami i tak dalej. Ma to potencjał do przepełnienia, ale często funkcja rekursywna może zostać przekształcona w funkcję nierekursywną (jak w przypadku pętli for), chociaż wiele elegancji znika.

Answer 3

Zabawne.

To, czego sobie życzysz, jest w rzeczywistości rodzajem iteratora, który sprawdzałby się w podanych zakresach i na każdym kroku daje permutację.

Zwykle można pisać bez metaprogramowania, zwłaszcza że szablony variadyczne są obsługiwane tylko od C++ 0x. Mimo to jest to bardzo interesujące wyzwanie, które czuję.

Naszym pierwszym pomocnikiem będzie klasa tuple. Będziemy także potrzebować kilku sztuczek programowania meta-szablonów, aby przekształcić jedną krotkę w drugą, ale pozwolę jej na ćwiczenie, aby czytelnik napisał zarówno funkcje meta-szablonu, jak i rzeczywiste funkcje do wykonania transformacji. (przeczytaj: dziś po południu jest za gorąco, abym mógł do tego dojść).

Tutaj masz coś do zrobienia.

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

Jeśli nie wiesz jak się do meta, tym łatwiej sposobem jest pójść rekurencyjna, to wymaga od użytkownika, aby wskazać pojemnik pragnie uzyskać dostęp poprzez at metody zrobieniu N jako parametr do wskazania indeks pojemnika.

Answer 4

Rekurencyjny sposób ...

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

Więc po dalszych badań, okazuje się, że to, co próbuję zrobić nazywamy iloczyn kartezjański. Skończyło się na zastosowaniu nieznacznie zmodyfikowanej wersji kodu this. Pomyślałem, że zaktualizuję to na wypadek, gdyby ktoś inny natknął się na to pytanie, szukając tej samej odpowiedzi.

Answer 6

Non rekurencyjny sposób:

#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

Można użyć fundamentalnych zasad liczenia, jak zwiększając ostatnią cyfrę aż osiągnie swoją wartość maksymalną, a następnie zwiększać przedostatni jeden i tak dalej, jak odliczanie robi Oto przykładowy kod, przy założeniu, że mogą istnieć różnice długości list różnic.

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

próby uruchomienia kodu z 4 1 1 1 1 i to daje wszystkie permutacje 4 cyfry 0 i 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 

Można użyć 2d tablice uzyskania kombinacji nn.