todas las combinaciones de k elementos de n

¿Alguien puede proporcionarme un enlace o pseudocódigo de una función para encontrar todas las combinaciones de k elementos de n? posiblemente en STL. No necesito calcular n elegir k, necesito enumerar todos los vectores de números de tamaño k.

Gracias

En C ++ se le da la siguiente rutina:

 template  inline bool next_combination(const Iterator first, Iterator k, const Iterator last) { /* Credits: Thomas Draper */ 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; } 

Luego puede proceder a hacer lo siguiente:

 // 9-choose-3 std::string s = "123456789"; std::size_t k = 3; do { std::cout << std::string(s.begin(),s.begin() + k) << std::endl; } while(next_combination(s.begin(),s.begin() + k,s.end())); 

O para un std :: vector de int:

 // 5-choose-3 std::size_t n = 5; std::size_t k = 3; std::vector ints; for (int i = 0; i < n; ints.push_back(i++)); do { for (int i = 0; i < k; ++i) { std::cout << ints[i]; } std::cout << "\n"; } while(next_combination(ints.begin(),ints.begin() + k,ints.end())); 

http://howardhinnant.github.io/combinations.html

Busque “for_each_combination”. Si encuentras algo más rápido, házmelo saber. A diferencia de otros algoritmos que a menudo veo, este no requiere que el tipo de elemento sea LessThanComparable.

Crea un vector auxiliar con n – k ceros seguido de k unos. Un cero significa que el elemento en el contenedor original no está incluido, mientras que uno significa que el elemento está incluido.

Ahora usa std :: next_permutation en el vector auxiliar para obtener la siguiente combinación.

Aquí hay un ejemplo perezoso de pseudocódigo que puede hacer el trabajo …

 void nChooseK(array[n],k){ recurse("",array[n],k); } void recurse(initialString,array[n],k){ if(k == 0){ print initialString; return; } for(i=0;i 

Puede usar std :: next_permutation pero es n! y no n elegir k. Podrías filtrarlos después de que los hayas creado. Pero esta solución es O (n!), No realmente perfecta. Aquí está la solución de prueba y error:

 int factorial(int value) { int result = 1; for(int i = 1; i <= value; i++) { result *= i; } return result; } std::set> binomial_coefficient(std::vector input, int k) { std::set> solutions; for(unsigned int i = 0; i < factorial(input.size()); i++) { std::next_permutation(input.begin(), input.end()); solutions.insert(std::set(input.begin(), input.begin() + k)); } return solutions; }