algoritmo de combinaciones

Question

Quiero hacer un algoritmo de clasificación simple.

teniendo en cuenta la entrada "abcde", me gustaría obtener el resultado a continuación. ¿podría decirme el algoritmo para eso?

arr[0] = "a" 
arr[1] = "ab" 
arr[2] = "ac" 
arr[3] = "ad" 
arr[4] = "ae" 
arr[5] = "abc" 
arr[6] = "abd" 
arr[7] = "abe" 
... 
arr[n] = "abcde" 

arr[n+1] = "b" 
arr[n+2] = "bc" 
arr[n+3] = "bd" 
arr[n+4] = "be" 
arr[n+5] = "bcd" 
arr[n+5] = "bce" 
arr[n+5] = "bde" 
... 
arr[n+m] = "bcde" 
... 
... 

Answer 1

Un algoritmo para "generar Power Set" de una matriz es lo que está buscando. Puede probar Google u otro motor de búsqueda para encontrar el algoritmo que mejor se adapte a sus necesidades.

Answer 2

Usted está describiendo power set. Aquí hay algunos códigos en C++:

#include <vector> 
#include <string> 
#include <algorithm> 
#include <functional> 
using namespace std; 

vector<string> string_powerset(string const &in) { 
    vector<string> result(1); // start output with one empty string 
    result.reserve(1 << in.size()); // output size = 2^(in.size()) 
    if (result.capacity() != 1<<in.size()) throw range_error("too big"); 

    for (string::const_iterator it = in.begin(); it != in.end(); ++ it) { 
     size_t middle = result.size(); // duplicate what we have so far 
     result.insert(result.end(), result.begin(), result.end()); 

      // append current character onto duplicated output 
     for_each(result.begin() + middle, result.end(), 
      bind2nd(mem_fun_ref(&string::push_back), * it)); 
    } 
    return result; 
} 

Probado trabajando: v). La verificación de rango no es la mejor, pero lo que sea.

Este código tenderá a desbordarse, debido al crecimiento exponencial del powerset, por lo que solo debe pasar cadenas cortas. La otra respuesta publicada evita este problema al generar y devolver una cadena a la vez. Sin embargo, esto es más fácil de entender, y usar una pieza de código mucho más grande y confusa sería una optimización prematura a menos que realmente tenga un problema de desbordamiento.

EDIT: I wrote up a next_subset answer, y no se parece en nada a Ben.

Answer 3

En C++, dada la siguiente rutina:

template <typename Iterator> 
bool next_combination(const Iterator first, Iterator k, const Iterator last) 
{ 
    /* Credits: Mark Nelson http://marknelson.us */ 
    if ((first == last) || (first == k) || (last == k)) 
     return false; 
    Iterator i1 = first; 
    Iterator i2 = last; 
    ++i1; 
    if (last == i1) 
     return false; 
    i1 = last; 
    --i1; 
    i1 = k; 
    --i2; 
    while (first != i1) 
    { 
     if (*--i1 < *i2) 
     { 
     Iterator j = k; 
     while (!(*i1 < *j)) ++j; 
     std::iter_swap(i1,j); 
     ++i1; 
     ++j; 
     i2 = k; 
     std::rotate(i1,j,last); 
     while (last != j) 
     { 
      ++j; 
      ++i2; 
     } 
     std::rotate(k,i2,last); 
     return true; 
     } 
    } 
    std::rotate(first,k,last); 
    return false; 
} 

entonces puede proceder a hacer lo siguiente:

std::string s = "abcde"; 
for(std::size_t i = 1; i != s.size(); ++i) 
{ 
    do 
    { 
     std::cout << std::string(s.begin(),s.begin() + i) << std::endl; 
    } 
    while(next_combination(s.begin(),s.begin() + i,s.end())); 
} 

Nota: Esto se debe esperar para ver 2^n-1 combinaciones, donde n es la longitud de la matriz o cadena.