c++ - permutaciones - variaciones

¿Hay algún método mejor para hacer la permutación de la cuerda?

Question

void permute(string elems, int mid, int end)
{
    static int count;
    if (mid == end) {
        cout << ++count << " : " << elems << endl;
        return ;
    }
    else {
    for (int i = mid; i <= end; i++) {
            swap(elems, mid, i);
            permute(elems, mid + 1, end);
            swap(elems, mid, i);
        }
    }
}

La función anterior muestra las permutaciones de str (con str[0..mid-1] como prefijo constante, y str[mid..end] como sufijo permutable). Entonces podemos usar permute(str, 0, str.size() - 1) para mostrar todas las permutaciones de una cadena.

Pero la función usa un algoritmo recursivo; tal vez su rendimiento podría mejorarse?

¿Hay algún método mejor para permutar una cadena?

Answer 1

¡Aquí hay uno que acabo de romper!

void permute(const char* str, int level=0, bool print=true) {

    if (print) std::cout << str << std::endl;

    char temp[30];
    for (int i = level; i<strlen(str); i++) {

        strcpy(temp, str);

        temp[level] = str[i];
        temp[i] = str[level];

        permute(temp, level+1, level!=i);
    }
}

int main() {
    permute("1234");

    return 0;
}

Answer 2

¡En realidad puedes hacerlo usando Knuth shuffling algo!

// find all the permutations of a string
// using Knuth radnom shuffling algorithm!

#include <iostream>
#include <string>

template <typename T, class Func>
void permutation(T array, std::size_t N, Func func)
{
    func(array);
    for (std::size_t n = N-1; n > 0; --n)
    {
        for (std::size_t k = 0; k <= n; ++k)
        {
            if (array[k] == array[n]) continue;
            using std::swap;
            swap(array[k], array[n]);
            func(array);
        }
    }
}

int main()
{
    while (std::cin.good())
    {
        std::string str;
        std::cin >> str;
        permutation(str, str.length(), [](std::string const &s){ 
            std::cout << s << std::endl; });
    }
}

Answer 3

¡La única forma de mejorar significativamente el rendimiento es encontrar una manera de evitar iterar a través de todas las permutaciones en primer lugar!

Permuting es una operación inevitablemente lenta (O (n!), O peor, dependiendo de lo que hagas con cada permutación), desafortunadamente, nada de lo que puedas hacer cambiará este hecho.

Además, tenga en cuenta que cualquier compilador moderno aplanará su recursión cuando las optimizaciones estén habilitadas, por lo que las ganancias de rendimiento (pequeñas) de la optimización manual se reducen aún más.

Answer 4

¿Desea ejecutar todas las permutaciones o contar el número de permutaciones?

Para el primero, use std::next_permutation según lo sugerido por otros. Cada permutación toma O (N) tiempo (pero menos tiempo amortizado) y ninguna memoria excepto su cuadro de llamadas, frente a O (N) tiempo y O (N) memoria para su función recursiva. ¡Todo el proceso es O (N!) Y no se puede hacer mejor que esto, como dijeron otros, porque no se pueden obtener más de O (X) resultados de un programa en menos de O (X) tiempo. Sin una computadora cuántica, de todos modos.

Para este último, solo necesita saber cuántos elementos únicos hay en la cadena.

big_int count_permutations( string s ) {
    big_int divisor = 1;
    sort( s.begin(), s.end() );
    for ( string::iterator pen = s.begin(); pen != s.end(); ) {
        size_t cnt = 0;
        char value = * pen;
        while ( pen != s.end() && * pen == value ) ++ cnt, ++ pen;
        divisor *= big_int::factorial( cnt );
    }
    return big_int::factorial( s.size() ) / divisor;
}

La velocidad está limitada por la operación de encontrar elementos duplicados, que para los caracteres se puede hacer en el tiempo O (N) con una tabla de búsqueda.

Answer 5

¿Por qué no pruebas std::next_permutation() o std::prev_permutation() ?

Campo de golf:

std::next_permutation()
std::prev_permutation()

Un simple ejemplo:

#include<string>
#include<iostream>
#include<algorithm>

int main()
{
   std::string s="123";
   do
   {

      std::cout<<s<<std::endl;

   }while(std::next_permutation(s.begin(),s.end()));
}

Salida:

123
132
213
231
312
321

Answer 6

Aquí hay un algoritmo no recursivo en C ++ de la entrada de Wikipedia para la generación desordenada de permutaciones . Para la cadena s de longitud n , para cualquier k de 0 a n! - 1 n! - 1 inclusive, lo siguiente modifica s para proporcionar una permutación única (es decir, diferente de las generadas para cualquier otro valor k en ese rango). Para generar todas las permutaciones, ejecútelo para todo n! k valores en el valor original de s.

#include <algorithm>

void permutation(int k, string &s) 
{
    for(int j = 1; j < s.size(); ++j) 
    {
        std::swap(s[k % (j + 1)], s[j]); 
        k = k / (j + 1);
    }
}

Aquí swap(s, i, j) intercambia la posición iyj de la cadena s.

Answer 7

Cualquier algoritmo para generar permutaciones se ejecutará en tiempo polinomial, porque el número de permutaciones para caracteres dentro de una cadena de n longitud es (n!) . Dicho esto, hay algunos algoritmos in situ bastante simples para generar permutaciones. Vea el algoritmo Johnson-Trotter .

Answer 8

Cualquier algoritmo que use o genere todas las permutaciones tomará O (N! * N) tiempo, O (N!) Como mínimo para generar todas las permutaciones y O (N) para usar el resultado, y eso es realmente lento. Tenga en cuenta que la impresión de la cadena también es O (N) afaik.

En un segundo, solo puede manejar cadenas de hasta 10 o 11 caracteres, independientemente del método que utilice. Desde 11! * 11 = 439084800 iteraciones (haciendo esto muchas en un segundo en la mayoría de las máquinas lo está presionando) y 12! * 12 = 5748019200 iteraciones. Así que incluso la implementación más rápida tomaría de 30 a 60 segundos en 12 caracteres.

El factorial simplemente crece demasiado rápido para que usted pueda ganar algo al escribir una implementación más rápida, a lo sumo obtendrá un personaje. Entonces sugeriría la recomendación de Prasoon. Es fácil de codificar y es bastante rápido. Aunque seguir con tu código está completamente bien también.

Solo te recomendaría que tengas cuidado de que no tengas involuntariamente caracteres extra en tu cadena, como el carácter nulo. Como eso hará que tu código sea un factor de N más lento.

Answer 9

En particular, quiere std::next_permutation() .

void permute(string elems, int mid, int end)
{
  int count = 0;
  while(next_permutation(elems.begin()+mid, elems.end()))
    cout << << ++count << " : " << elems << endl;
}

... o algo así...

Answer 10

Esta no es la mejor lógica, pero entonces, soy un principiante. Estaré muy feliz y obligado si alguien me da sugerencias sobre este código

#include<iostream.h>
#include<conio.h>
#include<string.h>
int c=1,j=1;


int fact(int p,int l)
{
int f=1;
for(j=1;j<=l;j++)
{
f=f*j;
if(f==p)
return 1;

}
return 0;
}


void rev(char *a,int q)
{
int l=strlen(a);
int m=l-q;
char t;
for(int x=m,y=0;x<q/2+m;x++,y++)
{
t=a[x];
a[x]=a[l-y-1];
a[l-y-1]=t;
}
c++;
cout<<a<<"  ";
}

int perm(char *a,int f,int cd)
{
if(c!=f)
{
int l=strlen(a);
rev(a,2);
cd++;
if(c==f)return 0;
if(cd*2==6)
{
for(int i=1;i<=c;i++)
{
if(fact(c/i,l)==1)
{
rev(a,j+1);
rev(a,2);
break;
}
}
cd=1;
}
rev(a,3);
perm(a,f,cd);
}
return 0;
}

void main()
{
clrscr();
char *a;
cout<<"/n/tEnter a Word";
cin>>a;
int f=1;

for(int o=1;o<=strlen(a);o++)
f=f*o;

perm(a,f,0);
getch();
}

Answer 11

Esta publicación: http://cplusplus.co.il/2009/11/14/enumerating-permutations/ trata sobre la permuta de cualquier cosa, no solo de cadenas. La publicación en sí y los comentarios a continuación son bastante informativos y no me gustaría copiar y pegar.

Answer 12

He escrito un algoritmo de permutación recientemente. Utiliza un vector de tipo T (plantilla) en lugar de una cadena, y no es súper rápido porque usa recursión y hay mucha copia. Pero tal vez puedas inspirar el código. Puedes encontrar el código here .

Answer 13

Incluso me costaba entender esa versión recursiva de la primera vez y me llevó algo de tiempo buscar una forma de berre. Más método para encontrar (que puedo pensar) es usar el algoritmo propuesto por Narayana Pandita . La idea básica es:

1. Primero ordena la cadena dada en orden decreciente y luego encuentra el índice del primer elemento del final que es menos que su siguiente carácter lexicigráficamente. Llame a este elemento index el ''primer índice''.
2. Ahora encuentre el carácter más pequeño que sea mayor que el elemento en el ''primer índice''. Llame a este elemento index el ''ceilIndex''.
3. Ahora intercambie los elementos en ''firstIndex'' y ''ceilIndex''.
4. Invierta la parte de la cadena desde el índice ''firstIndex + 1'' hasta el final de la cadena.
5. (En lugar del punto 4) También puede ordenar la parte de la cadena desde el índice ''firstIndex + 1'' hasta el final de la cadena.

Los puntos 4 y 5 hacen lo mismo, pero la complejidad del tiempo en el caso del punto 4 es O (n * n!) Y que en el caso del punto 5 es O (n ^ 2 * n!).

El algoritmo anterior puede incluso aplicarse al caso cuando tenemos caracteres duplicados en la cadena. :

El código para mostrar toda la permutación de una cadena:

#include <iostream>

using namespace std;

void swap(char *a, char *b)
{
    char tmp = *a;
    *a = *b;
    *b = tmp;
}


int partition(char arr[], int start, int end)
{
    int x = arr[end];
    int i = start - 1;
    for(int j = start; j <= end-1; j++)
    {
        if(arr[j] <= x)
        {
            i = i + 1;
            swap(&arr[i], &arr[j]);
        }
    }
    swap(&arr[i+1], &arr[end]);
    return i+1;
}

void quickSort(char arr[], int start, int end)
{
    if(start<end)
    {
        int q = partition(arr, start, end);
        quickSort(arr, start, q-1);
        quickSort(arr, q+1, end);
    }
}

int findCeilIndex(char *str, int firstIndex, int n)
{
    int ceilIndex;
    ceilIndex = firstIndex+1;

    for (int i = ceilIndex+1; i < n; i++)
    {
        if(str[i] >= str[firstIndex] && str[i] <= str[ceilIndex])
            ceilIndex = i;
    }
    return ceilIndex;
}

void reverse(char *str, int start, int end)
{
    while(start<=end)
    {
        char tmp = str[start];
        str[start] = str[end];
        str[end] = tmp;
        start++;
        end--;
    }
}

void permutate(char *str, int n)
{
    quickSort(str, 0, n-1);
    cout << str << endl;
    bool done = false;
    while(!done)
    {
        int firstIndex;
        for(firstIndex = n-2; firstIndex >=0; firstIndex--)
        {
            if(str[firstIndex] < str[firstIndex+1])
                break;
        }
        if(firstIndex<0)
            done = true;
        if(!done)
        {
            int ceilIndex;
            ceilIndex = findCeilIndex(str, firstIndex, n);
            swap(&str[firstIndex], &str[ceilIndex]);
            reverse(str, firstIndex+1, n-1);
            cout << str << endl;
        }
    }
}


int main()
{
    char str[] = "mmd";
    permutate(str, 3);
    return 0;
}

Answer 14

Me gustaría secundar la respuesta de Permaquid . El algoritmo que cita funciona de una manera fundamentalmente diferente de los diversos algoritmos de enumeración de permutación que se han ofrecido. No genera todas las permutaciones de n objetos, genera una permutación específica distinta, dado un número entero entre 0 and n!-1 . Si solo necesita una permutación específica, es mucho más rápido que enumerarlos todos y luego seleccionar uno.

Incluso si necesita todas las permutaciones, proporciona opciones que un algoritmo de enumeración de permutación no ofrece. Una vez escribí un cracker de criptoaritmo de fuerza bruta, que intentó todas las posibles asignaciones de letras a dígitos. Para problemas de base-10 , fue adecuado, ¡ya que solo hay 10! permutaciones para intentar. Pero para base-11 problemas de base-11 tomó un par de minutos y base-12 problemas de base-12 tomaron casi una hora.

Reemplacé el algoritmo de enumeración de permutación que había estado usando con un simple i=0--to--N-1 for-loop, usando el algoritmo Permaquid citado. El resultado fue solo un poco más lento. Pero luego dividí el rango de enteros en cuatro, y ejecuté cuatro bucles for simultáneamente, cada uno en un hilo separado. En mi procesador de cuatro núcleos, el programa resultante corría casi cuatro veces más rápido.

Así como es difícil encontrar una permutación individual usando los algoritmos de enumeración de permutación, generar subconjuntos delineados del conjunto de todas las permutaciones también es difícil. El algoritmo que citó Permaquid hace que ambos sean muy fáciles

Answer 15

No creo que esto sea mejor, pero funciona y no usa recursividad:

#include <iostream>
#include <stdexcept>
#include <tr1/cstdint>

::std::uint64_t fact(unsigned int v)
{
   ::std::uint64_t output = 1;
   for (unsigned int i = 2; i <= v; ++i) {
      output *= i;
   }
   return output;
}

void permute(const ::std::string &s)
{
   using ::std::cout;
   using ::std::uint64_t;
   typedef ::std::string::size_type size_t;

   static unsigned int max_size = 20;  // 21! > 2^64

   const size_t strsize = s.size();

   if (strsize > max_size) {
      throw ::std::overflow_error("This function can only permute strings of size 20 or less.");
   } else if (strsize < 1) {
      return;
   } else if (strsize == 1) {
      cout << "0 : " << s << ''/n'';
   } else {
      const uint64_t num_perms = fact(s.size());
      // Go through each permutation one-by-one
      for (uint64_t perm = 0; perm < num_perms; ++perm) {
         // The indexes of the original characters in the new permutation
         size_t idxs[max_size];

         // The indexes of the original characters in the new permutation in
         // terms of the list remaining after the first n characters are pulled
         // out.
         size_t residuals[max_size];

         // We use div to pull our permutation number apart into a set of
         // indexes.  This holds what''s left of the permutation number.
         uint64_t permleft = perm;

         // For a given permutation figure out which character from the original
         // goes in each slot in the new permutation.  We start assuming that
         // any character could go in any slot, then narrow it down to the
         // remaining characters with each step.
         for (unsigned int i = strsize; i > 0; permleft /= i, --i) {
            uint64_t taken_char = permleft % i;
            residuals[strsize - i] = taken_char;

            // Translate indexes in terms of the list of remaining characters
            // into indexes in terms of the original string.
            for (unsigned int o = (strsize - i); o > 0; --o) {
               if (taken_char >= residuals[o - 1]) {
                  ++taken_char;
               }
            }
            idxs[strsize - i] = taken_char;
         }
         cout << perm << " : ";
         for (unsigned int i = 0; i < strsize; ++i) {
            cout << s[idxs[i]];
         }
         cout << ''/n'';
      }
   }
}

Lo divertido de esto es que el único estado que usa desde la permutación hasta la permutación es el número de la permutación, el número total de permutaciones y la cadena original. Eso significa que se puede encapsular fácilmente en un iterador o algo así sin tener que preservar cuidadosamente el estado correcto exacto. Incluso puede ser un iterador de acceso aleatorio.

Por supuesto, :: std :: next_permutation almacena el estado en las relaciones entre los elementos, pero eso significa que no puede funcionar en cosas desordenadas, y realmente me pregunto qué hace si tienes dos cosas iguales en la secuencia. Puede resolver eso permutando los índices, por supuesto, pero eso agrega un poco más de complicación.

El mío funcionará con cualquier rango de iterador de acceso aleatorio siempre que sea lo suficientemente corto. Y si no lo es, nunca pasarás todas las permutaciones de todos modos.

La idea básica de este algoritmo es que cada permutación de N elementos se puede enumerar. ¡El número total es N! o fact(N) . Y cualquier permutación dada puede considerarse como un mapeo de los índices fuente de la secuencia original en un conjunto de índices de destino en la nueva secuencia. Una vez que tenga una enumeración de todas las permutaciones, lo único que queda por hacer es asignar cada número de permutación a una permutación real.

El primer elemento en la lista permutada puede ser cualquiera de los N elementos de la lista original. El segundo elemento puede ser cualquiera de los N-1 elementos restantes, y así sucesivamente. El algoritmo usa el operador % para separar el número de permutación en un conjunto de selecciones de esta naturaleza. Primero, modulo es el número de permutación por N para obtener un número de [0, N). Descarta el resto dividiendo por N, luego modulo por el tamaño de la lista - 1 para obtener un número de [0, N-1) y así sucesivamente. Eso es lo que hace for (i = loop).

El segundo paso es traducir cada número en un índice en la lista original. El primer número es fácil porque es solo un índice directo. El segundo número es un índice en una lista que contiene todos los elementos excepto el eliminado en el primer índice, y así sucesivamente. Eso es lo que hace for (o = loop).

residuals es una lista de índices en las listas sucesivamente más pequeñas. idxs es una lista de índices en la lista original. Existe una correspondencia de uno a uno entre los valores en residuals e idxs . Cada uno representa el mismo valor en diferentes ''espacios de coordenadas''.

La respuesta apuntada por la respuesta que eligió tiene la misma idea básica, pero tiene una forma mucho más elegante de realizar el mapeo que mi método de fuerza literal y bruta. De esa forma será un poco más rápido que mi método, pero ambos tienen la misma velocidad y ambos tienen la misma ventaja de acceso aleatorio al espacio de permutación, lo que facilita un montón de cosas, incluso (como señaló la respuesta que escogiste) algoritmos paralelos.

Answer 16

Si está interesado en la generación de permutación, hice un trabajo de investigación sobre esto hace un tiempo: http://www.oriontransfer.co.nz/research/permutation-generation

Viene completo con el código fuente, y hay 5 o más métodos diferentes implementados.

Answer 17

Vale la pena investigar el algoritmo aleatorio de mezcla de Knuth .

// In-place shuffle of char array
void shuffle(char array[], int n)
{
    for ( ; n > 1; n--)
    {
        // Pick a random element to move to the end
        int k = rand() % n;  // 0 <= k <= n-1  

        // Simple swap of variables
        char tmp = array[k];
        array[k] = array[n-1];
        array[n-1] = tmp;
    }
}

Answer 18

  //***************anagrams**************//


  //************************************** this code works only when there are no   
  repeatations in the original string*************//
  #include<iostream>
  using namespace std;

  int counter=0;

  void print(char empty[],int size)
  {

  for(int i=0;i<size;i++)
  {
    cout<<empty[i];
  }
  cout<<endl;
  }


  void makecombination(char original[],char empty[],char comb[],int k,int& nc,int size)
{
nc=0;

int flag=0;
for(int i=0;i<size;i++)
{
    flag=0;                                                                   // {
    for(int j=0;j<k;j++)
    {
        if(empty[j]==original[i])                                                                // remove this code fragment
        {                                                                                        // to print permutations with repeatation
            flag=1;
            break;
        }
    }
    if(flag==0)                                                                // }
    {
        comb[nc++]=original[i];
    }
}
//cout<<"checks  ";
//    print(comb,nc);
}


void recurse(char original[],char empty[],int k,int size)
{
char *comb=new char[size];


int nc;


if(k==size)
{
    counter++;
    print(empty,size);
    //cout<<counter<<endl;

}
else
{
    makecombination(original,empty,comb,k,nc,size);
    k=k+1;
    for(int i=0;i<nc;i++)
    {
        empty[k-1]=comb[i];

        cout<<"k = "<<k<<" nc = "<<nc<<" empty[k-1] = "<<empty[k-1]<<endl;//checks the  value of k , nc, empty[k-1] for proper understanding
        recurse(original,empty,k,size);
    }
}

}

int main()
{
const int size=3;
int k=0;
char original[]="ABC";

char empty[size];
for(int f=0;f<size;f++)
empty[f]=''*'';

recurse(original,empty,k,size);

cout<<endl<<counter<<endl;
return 0;
}

Answer 19

**// Prints all permutation of a string**

    #include<bits/stdc++.h>
    using namespace std;


    void printPermutations(string input, string output){
        if(input.length() == 0){
            cout<<output <<endl;
            return;
        }

        for(int i=0; i<=output.length(); i++){
            printPermutations(input.substr(1),  output.substr(0,i) + input[0] + output.substr(i));
        }
    }

    int main(){
        string s = "ABC";
        printPermutations(s, "");
        return 0;
    }