algoritmo de combinaciones

5 minutos de lectura

algoritmo de combinaciones
vaquero misterioso

Quiero hacer un algoritmo de clasificación simple.

dada la entrada “abcde”, me gustaría la salida 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"
...
...

1646965869 170 algoritmo de combinaciones
rahmivolkan

Lo que está buscando es un algoritmo para “generar Power Set” a partir de una matriz. Puedes probar Google o algún otro motor de búsqueda para encontrar el algoritmo que mejor se adapte a tus necesidades.

  • +1 porque a veces las personas sienten que necesitan buscar algo en Google pero no conocen el nombre del algoritmo.

    – muxecoide

    24 de marzo de 2010 a las 11:24

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

A continuación, 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: debe esperar ver combinaciones 2^n-1, donde n es la longitud de la matriz o cadena.

  • El sitio web que citó no parece contener este programa.

    – Patatas

    24 de marzo de 2010 a las 18:07

  • deberías esforzarte un poco más: marknelson.us/2002/03/01/next-permutation en la página busque el término: “next_combination”

    Matthieu N.

    24 de marzo de 2010 a las 20:38

  • @Beh: Incorrecto. Puse next_combination en la barra de búsqueda, se completó automáticamente y no arrojó resultados marknelson.us/… . Sospecho que usaste Google. En cualquier caso, esa página no contienen ese programa, solo hay comentarios con enlaces a varios programas similares. Lo más cercano que veo a una explicación es codeguru.com/cpp/cpp/algorithms/combinations/article.php/c5117 pero no tiene este código en particular. Después de volver a publicar el código de alguien, debe proporcionar créditos más claros.

    – Patatas

    7 abr 2010 a las 20:48


algoritmo de combinaciones
matapatatas

Estás describiendo un set de poder. Aquí hay algo de código 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 funcionando :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 debes pasarle 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 tener un problema de desbordamiento.

EDITAR: escribí un next_subset respuesta, y no se parece en nada a la de Ben.

  • Te voté porque haces un buen uso de STL. Pero hay algunas cosas que criticaría, pero estas son cuestiones de estilo. Primero, using namespace std no es una buena idea. En segundo lugar, usar el operador de cambio para potencia de 2 no está claro. Tercero, ¿por qué string const & in en lugar de const string & in (Nunca he visto eso)?

    –Björn Pollex

    25 de marzo de 2010 a las 9:10

  • 1. Sentí que me gané un poco de pereza arreglando la pregunta y escribiendo todo este código. OP no me parece probable que tenga problemas con una base de código grande. Este no es un archivo de encabezado. 2. Así que lo comenté y también noté consternación por la situación de desbordamiento. 3. Mi const el estilo es más uniforme. const se adhiere a la anterior identificador o modificador, a menos que const es el primer token del tipo. Evito el caso especial. También, diciendo string primero “se pone manos a la obra más rápido”.

    – Patatas

    25 de marzo de 2010 a las 11:14

  • Para que conste, esta respuesta ahora tiene 3 votos a favor y 3 a favor. Ningún votante ha dejado un comentario.

    – Patatas

    7 abr 2010 a las 20:40

  • Te voté a favor por la razón por la que votaron en contra. Yo mismo uso el estilo presentado por usted, y si alguien me dice que nunca vio esto antes, simplemente no sé qué decir.

    – No hay nada que podemos hacer

    13 de abril de 2010 a las 13:39

¿Ha sido útil esta solución?

Esta web utiliza cookies propias y de terceros para su correcto funcionamiento y para fines analíticos y para mostrarte publicidad relacionada con sus preferencias en base a un perfil elaborado a partir de tus hábitos de navegación. Al hacer clic en el botón Aceptar, acepta el uso de estas tecnologías y el procesamiento de tus datos para estos propósitos. Configurar y más información
Privacidad