c++ - permutar - permutaciones y combinaciones
¿Cómo puedo encontrar todas las permutaciones de una cadena sin usar la recursión? (6)
¿Has probado usar el STL? Existe un algoritmo llamado next_permutation que, dado un rango, devolverá verdadero en cada llamada subsiguiente hasta que se hayan encontrado todas las permutaciones. Funciona no solo en cadenas sino en cualquier tipo de "secuencia".
¿Alguien puede ayudarme con esto? Este es un programa para encontrar todas las permutaciones de una cadena de cualquier longitud. Necesita una forma no recursiva de lo mismo. (se prefiere una implementación de lenguaje C)
using namespace std;
string swtch(string topermute, int x, int y)
{
string newstring = topermute;
newstring[x] = newstring[y];
newstring[y] = topermute[x]; //avoids temp variable
return newstring;
}
void permute(string topermute, int place)
{
if(place == topermute.length() - 1)
{
cout<<topermute<<endl;
}
for(int nextchar = place; nextchar < topermute.length(); nextchar++)
{
permute(swtch(topermute, place, nextchar),place+1);
}
}
int main(int argc, char* argv[])
{
if(argc!=2)
{
cout<<"Proper input is ''permute string''";
return 1;
}
permute(argv[1], 0);
return 0;
}
Esto resuelve el problema sin recurrencia. El único problema es que generará una salida duplicada en el caso en que se repita un carácter en la cadena.
#include<iostream.h>
#include<conio.h>
#include<stdio.h>
#include<string.h>
int factorial(int n)
{
int fact=1;
for(int i=2;i<=n;i++)
fact*=i;
return fact;
}
char *str;
void swap(int i,int j)
{
char temp=str[i];
str[i]=str[j];
str[j]=temp;
}
void main()
{
clrscr();
int len,fact,count=1;
cout<<"Enter the string:";
gets(str);
len=strlen(str);
fact=factorial(len);
for(int i=0;i<fact;i++)
{
int j=i%(len-1);
swap(j,j+1);
cout<<"/n"<<count++<<". ";
for(int k=0;k<len;k++)
cout<<str[k];
}
getch();
}
Otro enfoque sería asignar una matriz de n! char arrays y llenarlos de la misma manera que lo haría a mano.
Si la cadena es "abcd", ponga todos los caracteres "a" en la posición 0 para el primer n-1. arrays, en la posición 1 para el siguiente n-1! arrays, etc. ¡Luego coloque todos los caracteres "b" en la posición 1 para el primer n-2! arrays, etc., todos los caracteres "c" en la posición 2 para el primer n-3! ¡matrices, etc., y todos los caracteres "d" en la posición 3 para el primer n-4! matrices, etc., utilizando módulo aritmético en cada caso para pasar de la posición 3 a la posición 0 mientras completa las matrices.
No es necesario intercambiar y usted sabe desde el principio si tiene suficiente memoria para almacenar los resultados o no.
Primer consejo: no pase std: argumentos de cadena por valor. Use referencias de const
string swtch(const string& topermute, int x, int y)
void permute(const string & topermute, int place)
Le ahorrará una gran cantidad de copias innecesarias.
En cuanto a la solución C ++, tiene las funciones std::next_permutation y std::prev_permutation en el encabezado del algorithm . Entonces puedes escribir:
int main(int argc, char* argv[])
{
if(argc!=2)
{
cout<<"Proper input is ''permute string''" << endl;
return 1;
}
std::string copy = argv[1];
// program argument and lexically greater permutations
do
{
std::cout << copy << endl;
}
while (std::next_permutation(copy.begin(), copy.end());
// lexically smaller permutations of argument
std::string copy = argv[1];
while (std::prev_permutation(copy.begin(), copy.end())
{
std::cout << copy << endl;
}
return 0;
}
En cuanto a la solución C, debe cambiar los tipos de variables de std :: string a char * (ugh, y debe administrar la memoria correctamente). Creo que un enfoque similar: escribir funciones
int next_permutation(char * begin, char * end);
int prev_permutation(char * begin, char * end);
con la misma semántica que las funciones STL - lo hará. Puede encontrar el código fuente para std::next_permutation con explicación aquí . Espero que puedas escribir un código similar que funcione en char * (BTW std :: next_permutation puede funcionar con char * sin problemas, pero querías la solución C) ya que soy perezoso para hacerlo solo :-)
Una pila basada en el equivalente no recursivo de tu código:
#include <iostream>
#include <string>
struct State
{
State (std::string topermute_, int place_, int nextchar_, State* next_ = 0)
: topermute (topermute_)
, place (place_)
, nextchar (nextchar_)
, next (next_)
{
}
std::string topermute;
int place;
int nextchar;
State* next;
};
std::string swtch (std::string topermute, int x, int y)
{
std::string newstring = topermute;
newstring[x] = newstring[y];
newstring[y] = topermute[x]; //avoids temp variable
return newstring;
}
void permute (std::string topermute, int place = 0)
{
// Linked list stack.
State* top = new State (topermute, place, place);
while (top != 0)
{
State* pop = top;
top = pop->next;
if (pop->place == pop->topermute.length () - 1)
{
std::cout << pop->topermute << std::endl;
}
for (int i = pop->place; i < pop->topermute.length (); ++i)
{
top = new State (swtch (pop->topermute, pop->place, i), pop->place + 1, i, top);
}
delete pop;
}
}
int main (int argc, char* argv[])
{
if (argc!=2)
{
std::cout<<"Proper input is ''permute string''";
return 1;
}
else
{
permute (argv[1]);
}
return 0;
}
Intenté hacerlo como C y evité los contenedores STL de C ++ y las funciones de los miembros (aunque utilicé un constructor por simplicidad).
Tenga en cuenta que las permutaciones se generan en orden inverso al original.
Debo agregar que usar una pila de esta manera es simplemente simular la recursión.
#include <iostream>
#include <string>
using namespace std;
void permuteString(string& str, int i)
{
for (int j = 0; j < i; j++) {
swap(str[j], str[j+1]);
cout << str << endl;
}
}
int factorial(int n)
{
if (n != 1) return n*factorial(n-1);
}
int main()
{
string str;
cout << "Enter string: ";
cin >> str;
cout << str.length() << endl;
int fact = factorial(str.length());
int a = fact/((str.length()-1));
for (int i = 0; i < a; i++) {
permuteString(str, (str.length()-1));
}
}