next_permutation para combinaciones o subconjuntos en powerset

Question

¿Hay alguna biblioteca o función equivalente que me dé la siguiente combinación de un conjunto de valores como next_permutation en does for me?

Answer 1

Google buscando C++ "next_combination" apareció this.

• búsqueda de "mediados" hacia atrás hasta que encuentre un elemento que es menor que * (fin - 1). Este es el elemento que debemos incrementar. Llame a este "head_pos".
• buscar desde "final" hacia atrás hasta que encuentre el último elemento que es aún más grande que * head_pos. Llámalo "tail_pos".
• intercambiar head_pos y tail_pos. Reordene los elementos de [head_pos + 1, mid [ y [tail_pos + 1, end [en aumento de orden ].

Answer 2

No conozco ninguno. La idea básica es representar tus elementos como una matriz de bits. Así, por ejemplo, usted tiene el conjunto S:

S = {a, b, c} 
[i, j, k] // a is the first bit, b is the second bit, c is the third bit 

Para generar el conjunto potencia de S (solo generan todos los números que son de tamaño == 3 bits mediante el uso de la simple adición):

000 // {} 
001 // {c} 
010 // {b} 
011 // {b, c} 
100 // {a} 
101 // {a, c} 
110 // {a, b} 
111 // {a, b, c} 

Todo lo que tiene que hacer es encontrar qué bits están establecidos y relacionarlos con los elementos de su conjunto.

En la nota final, hay una combinación que puede producir cuando quiere que todos los elementos se utilicen y esa combinación es la propia, porque en combinaciones el orden no importa, así que seguro estamos hablando de un número de elementos n donde 0 <= n <= size(S)

Answer 3

He usado this library cuando he necesitado para hacer esto. Tiene una interfaz muy similar a std::next_permutation, por lo que será fácil de usar si ya la has utilizado anteriormente.

Answer 4

En caso de que no tenga más remedio que implementar su propia función, tal vez este horror pueda ayudar un poco o quizás otros horrores entre las respuestas a esa pregunta.

Algorithm to return all combinations of k elements from n

lo escribí hace algún tiempo y la imagen completa se me escapa ahora :), pero la idea básica es la siguiente: Usted tiene el conjunto original y la combinación actual es un vector de iteradores a los elementos seleccionados . Para obtener la siguiente combinación, escanea el conjunto de derecha a izquierda buscando una "burbuja". Por "burbuja" me refiero a uno o más elementos adyacentes no seleccionados. La "burbuja" podría estar inmediatamente a la derecha. Luego, en Su combinación, intercambia el primer elemento a la izquierda de la "burbuja" y todos los demás elementos de la combinación, que están a la derecha en el conjunto, con un subconjunto de elementos adyacentes que comienza al comienzo de la " burbuja".

Answer 5

La enumeración del conjunto de potencias (es decir, todas las combinaciones de todos los tamaños) puede usar una adaptación del algoritmo de incremento binario.

template< class I, class O > // I forward, O bidirectional iterator 
O next_subset(I uni_first, I uni_last, // set universe in a range 
    O sub_first, O sub_last) { // current subset in a range 
    std::pair< O, I > mis = std::mismatch(sub_first, sub_last, uni_first); 
    if (mis.second == uni_last) return sub_first; // finished cycle 

    O ret; 
    if (mis.first == sub_first) { // copy elements following mismatch 
     std::copy_backward(mis.first, sub_last, ++ (ret = sub_last)); 
    } else ret = std::copy(mis.first, sub_last, ++ O(sub_first)); 
    * sub_first = * mis.second; // add first element not yet in result 
    return ret; // return end of new subset. (Output range must accommodate.) 
} 

El requisito de un iterador bidireccional es desafortunado y podría solucionarse.

que iba a hacer que manejar elementos idénticos (conjuntos múltiples), pero tengo que ir a la cama: v. (

Uso:

#include <iostream> 
#include <vector> 
using namespace std; 

char const *fruits_a[] = { "apples", "beans", "cherries", "durian" }; 
vector<string> fruits(fruits_a, fruits_a + sizeof fruits_a/sizeof *fruits_a); 

int main() { 
    vector<string> sub_fruits(fruits.size()); 
    vector<string>::iterator last_fruit = sub_fruits.begin(); 

    while ( 
     (last_fruit = next_subset(fruits.begin(), fruits.end(), 
        sub_fruits.begin(), last_fruit)) 
      != sub_fruits.begin()) { 
     cerr << "size " << last_fruit - sub_fruits.begin() << ": "; 
     for (vector<string>::iterator fit = sub_fruits.begin(); fit != last_fruit; ++ fit) { 
      cerr << * fit << " "; 
     } 
     cerr << endl; 
    } 
} 

EDIT: Aquí está la versión de . multiconjuntos El conjunto no tiene que ser resuelto, pero los elementos idénticos tienen que ser agrupados

#include <iterator> 
#include <algorithm> 
#include <functional> 

template< class I, class O > // I forward, O bidirectional iterator 
I next_subset(I uni_first, I uni_last, // set universe in a range 
    O sub_first, O sub_last) { // current subset in a range 
    std::pair< O, I > mis = std::mismatch(sub_first, sub_last, uni_first); 
    if (mis.second == uni_last) return sub_first; // finished cycle 

    typedef std::reverse_iterator<O> RO; 
    mis.first = std::find_if(RO(mis.first), RO(sub_first), std::bind1st(
     std::not_equal_to< typename std::iterator_traits<O>::value_type >(), 
     * mis.second)).base(); // move mis.first before identical grouping 

    O ret; 
    if (mis.first != sub_first) { // copy elements after mismatch 
     ret = std::copy(mis.first, sub_last, ++ O(sub_first)); 
    } else std::copy_backward(mis.first, sub_last, ++ (ret = sub_last)); 

    * sub_first = * mis.second; // add first element not yet in result 
    return ret; 
} 

#include <vector> 
#include <iostream> 
using namespace std; 

char const *fruits_a[] = { "apples", "apples", "beans", "beans", "cherries" }; 
vector<string> fruits(fruits_a, fruits_a + sizeof fruits_a/sizeof *fruits_a); 

int main() { 
    vector<string> sub_fruits(fruits.size()); 
    vector<string>::iterator last_fruit = sub_fruits.begin(); 

    while (
     (last_fruit = next_subset(fruits.begin(), fruits.end(), 
            sub_fruits.begin(), last_fruit) 
     ) != sub_fruits.begin()) { 
     cerr << "size " << last_fruit - sub_fruits.begin() << ": "; 
     for (vector<string>::iterator fit = sub_fruits.begin(); fit != last_fruit; ++ fit) { 
      cerr << * fit << " "; 
     } 
     cerr << endl; 
    } 
} 

de salida:.

size 1: apples 
size 2: apples apples 
size 1: beans 
size 2: apples beans 
size 3: apples apples beans 
size 2: beans beans 
size 3: apples beans beans 
size 4: apples apples beans beans 
size 1: cherries 
size 2: apples cherries 
size 3: apples apples cherries 
size 2: beans cherries 
size 3: apples beans cherries 
size 4: apples apples beans cherries 
size 3: beans beans cherries 
size 4: apples beans beans cherries 
size 5: apples apples beans beans cherries 

Answer 6

combinaciones: desde el artículo de Mark Nelson sobre el mismo tema que tenemos next_combination http://marknelson.us/2002/03/01/next-permutation
permutaciones: desde STL hemos 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; 
}