Número arbitrario de bucles anidados?

Question

Estoy buscando tomar un número arbitrario de listas (ej. [2, 1, 4 ...), [8, 3, ...], ...) y elegir números de cada lista para generar todas las permutaciones. Ej:

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

Esto se logra fácilmente usando bucles foráneos anidados, pero como me gustaría aceptarlo de forma arbitraria número de listas parece que los for-loops tendrían que estar codificados. Uno para cada lista Además, como mi programa probablemente generará muchas decenas de miles de permutaciones, me gustaría generar una sola permutación a la vez (en lugar de calcularlas todas de una vez y almacenar el resultado en un vector). ¿Hay alguna manera de lograr esto programáticamente?

Dado que el número de listas es conocido en tiempo de compilación, pensé que tal vez podría usar meta-programación basada en plantilla. Sin embargo, eso parece torpe y tampoco cumple con el requisito de "uno a la vez". ¿Alguna sugerencia?

Answer 1

El STL no tenía una función lista para ello, pero es posible que pueda escribir su propia implementación modificando algunas partes de next_permutation.

El problema es análogo a implementar un sumador de dígitos binarios. Incremento array[0]. Si el nuevo valor de array[0] desbordamientos (lo que significa que su valor es mayor que el número de listas que tiene) a continuación, establecer array[0] a cero e incrementar array[1]. Y así.

Answer 2

El uso de la recursividad que probablemente podría "alimentarse" con la posición actual, las listas restantes y así sucesivamente. Esto tiene el potencial de desbordamiento, pero a menudo una función recursiva puede convertirse en una no recursiva (como con un bucle for), aunque gran parte de la elegancia desaparece.

Answer 3

Divertido.

Lo que parece que desear es en realidad una especie de repetidor, que iterar sobre los rangos indicados, y en cada paso que da una permutación.

Se puede, por lo general, ser escrito sin metaprogramming, especialmente desde plantillas variadic sólo se admiten desde C++ 0x. No obstante, es un desafío muy interesante que siento.

Nuestro primer ayudante de aquí va a ser pequeña clase tuple. También vamos a necesitar un número de truco de programación de meta-plantilla para transformar una tupla en otra, pero lo dejaré como ejercicio para que el lector escriba tanto las funciones de meta-plantilla necesarias como las funciones reales para ejecutar la transformación. (léase: esta tarde es demasiado caluroso para llegar a él).

Aquí hay algo para que empieces.

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

Si usted no sabe cómo hacer para meta, el camino más fácil es ir recursivo, entonces requerirá al usuario que indique qué contenedor se desea acceder a través de un método at tomar una N como parámetro para indicar la índice del contenedor

Answer 4

La manera recursiva ...

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

De modo que tras una investigación posterior, resulta que lo que estoy tratando de hacer se llama un producto cartesiano. Terminé usando una versión ligeramente modificada del código this. Solo pensé en actualizar esto en caso de que alguien más tropiece con esta pregunta buscando la misma respuesta.

Answer 6

La forma no recursiva:

#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

Puede utilizar principio fundamental de conteo, como incrementar el último dígito hasta que alcanza su valor máximo, incremente la segunda pasada y así sucesivamente, como una cuenta atrás hace Aquí hay un código de muestra, suponiendo que puede haber una diferencia de longitud de listas de diferencias.

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

intenta ejecutar el código con 4 1 1 1 1 y le dará todas las permutaciones de 4 dígitos de 0 y 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 

Usted puede utilizar matrices 2D para conseguir combinaciones de números.