Beliebige Anzahl von Nested-Loops?

Question

Ich suche eine beliebige Anzahl von Listen (zB [2, 1, 4...], [8, 3, ...],...) Und wähle Zahlen aus jeder Liste um sie zu generieren alle Permutationen. Beispiel:

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

Dies wird erreicht, einfach mit verschachtelten for-Schleifen, aber da ich es möchte eine willkürliche akzeptieren Anzahl der Listen Es scheint, dass die For-Schleifen hart codiert werden müssten. Eine für jede Liste. Da mein Programm wahrscheinlich viele Zehntausende von Permutationen erzeugt, möchte ich auch nur eine einzige Permutation erzeugen (anstatt sie alle auf einmal zu berechnen und das Ergebnis in einem Vektor zu speichern). Gibt es eine Möglichkeit, dies programmatisch zu erreichen?

Da die Anzahl der Listen zur Kompilierzeit bekannt ist, dachte ich, dass ich vielleicht Template-basierte Meta-Programmierung verwenden könnte. Das scheint jedoch ungeschickt zu sein und erfüllt auch nicht die "eine nach der anderen" Anforderung. Irgendwelche Vorschläge?

Answer 1

Die STL hatte keine vorgefertigte Funktion dafür, aber Sie können möglicherweise Ihre eigene Implementierung schreiben, indem Sie einige Teile von next_permutation ändern.

Das Problem ist analog, einen binären Digitaddierer zu implementieren. Inkrement array[0]. Wenn der neue Wert array[0] überläuft (dh der Wert ist größer als die Anzahl der Listen, die Sie haben), setzen Sie array[0] auf 0 und erhöhen Sie array[1]. Und so weiter.

Answer 2

Mithilfe der Rekursion könnten Sie sich wahrscheinlich mit der aktuellen Position, den verbleibenden Listen und so weiter "ernähren". Dies kann potenziell überlaufen, aber oft kann eine rekursive Funktion in eine nicht-rekursive Funktion umgewandelt werden (wie bei einer for-Schleife), obwohl ein Großteil der Eleganz verschwindet.

Answer 3

Amüsant.

Was Sie zu wünschen scheinen, ist eigentlich eine Art Iterator, der über die angegebenen Bereiche iterieren würde, und bei jedem Schritt gibt es eine Permutation.

Es kann in der Regel ohne Metaprogrammierung geschrieben werden, zumal variadic Vorlagen nur seit C++ 0x unterstützt werden. Trotzdem ist es eine sehr interessante Herausforderung, die ich fühle.

Unser erster Helfer wird hier kleine tuple Klasse sein. Wir werden auch eine Reihe von Metaschablonen-Programmiertricks benötigen, um ein Tupel in ein anderes zu transformieren, aber ich werde es als Übung für den Leser zulassen, sowohl die notwendigen Meta-Template-Funktionen als auch die eigentlichen Funktionen zum Ausführen der Transformation zu schreiben (Lies: Heute Nachmittag ist es viel zu heiß, um zu mir zu kommen).

Hier ist etwas, um dich in Schwung zu bringen.

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

Wenn Sie nicht wissen, wie meta zu gehen, ist der einfachere Weg rekursiv zu gehen, benötigen dann den Benutzer, um anzuzeigen, welcher Behälter wünscht sie über eine at Methode für den Zugriff auf einen N als Parameter verwendet wird, um anzuzeigen, die Containerindex.

Answer 4

Der rekursive Weg ...

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

Nach weiteren Untersuchungen stellt sich heraus, dass das, was ich versuche, ein kartesisches Produkt genannt wird. Ich endete mit einer leicht modifizierten Version von this Code. Ich dachte nur, ich würde das für den Fall aktualisieren, dass jemand anderes auf diese Frage stößt und nach derselben Antwort sucht.

Answer 6

Die nicht rekursiven Art und Weise:

#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

Sie grundlegendes Prinzip der Zählung verwenden kann, wie die letzte Ziffer erhöht wird, bis er seinen Maximalwert erreicht hat, dann die zweiten letzten erhöhen und so weiter, wie ein Countdown tut Hier ist ein Beispielcode, vorausgesetzt, es könnte Diff-Länge von Diff-Listen sein.

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

versuchen, den Code mit 4 1 1 1 1 und es gibt alle 4-stelligen Permutationen von 0 und 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 

Sie können 2D-Arrays laufen verwenden für Kombinationen von nos bekommen.