sacar - combinación y permutación en C++

sacar combinaciones en c++

Question

¿Cuál es la biblioteca existente más utilizada en C ++ para dar toda la combinación y permutación de k elementos de n elementos?

No estoy preguntando el algoritmo sino la biblioteca o métodos existentes.

Gracias.

Answer 1

@ Charles Bailey arriba:

Podría estar equivocado, pero creo que los primeros dos algoritmos anteriores no eliminan los duplicados entre el primero y el medio. Tal vez no estoy seguro de cómo usarlo.

4 elige 2 ejemplo:
12 34
12 43 (después del género)
13 24 (después de next_permutation)
13 42 (después del género)
14 23 (después de next_permutation)
14 32 (después de ordenar)
21 34 (después de next_permutation)

Así que agregué un cheque para ver si el valor en cursiva está en orden antes de volver, pero definitivamente no habría pensado en la parte que escribiste (¡muy elegante! ¡Gracias!).

No completamente probado, solo pruebas superficiales ...

template
bool next_combination(RandIt first, RandIt mid, RandIt last)
{
typedef typename std::iterator_traits< RandIt >::value_type value_type;
std::sort(mid, last, std::greater< value_type >() );
while(std::next_permutation(first, last)){
if(std::adjacent_find(first, mid, std::greater< value_type >() ) == mid){
return true;
}
std::sort(mid, last, std::greater< value_type >() );
return false;
}

Answer 2

Combinaciones: del artículo de Mark Nelson sobre el mismo tema, tenemos next_combination http://marknelson.us/2002/03/01/next-permutation Permutaciones: de STL tenemos std :: next_permutation

 template <typename Iterator>
inline bool next_combination(const Iterator first, Iterator k, const Iterator last)
{
if ((first == last) || (first == k) || (last == k))
return false;
Iterator itr1 = first;
Iterator itr2 = last;
++itr1;
if (last == itr1)
return false;
itr1 = last;
--itr1;
itr1 = k;
--itr2;
while (first != itr1)
{
if (*--itr1 < *itr2)
{
Iterator j = k;
while (!(*itr1 < *j)) ++j;
std::iter_swap(itr1,j);
++itr1;
++j;
itr2 = k;
std::rotate(itr1,j,last);
while (last != j)
{
++j;
++itr2;
}
std::rotate(k,itr2,last);
return true;
}
}
std::rotate(first,k,last);
return false;
}

Answer 3

Decidí probar las soluciones de dman y Charles Bailey aquí. Los llamaré soluciones A y B respectivamente. Mi prueba es visitar cada combinación de un vector<int> size = 100, 5 a la vez. Aquí está el código de prueba:

Código de prueba

struct F
{
unsigned long long count_;
F() : count_(0) {}
bool operator()(std::vector<int>::iterator, std::vector<int>::iterator)
{++count_; return false;}
};
int main()
{
typedef std::chrono::high_resolution_clock Clock;
typedef std::chrono::duration<double> sec;
typedef std::chrono::duration<double, std::nano> ns;
int n = 100;
std::vector<int> v(n);
std::iota(v.begin(), v.end(), 0);
std::vector<int>::iterator r = v.begin() + 5;
F f;
Clock::time_point t0 = Clock::now();
do
{
f(v.begin(), r);
} while (next_combination(v.begin(), r, v.end()));
Clock::time_point t1 = Clock::now();
sec s0 = t1 - t0;
ns pvt0 = s0 / f.count_;
std::cout << "N = " << v.size() << ", r = " << r-v.begin()
<< ", visits = " << f.count_ << ''/n''
<< "/tnext_combination total = " << s0.count() << " seconds/n"
<< "/tnext_combination per visit = " << pvt0.count() << " ns";
}

Todo el código se compiló usando clang ++ -O3 en un procesador Intel Core i5 a 2,8 GHz.

Solución A

La solución A da como resultado un ciclo infinito. Incluso cuando hago n muy pequeño, este programa nunca termina. Posteriormente downvoted por esta razón.

Solución B

Esta es una edición. La solución B cambió en el transcurso de escribir esta respuesta. Al principio dio respuestas incorrectas y debido a una actualización muy rápida ahora da respuestas correctas. Imprime:

N = 100, r = 5, visits = 75287520
next_combination total = 4519.84 seconds
next_combination per visit = 60034.3 ns

Solución C

Luego probé la solución de N2639 que se ve muy similar a la solución A, pero funciona correctamente. Llamaré a esta solución C y se imprime:

N = 100, r = 5, visits = 75287520
next_combination total = 6.42602 seconds
next_combination per visit = 85.3531 ns

La solución C es 703 veces más rápida que la solución B.

Solución D

Finalmente hay una solución D que se encuentra here . Esta solución tiene una firma / estilo diferente y se llama for_each_combination , y se usa de forma muy parecida a std::for_each . El código de controlador anterior cambia entre las llamadas del temporizador como así:

Clock::time_point t0 = Clock::now();
f = for_each_combination(v.begin(), r, v.end(), f);
Clock::time_point t1 = Clock::now();

La solución D imprime:

N = 100, r = 5, visits = 75287520
for_each_combination = 0.498979 seconds
for_each_combination per visit = 6.62765 ns

La solución D es 12.9 veces más rápida que la solución C, y más de 9000 veces más rápida que la solución B.

Considero que este es un problema relativamente pequeño: solo 75 millones de visitas. A medida que el número de visitas aumenta en los miles de millones, la discrepancia en el rendimiento entre estos algoritmos continúa creciendo. La solución B ya es difícil de manejar. La solución C eventualmente se vuelve difícil de manejar. La solución D es el algoritmo de mayor rendimiento para visitar todas las combinaciones que conozco.

El here también contiene muchos otros algoritmos para enumerar y visitar permutaciones con varias propiedades (circular, reversible, etc.). Cada uno de estos algoritmos se diseñó con el rendimiento como uno de los objetivos. Y tenga en cuenta que ninguno de estos algoritmos requiere que la secuencia inicial esté ordenada. Los elementos ni siquiera necesitan ser menos LessThanComparable .

Answer 4

Esta respuesta proporciona una solución de esfuerzo de implementación mínima. Puede no tener un rendimiento aceptable si desea recuperar combinaciones para grandes rangos de entrada.

La biblioteca estándar tiene std::next_permutation y puedes construir trivialmente una next_k_permutation de ella y una next_combination de eso.

template<class RandIt, class Compare>
bool next_k_permutation(RandIt first, RandIt mid, RandIt last, Compare comp)
{
std::sort(mid, last, std::tr1::bind(comp, std::tr1::placeholders::_2
, std::tr1::placeholders::_1));
return std::next_permutation(first, last, comp);
}

Si no tiene tr1::bind o boost::bind , necesitará construir un objeto de función que intercambie los argumentos a una comparación dada. Por supuesto, si solo está interesado en una variante next_combination std::less de next_combination , puede usar std::greater directamente:

template<class RandIt>
bool next_k_permutation(RandIt first, RandIt mid, RandIt last)
{
typedef typename std::iterator_traits<RandIt>::value_type value_type;
std::sort(mid, last, std::greater< value_type >());
return std::next_permutation(first, last);
}

Esta es una versión relativamente segura de next_combination . Si puede garantizar que el rango [mid, last) está en orden tal como lo estaría después de una llamada a next_combination , puede usar el más simple:

template<class BiDiIt, class Compare>
bool next_k_permutation(BiDiIt first, BiDiIt mid, BiDiIt last, Compare comp)
{
std::reverse(mid, last);
return std::next_permutation(first, last, comp);
}

Esto también funciona con iteradores bidireccionales e iteradores de acceso aleatorio.

Para generar combinaciones de salida en lugar de k-permutaciones, debemos asegurarnos de que sacamos cada combinación solo una vez, por lo que devolveremos una combinación solo si es una permutación k en orden.

template<class BiDiIt, class Compare>
bool next_combination(BiDiIt first, BiDiIt mid, BiDiIt last, Compare comp)
{
bool result;
do
{
result = next_k_permutation(first, mid, last, comp);
} while (std::adjacent_find( first, mid,
std::tr1::bind(comp, std::tr1::placeholders::_2
, std::tr1::placeholders::_1) )
!= mid );
return result;
}

Las alternativas serían usar un iterador inverso en lugar del parámetro swapping bind call o usar std::greater explícitamente si std::less es la comparación utilizada.