next_permutation per combinazioni o sottoinsiemi in powerset

Question

C'è qualche libreria o funzione equivalente che mi darà la prossima combinazione di un insieme di valori come next_permutation in fa per me?

Answer 1

Googling per C++ "next_combination" attivato this.

• ricerca da "metà" a ritroso fino a trovare un elemento che è più piccolo di quanto * (fine - 1). Questo è l'elemento che dovremmo incrementare. Chiama questo "head_pos".
• ricerca da "fine" all'indietro fino a trovare l'ultimo elemento che è ancora più grande di * head_pos. Chiamalo "tail_pos".
• scambia head_pos e tail_pos. Riordina gli elementi da [head_pos + 1, mid [ e [tail_pos + 1, end [in ordine crescente .

Answer 2

Non ne sono a conoscenza. L'idea di base è di rappresentare i tuoi elementi come un array di bit. Così, per esempio, si ha l'insieme S:

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

Per generare il Power Set di S (solo generare tutti i numeri che sono di dimensioni == 3 bit utilizzando la semplice aggiunta):

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

Tutto quello che devi fare è trovare quali bit sono impostati e metterli in relazione con gli elementi del tuo set.

Sulla nota finale, c'è una combinazione che puoi produrre quando vuoi che tutti gli elementi siano usati e quella combinazione è l'insieme stesso, perché nelle combinazioni l'ordine non ha importanza, di sicuro stiamo parlando di un numero di elementi n dove 0 <= n <= size(S)

Answer 3

Ho usato this library quando ho avuto bisogno di fare questo. Ha un'interfaccia molto simile a std::next_permutation quindi sarà facile da usare se l'hai già usata prima.

Answer 4

Nel caso in cui non si abbia scelta, ma per implementare la propria funzione, forse questo orrore può aiutare un po 'o forse altri orrori tra le risposte a questa domanda.

Algorithm to return all combinations of k elements from n

ho scritto qualche tempo fa e il quadro completo mi sfugge adesso :), ma l'idea di base è questa: Hai la serie originale e la combinazione attuale è un vettore di iteratori agli elementi selezionati . Per ottenere la combinazione successiva, esegui la scansione del set da destra a sinistra alla ricerca di una "bolla". Per "bolla" intendo uno o più elementi adiacenti non selezionati. La "bolla" potrebbe essere immediatamente sulla destra. Quindi, nella tua combinazione, scambi il primo elemento a sinistra della "bolla" e tutti gli altri elementi della combinazione, che sono a destra nell'insieme, con un sottoinsieme di elementi adiacenti che inizia all'inizio del " bolla".

Answer 5

L'enumerazione del gruppo di continuità (ovvero tutte le combinazioni di tutte le dimensioni) può utilizzare un adattamento dell'algoritmo di 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.) 
} 

Il requisito di un iteratore bidirezionale è sfortunato e potrebbe essere risolto.

stavo per farlo gestire elementi identici (multinsiemi), ma ho bisogno di andare a letto: v. (

Usage:

#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: ecco la versione per . multinsiemi Il set non deve essere filtrate ma elementi identici non devono essere raggruppati

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

uscita:.

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

Combinazioni: dall'articolo di Mark Nelson sullo stesso argomento abbiamo next_combination http://marknelson.us/2002/03/01/next-permutation
Permutazioni: da STL abbiamo 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; 
}