Progtwig para imprimir permutaciones de elementos dados

Recientemente participé en la competencia de progtwigción certificada de ACM. Esta es la pregunta que no podía hacer en ese momento:

“Dado un conjunto de enteros que tienen n elementos, escriba un progtwig para imprimir todas las permutaciones”.

Por favor dime cómo hacer esta pregunta. ¿Hay algún algoritmo para hacer este tipo de preguntas?

suponiendo que no haya repeticiones: simplemente cambie cada elemento con todos los elementos siguientes posibles e invoque recursivamente la función.

void permute(int *array,int i,int length) { if (length == i){ printArray(array,length); return; } int j = i; for (j = i; j < length; j++) { swap(array+i,array+j); permute(array,i+1,length); swap(array+i,array+j); } return; } 

Puede ver el código con funciones auxiliares swap() e printArray() realizando con un caso de prueba básico en ideone

Bonificación : Esto es similar a la idea de la mezcla de fisher-yates , pero aquí -intenta cambiar el elemento en i con el siguiente elemento elegido al azar- lo cambias con todos ellos, cada uno a la vez.

Un enfoque recursivo debería funcionar bien:

 If the list is empty Return the only possible permutation, an empty list. Else For each element of the list Put the element at the first place (ie swap it with the first element) (If the element is same as the first one, don't swap) Recursively find all the permutations of the rest of the list 

Este algoritmo no generará permutaciones repetidas.

Aquí hay una implementación de Python:

 def permute(s): if len(s) == 0: return [[]] ret = [s[0:1] + x for x in permute(s[1:])] for i in range(1, len(s)): if s[i] == s[0]: continue s[0], s[i] = s[i], s[0] ret += [s[0:1] + x for x in permute(s[1:])] return ret s = [0, 1, 2, 3] for x in permute(s): print x 

Lo similar en C debería ser así:

 void swap(char* str, int i, int j) { char temp = str[i]; str[i] = str[j]; str[j] = temp; } void permute(char *string, int start, int end) { if(start == end) { printf("%s\n", string); return; } permute(string, start + 1, end); int i; for(i = start + 1; i < end; i++) { if(string[start] == string[i]) continue; swap(string, start, i); permute(string, start + 1, end); swap(string, start, i); } } 

Aquí hay una solución iterativa:

Primero ordena la matriz.

  • Encuentre el índice máximo ia [i + 1]. (si no existe tal índice, no quedan más permutaciones)

Encuentra el índice máximo j

Cambia a [i] y a [j].

Invierta a [i + 1] .. a [n-1] y vaya al paso *.

Para obtener la permutación que tienes que usar recussion y backtracking, puedes resolverla también a través de la fuerza bruta, pero se vuelve compleja

  void swap(int *x1,int *x2) { int x=*x1; *x1=*x2; *x2=x; } void per(int *arr,int st,int ls) { int i=0; if(st==ls) { int k; for(k=0;k