algorithm - repeticion - Algoritmo para generar todas las permutaciones posibles de una lista?
permutation python (30)
Digamos que tengo una lista de n elementos, ¡sé que hay n! posibles formas de ordenar estos elementos. ¿Qué es un algoritmo para generar todos los ordenamientos posibles de esta lista? Ejemplo, tengo la lista [a, b, c]. El algoritmo devolvería [[a, b, c], [a, c, b,], [b, a, c], [b, c, a], [c, a, b], [c, b , un]].
Estoy leyendo esto aquí http://en.wikipedia.org/wiki/Permutation#Algorithms_to_generate_permutations
Pero Wikipedia nunca ha sido buena para explicar. No entiendo mucho de eso.
Aquí está el código en Python para imprimir todas las permutaciones posibles de una lista:
def next_perm(arr):
# Find non-increasing suffix
i = len(arr) - 1
while i > 0 and arr[i - 1] >= arr[i]:
i -= 1
if i <= 0:
return False
# Find successor to pivot
j = len(arr) - 1
while arr[j] <= arr[i - 1]:
j -= 1
arr[i - 1], arr[j] = arr[j], arr[i - 1]
# Reverse suffix
arr[i : ] = arr[len(arr) - 1 : i - 1 : -1]
print arr
return True
def all_perm(arr):
a = next_perm(arr)
while a:
a = next_perm(arr)
arr = raw_input()
arr.split('' '')
arr = map(int, arr)
arr.sort()
print arr
all_perm(arr)
He usado un algoritmo de orden lexicográfico para obtener todas las permutaciones posibles, pero un algoritmo recursivo es más eficiente. Puede encontrar el código para el algoritmo recursivo aquí: permutaciones de recursión de Python
Aquí hay un algoritmo en Python que funciona en su lugar en una matriz:
def permute(xs, low=0):
if low + 1 >= len(xs):
yield xs
else:
for p in permute(xs, low + 1):
yield p
for i in range(low + 1, len(xs)):
xs[low], xs[i] = xs[i], xs[low]
for p in permute(xs, low + 1):
yield p
xs[low], xs[i] = xs[i], xs[low]
for p in permute([1, 2, 3, 4]):
print p
Puede probar el código aquí: http://repl.it/J9v
Aquí hay un algoritmo en R, en caso de que alguien necesite evitar cargar bibliotecas adicionales como tenía que hacerlo.
permutations <- function(n){
if(n==1){
return(matrix(1))
} else {
sp <- permutations(n-1)
p <- nrow(sp)
A <- matrix(nrow=n*p,ncol=n)
for(i in 1:n){
A[(i-1)*p+1:p,] <- cbind(i,sp+(sp>=i))
}
return(A)
}
}
Ejemplo de uso:
> matrix(letters[permutations(3)],ncol=3)
[,1] [,2] [,3]
[1,] "a" "b" "c"
[2,] "a" "c" "b"
[3,] "b" "a" "c"
[4,] "b" "c" "a"
[5,] "c" "a" "b"
[6,] "c" "b" "a"
Aquí hay un método Ruby de juguete que funciona como #permutation.to_a que podría ser más legible para los locos. Es hella lenta, pero también 5 líneas.
def permute(ary)
return [ary] if ary.size <= 1
ary.collect_concat.with_index do |e, i|
rest = ary.dup.tap {|a| a.delete_at(i) }
permute(rest).collect {|a| a.unshift(e) }
end
end
Aquí hay una implementación para ColdFusion (requiere CF10 debido al argumento de combinación para ArrayAppend ()):
public array function permutateArray(arr){
if (not isArray(arguments.arr) ) {
return [''The ARR argument passed to the permutateArray function is not of type array.''];
}
var len = arrayLen(arguments.arr);
var perms = [];
var rest = [];
var restPerms = [];
var rpLen = 0;
var next = [];
//for one or less item there is only one permutation
if (len <= 1) {
return arguments.arr;
}
for (var i=1; i <= len; i++) {
// copy the original array so as not to change it and then remove the picked (current) element
rest = arraySlice(arguments.arr, 1);
arrayDeleteAt(rest, i);
// recursively get the permutation of the rest of the elements
restPerms = permutateArray(rest);
rpLen = arrayLen(restPerms);
// Now concat each permutation to the current (picked) array, and append the concatenated array to the end result
for (var j=1; j <= rpLen; j++) {
// for each array returned, we need to make a fresh copy of the picked(current) element array so as to not change the original array
next = arraySlice(arguments.arr, i, 1);
arrayAppend(next, restPerms[j], true);
arrayAppend(perms, next);
}
}
return perms;
}
Basado en la solución js de KhanSharp anterior.
Aquí hay una solución recursiva en PHP. La publicación de WhirlWind describe con precisión la lógica. Vale la pena mencionar que generar todas las permutaciones se ejecuta en tiempo factorial, por lo que podría ser una buena idea usar un enfoque iterativo en su lugar.
public function permute($sofar, $input){
for($i=0; $i < strlen($input); $i++){
$diff = strDiff($input,$input[$i]);
$next = $sofar.$input[$i]; //next contains a permutation, save it
$this->permute($next, $diff);
}
}
La función strDiff toma dos cadenas, s1 y s2 , y devuelve una nueva cadena con todo en s1 sin elementos en s2 (duplica la materia). Entonces, strDiff(''finish'',''i'') => ''fnish'' (la segunda ''i'' no se elimina).
Aquí ya hay muchas buenas soluciones, pero me gustaría compartir cómo resolví este problema yo solo y espero que esto pueda ser útil para alguien a quien también le gustaría obtener su propia solución.
Después de reflexionar sobre el problema, he llegado a dos conclusiones:
- Para la lista
Ldel tamañon, habrá la misma cantidad de soluciones comenzando con L 1 , L 2 ... L n elementos de la lista. Como en total hayn!permutaciones de la lista de tamañon, obtenemosn! / n = (n-1)!n! / n = (n-1)!permutaciones en cada grupo. - La lista de 2 elementos tiene solo 2 permutaciones =>
[a,b]y[b,a].
Usando estas dos ideas simples, he derivado el siguiente algoritmo:
permute array
if array is of size 2
return first and second element as new array
return second and first element as new array
else
for each element in array
new subarray = array with excluded element
return element + permute subarray
Aquí es cómo lo implementé en C #:
public IEnumerable<List<T>> Permutate<T>(List<T> input)
{
if (input.Count == 2) // this are permutations of array of size 2
{
yield return new List<T>(input);
yield return new List<T> {input[1], input[0]};
}
else
{
foreach(T elem in input) // going through array
{
var rlist = new List<T>(input); // creating subarray = array
rlist.Remove(elem); // removing element
foreach(List<T> retlist in Permutate(rlist))
{
retlist.Insert(0,elem); // inserting the element at pos 0
yield return retlist;
}
}
}
}
Básicamente, para cada elemento de izquierda a derecha, se generan todas las permutaciones de los elementos restantes (y cada uno se agrega con los elementos actuales). Esto se puede hacer recursivamente (o iterativamente si le gusta el dolor) hasta que se alcance el último elemento, en cuyo punto solo hay un orden posible.
Entonces con la lista [1,2,3,4] se generan todas las permutaciones que comienzan con 1, luego todas las permutaciones que comienzan con 2, luego 3 y luego 4.
Esto efectivamente reduce el problema de encontrar permutaciones de una lista de cuatro elementos a una lista de tres elementos. Después de reducir a 2 y luego a 1 lista de artículos, se encontrarán todos.
Ejemplo que muestra las permutaciones del proceso usando 3 bolas de colores:
(de https://en.wikipedia.org/wiki/Permutation#/media/File:Permutations_RGB.svg - https://commons.wikimedia.org/wiki/File:Permutations_RGB.svg )
Como dijo WhirlWind, comienzas por el principio.
Cambia el cursor con cada valor restante, incluido el cursor en sí, estas son todas las instancias nuevas (utilicé un int[] y array.clone() en el ejemplo).
Luego realice permutaciones en todas estas listas diferentes, asegurándose de que el cursor esté uno a la derecha.
Cuando ya no quedan más valores (el cursor está al final), imprima la lista. Esta es la condición de parada.
public void permutate(int[] list, int pointer) {
if (pointer == list.length) {
//stop-condition: print or process number
return;
}
for (int i = pointer; i < list.length; i++) {
int[] permutation = (int[])list.clone();.
permutation[pointer] = list[i];
permutation[i] = list[pointer];
permutate(permutation, pointer + 1);
}
}
En Scala
def permutazione(n: List[Int]): List[List[Int]] = permutationeAcc(n, Nil)
def permutationeAcc(n: List[Int], acc: List[Int]): List[List[Int]] = {
var result: List[List[Int]] = Nil
for (i ← n if (!(acc contains (i))))
if (acc.size == n.size-1)
result = (i :: acc) :: result
else
result = result ::: permutationeAcc(n, i :: acc)
result
}
En la siguiente solución Java, aprovechamos el hecho de que las cadenas son inmutables para evitar clonar el conjunto de resultados en cada iteración.
La entrada será una Cadena, diga "abc", y la salida serán todas las permutaciones posibles:
abc
acb
bac
bca
cba
cab
Código:
public static void permute(String s) {
permute(s, 0);
}
private static void permute(String str, int left){
if(left == str.length()-1) {
System.out.println(str);
} else {
for(int i = left; i < str.length(); i++) {
String s = swap(str, left, i);
permute(s, left+1);
}
}
}
private static String swap(String s, int left, int right) {
if (left == right)
return s;
String result = s.substring(0, left);
result += s.substring(right, right+1);
result += s.substring(left+1, right);
result += s.substring(left, left+1);
result += s.substring(right+1);
return result;
}
El mismo enfoque se puede aplicar a las matrices (en lugar de una cadena):
public static void main(String[] args) {
int[] abc = {1,2,3};
permute(abc, 0);
}
public static void permute(int[] arr, int index) {
if (index == arr.length) {
System.out.println(Arrays.toString(arr));
} else {
for (int i = index; i < arr.length; i++) {
int[] permutation = arr.clone();
permutation[index] = arr[i];
permutation[i] = arr[index];
permute(permutation, index + 1);
}
}
}
Es mi solución en Java:
public class CombinatorialUtils {
public static void main(String[] args) {
List<String> alphabet = new ArrayList<>();
alphabet.add("1");
alphabet.add("2");
alphabet.add("3");
alphabet.add("4");
for (List<String> strings : permutations(alphabet)) {
System.out.println(strings);
}
System.out.println("-----------");
for (List<String> strings : combinations(alphabet)) {
System.out.println(strings);
}
}
public static List<List<String>> combinations(List<String> alphabet) {
List<List<String>> permutations = permutations(alphabet);
List<List<String>> combinations = new ArrayList<>(permutations);
for (int i = alphabet.size(); i > 0; i--) {
final int n = i;
combinations.addAll(permutations.stream().map(strings -> strings.subList(0, n)).distinct().collect(Collectors.toList()));
}
return combinations;
}
public static <T> List<List<T>> permutations(List<T> alphabet) {
ArrayList<List<T>> permutations = new ArrayList<>();
if (alphabet.size() == 1) {
permutations.add(alphabet);
return permutations;
} else {
List<List<T>> subPerm = permutations(alphabet.subList(1, alphabet.size()));
T addedElem = alphabet.get(0);
for (int i = 0; i < alphabet.size(); i++) {
for (List<T> permutation : subPerm) {
int index = i;
permutations.add(new ArrayList<T>(permutation) {{
add(index, addedElem);
}});
}
}
}
return permutations;
}
}
Estaba pensando en escribir un código para obtener las permutaciones de cualquier entero dado de cualquier tamaño, es decir, proporcionando un número 4567 obtenemos todas las permutaciones posibles hasta 7654 ... Así que trabajé en él y encontré un algoritmo y finalmente lo implementé, Aquí es el código escrito en "c". Simplemente puede copiarlo y ejecutarlo en cualquier compilador de código abierto. Pero algunos defectos están esperando para ser eliminados. Por favor aprecio
Código:
#include <stdio.h>
#include <conio.h>
#include <malloc.h>
//PROTOTYPES
int fact(int); //For finding the factorial
void swap(int*,int*); //Swapping 2 given numbers
void sort(int*,int); //Sorting the list from the specified path
int imax(int*,int,int); //Finding the value of imax
int jsmall(int*,int); //Gives position of element greater than ith but smaller than rest (ahead of imax)
void perm(); //All the important tasks are done in this function
int n; //Global variable for input OR number of digits
void main()
{
int c=0;
printf("Enter the number : ");
scanf("%d",&c);
perm(c);
getch();
}
void perm(int c){
int *p; //Pointer for allocating separate memory to every single entered digit like arrays
int i, d;
int sum=0;
int j, k;
long f;
n = 0;
while(c != 0) //this one is for calculating the number of digits in the entered number
{
sum = (sum * 10) + (c % 10);
n++; //as i told at the start of loop
c = c / 10;
}
f = fact(n); //It gives the factorial value of any number
p = (int*) malloc(n*sizeof(int)); //Dynamically allocation of array of n elements
for(i=0; sum != 0 ; i++)
{
*(p+i) = sum % 10; //Giving values in dynamic array like 1234....n separately
sum = sum / 10;
}
sort(p,-1); //For sorting the dynamic array "p"
for(c=0 ; c<f/2 ; c++) { //Most important loop which prints 2 numbers per loop, so it goes upto 1/2 of fact(n)
for(k=0 ; k<n ; k++)
printf("%d",p[k]); //Loop for printing one of permutations
printf("/n");
i = d = 0;
i = imax(p,i,d); //provides the max i as per algo (i am restricted to this only)
j = i;
j = jsmall(p,j); //provides smallest i val as per algo
swap(&p[i],&p[j]);
for(k=0 ; k<n ; k++)
printf("%d",p[k]);
printf("/n");
i = d = 0;
i = imax(p,i,d);
j = i;
j = jsmall(p,j);
swap(&p[i],&p[j]);
sort(p,i);
}
free(p); //Deallocating memory
}
int fact (int a)
{
long f=1;
while(a!=0)
{
f = f*a;
a--;
}
return f;
}
void swap(int *p1,int *p2)
{
int temp;
temp = *p1;
*p1 = *p2;
*p2 = temp;
return;
}
void sort(int*p,int t)
{
int i,temp,j;
for(i=t+1 ; i<n-1 ; i++)
{
for(j=i+1 ; j<n ; j++)
{
if(*(p+i) > *(p+j))
{
temp = *(p+i);
*(p+i) = *(p+j);
*(p+j) = temp;
}
}
}
}
int imax(int *p, int i , int d)
{
while(i<n-1 && d<n-1)
{
if(*(p+d) < *(p+d+1))
{
i = d;
d++;
}
else
d++;
}
return i;
}
int jsmall(int *p, int j)
{
int i,small = 32767,k = j;
for (i=j+1 ; i<n ; i++)
{
if (p[i]<small && p[i]>p[k])
{
small = p[i];
j = i;
}
}
return j;
}
Este es un código recursivo para Java, la idea es tener un prefijo que agregue el resto de los caracteres:
public static void permutation(String str) {
permutation("", str);
}
private static void permutation(String prefix, String str) {
int n = str.length();
if (n == 0) System.out.println(prefix);
else {
for (int i = 0; i < n; i++)
permutation(prefix + str.charAt(i), str);
}
}
Ejemplo:
Entrada = "ABC"; Salida:
ABC ACB BAC BCA CAB CBA
He escrito esta solución recursiva en ANSI C. Cada ejecución de la función Permutate proporciona una permutación diferente hasta que se completen todas. Las variables globales también se pueden usar para variables de hecho y recuento.
#include <stdio.h>
#define SIZE 4
void Rotate(int vec[], int size)
{
int i, j, first;
first = vec[0];
for(j = 0, i = 1; i < size; i++, j++)
{
vec[j] = vec[i];
}
vec[j] = first;
}
int Permutate(int *start, int size, int *count)
{
static int fact;
if(size > 1)
{
if(Permutate(start + 1, size - 1, count))
{
Rotate(start, size);
}
fact *= size;
}
else
{
(*count)++;
fact = 1;
}
return !(*count % fact);
}
void Show(int vec[], int size)
{
int i;
printf("%d", vec[0]);
for(i = 1; i < size; i++)
{
printf(" %d", vec[i]);
}
putchar(''/n'');
}
int main()
{
int vec[] = { 1, 2, 3, 4, 5, 6 }; /* Only the first SIZE items will be permutated */
int count = 0;
do
{
Show(vec, SIZE);
} while(!Permutate(vec, SIZE, &count));
putchar(''/n'');
Show(vec, SIZE);
printf("/nCount: %d/n/n", count);
return 0;
}
La respuesta de Wikipedia para el "orden lexicográfico" me parece perfectamente explícita en el estilo del libro de cocina. ¡Cita un origen del siglo 14 para el algoritmo!
Acabo de escribir una implementación rápida en Java del algoritmo de Wikipedia como un control y no fue un problema. Pero lo que tienes en tu Q como ejemplo NO es "enumera todas las permutaciones", sino "una LISTA de todas las permutaciones", por lo que wikipedia no será de mucha ayuda para ti. Necesita un lenguaje en el que se puedan construir listas de permutaciones. Y créanme, las listas de unos miles de millones de largo no suelen manejarse en idiomas imperativos. Realmente desea un lenguaje de programación funcional no estricto, en el que las listas sean un objeto de primera clase, para sacar cosas sin acercar la máquina a la muerte por calor del Universo.
Eso es fácil. En Haskell estándar o en cualquier lenguaje FP moderno:
-- perms of a list
perms :: [a] -> [ [a] ]
perms (a:as) = [bs ++ a:cs | perm <- perms as, (bs,cs) <- splits perm]
perms [] = [ [] ]
y
-- ways of splitting a list into two parts
splits :: [a] -> [ ([a],[a]) ]
splits [] = [ ([],[]) ]
splits (a:as) = ([],a:as) : [(a:bs,cs) | (bs,cs) <- splits as]
No se puede hablar realmente de resolver un problema de permultación en recursión sin publicar una implementación en un (dialecto de) lenguaje que fue pionero en la idea . Entonces, para completar, esta es una de las formas en que se puede hacer en Scheme.
(define (permof wd)
(cond ((null? wd) ''())
((null? (cdr wd)) (list wd))
(else
(let splice ([l ''()] [m (car wd)] [r (cdr wd)])
(append
(map (lambda (x) (cons m x)) (permof (append l r)))
(if (null? r)
''()
(splice (cons m l) (car r) (cdr r))))))))
llamando (permof (list "foo" "bar" "baz")) obtendremos:
''(("foo" "bar" "baz")
("foo" "baz" "bar")
("bar" "foo" "baz")
("bar" "baz" "foo")
("baz" "bar" "foo")
("baz" "foo" "bar"))
No entraré en los detalles del algoritmo porque ya se explicó lo suficiente en otras publicaciones. La idea es la misma
Sin embargo, los problemas recursivos tienden a ser mucho más difíciles de modelar y pensar en medios destructivos como Python, C y Java, mientras que en Lisp o ML se puede expresar de forma concisa.
Otro en Python, no está en su lugar como @cdiggins, pero creo que es más fácil de entender
def permute(num):
if len(num) == 2:
# get the permutations of the last 2 numbers by swapping them
yield num
num[0], num[1] = num[1], num[0]
yield num
else:
for i in range(0, len(num)):
# fix the first number and get the permutations of the rest of numbers
for perm in permute(num[0:i] + num[i+1:len(num)]):
yield [num[i]] + perm
for p in permute([1, 2, 3, 4]):
print p
Para ser completo, C ++
#include <iostream>
#include <algorithm>
#include <string>
std::string theSeq = "abc";
do
{
std::cout << theSeq << endl;
}
while (std::next_permutation(theSeq.begin(), theSeq.end()));
...
abc
acb
bac
bca
cab
cba
Recursivo siempre requiere un esfuerzo mental para mantenerse. Y para números grandes, factorial es muy grande y el desbordamiento de la pila fácilmente será un problema.
Para números pequeños (3 o 4, que se encuentran principalmente), los bucles múltiples son bastante simples y directos. Es lamentable que las respuestas con bucles no hayan sido votadas.
Comencemos con la enumeración (en lugar de la permutación). Simplemente lea el código como código de pseudoperl.
$foreach $i1 in @list
$foreach $i2 in @list
$foreach $i3 in @list
print "$i1, $i2, $i3/n"
La enumeración se encuentra con más frecuencia que la permutación, pero si se necesita permutación, simplemente agregue las condiciones:
$foreach $i1 in @list
$foreach $i2 in @list
$if $i2==$i1
next
$foreach $i3 in @list
$if $i3==$i1 or $i3==$i2
next
print "$i1, $i2, $i3/n"
Ahora, si realmente necesita un método general para listas grandes, podemos usar el método radix. Primero, considere el problema de enumeración:
$n=@list
my @radix
$for $i=0:$n
$radix[$i]=0
$while 1
my @temp
$for $i=0:$n
push @temp, $list[$radix[$i]]
print join(", ", @temp), "/n"
$call radix_increment
subcode: radix_increment
$i=0
$while 1
$radix[$i]++
$if $radix[$i]==$n
$radix[$i]=0
$i++
$else
last
$if $i>=$n
last
El incremento de Radix consiste esencialmente en contar números (en la base del número de elementos de la lista).
Ahora si necesita permutaion, simplemente agregue las verificaciones dentro del ciclo:
subcode: check_permutation
my @check
my $flag_dup=0
$for $i=0:$n
$check[$radix[$i]]++
$if $check[$radix[$i]]>1
$flag_dup=1
last
$if $flag_dup
next
Editar: El código anterior debería funcionar, pero para la permutación, radix_increment podría ser un desperdicio. Entonces, si el tiempo es una preocupación práctica, tenemos que cambiar radix_increment en permute_inc:
subcode: permute_init
$for $i=0:$n
$radix[$i]=$i
subcode: permute_inc
$max=-1
$for $i=$n:0
$if $max<$radix[$i]
$max=$radix[$i]
$else
$for $j=$n:0
$if $radix[$j]>$radix[$i]
$call swap, $radix[$i], $radix[$j]
break
$j=$i+1
$k=$n-1
$while $j<$k
$call swap, $radix[$j], $radix[$k]
$j++
$k--
break
$if $i<0
break
Por supuesto, ahora que este código es lógicamente más complejo, me iré para el ejercicio del lector.
Sé que es un tema muy antiguo e incluso fuera de lugar en el de hoy, pero aún así quería contribuir con una respuesta de javascript amigable por la sencilla razón de que se ejecuta en su navegador.
También agregué el punto de corte de la directiva de debugger para que pueda recorrer el código (se requiere Chrome) para ver cómo funciona este algoritmo. Abra su consola de desarrollo en Chrome ( F12 en Windows o CMD + OPTION + I en Mac) y luego haga clic en "Ejecutar fragmento de código". Esto implementa el mismo algoritmo exacto que @WhirlWind presentó en su respuesta.
Su navegador debe detener la ejecución en la directiva de debugger . Use F8 para continuar la ejecución del código.
¡Pase el código y vea cómo funciona!
function permute(rest, prefix = []) {
if (rest.length === 0) {
return [prefix];
}
return (rest
.map((x, index) => {
const oldRest = rest;
const oldPrefix = prefix;
// the `...` destructures the array into single values flattening it
const newRest = [...rest.slice(0, index), ...rest.slice(index + 1)];
const newPrefix = [...prefix, x];
debugger;
const result = permute(newRest, newPrefix);
return result;
})
// this step flattens the array of arrays returned by calling permute
.reduce((flattened, arr) => [...flattened, ...arr], [])
);
}
console.log(permute([1, 2, 3]));
Si alguien se pregunta cómo hacerlo en permutación en javascript.
Idea / pseudocódigo
- elige un elemento a la vez
- permute el resto del elemento y luego agregue el elemento elegido a la totalidad de la permutación
por ejemplo. ''a'' + permute (bc). permute de bc sería bc & cb. Ahora agrega que estos dos darán abc, acb. de manera similar, elegir b + permute (ac) proporcionará bac, bca ... y continuará.
ahora mira el código
function permutations(arr){
var len = arr.length,
perms = [],
rest,
picked,
restPerms,
next;
//for one or less item there is only one permutation
if (len <= 1)
return [arr];
for (var i=0; i<len; i++)
{
//copy original array to avoid changing it while picking elements
rest = Object.create(arr);
//splice removed element change array original array(copied array)
//[1,2,3,4].splice(2,1) will return [3] and remaining array = [1,2,4]
picked = rest.splice(i, 1);
//get the permutation of the rest of the elements
restPerms = permutations(rest);
// Now concat like a+permute(bc) for each
for (var j=0; j<restPerms.length; j++)
{
next = picked.concat(restPerms[j]);
perms.push(next);
}
}
return perms;
}
Tómate tu tiempo para entender esto. Obtuve este código de ( preocupación en JavaScript )
Solución Bourne shell - en un total de cuatro líneas (sin prueba para ningún caso de param):
test $# -eq 1 && echo "$1" && exit
for i in $*; do
$0 `echo "$*" | sed -e "s/$i//"` | sed -e "s/^/$i /"
done
Versión de Java
/**
* @param uniqueList
* @param permutationSize
* @param permutation
* @param only Only show the permutation of permutationSize,
* else show all permutation of less than or equal to permutationSize.
*/
public static void my_permutationOf(List<Integer> uniqueList, int permutationSize, List<Integer> permutation, boolean only) {
if (permutation == null) {
assert 0 < permutationSize && permutationSize <= uniqueList.size();
permutation = new ArrayList<>(permutationSize);
if (!only) {
System.out.println(Arrays.toString(permutation.toArray()));
}
}
for (int i : uniqueList) {
if (permutation.contains(i)) {
continue;
}
permutation.add(i);
if (!only) {
System.out.println(Arrays.toString(permutation.toArray()));
} else if (permutation.size() == permutationSize) {
System.out.println(Arrays.toString(permutation.toArray()));
}
if (permutation.size() < permutationSize) {
my_permutationOf(uniqueList, permutationSize, permutation, only);
}
permutation.remove(permutation.size() - 1);
}
}
P.ej
public static void main(String[] args) throws Exception {
my_permutationOf(new ArrayList<Integer>() {
{
add(1);
add(2);
add(3);
}
}, 3, null, true);
}
salida:
[1, 2, 3]
[1, 3, 2]
[2, 1, 3]
[2, 3, 1]
[3, 1, 2]
[3, 2, 1]
en PHP
$set=array(''A'',''B'',''C'',''D'');
function permutate($set) {
$b=array();
foreach($set as $key=>$value) {
if(count($set)==1) {
$b[]=$set[$key];
}
else {
$subset=$set;
unset($subset[$key]);
$x=permutate($subset);
foreach($x as $key1=>$value1) {
$b[]=$value.'' ''.$value1;
}
}
}
return $b;
}
$x=permutate($set);
var_export($x);
esta es una versión java para permutación
public class Permutation {
static void permute(String str) {
permute(str.toCharArray(), 0, str.length());
}
static void permute(char [] str, int low, int high) {
if (low == high) {
System.out.println(str);
return;
}
for (int i=low; i<high; i++) {
swap(str, i, low);
permute(str, low+1, high);
swap(str, low, i);
}
}
static void swap(char [] array, int i, int j) {
char t = array[i];
array[i] = array[j];
array[j] = t;
}
}
// C program to print all permutations with duplicates allowed
#include <stdio.h>
#include <string.h>
/* Function to swap values at two pointers */
void swap(char *x, char *y)
{
char temp;
temp = *x;
*x = *y;
*y = temp;
}
/* Function to print permutations of string
This function takes three parameters:
1. String
2. Starting index of the string
3. Ending index of the string. */
void permute(char *a, int l, int r)
{
int i;
if (l == r)
printf("%s/n", a);
else
{
for (i = l; i <= r; i++)
{
swap((a+l), (a+i));
permute(a, l+1, r);
swap((a+l), (a+i)); //backtrack
}
}
}
/* Driver program to test above functions */
int main()
{
char str[] = "ABC";
int n = strlen(str);
permute(str, 0, n-1);
return 0;
}
Referencia: Geeksforgeeks.org
#!/usr/bin/env python
import time
def permutations(sequence):
# print sequence
unit = [1, 2, 1, 2, 1]
if len(sequence) >= 4:
for i in range(4, (len(sequence) + 1)):
unit = ((unit + [i - 1]) * i)[:-1]
# print unit
for j in unit:
temp = sequence[j]
sequence[j] = sequence[0]
sequence[0] = temp
yield sequence
else:
print ''You can use PEN and PAPER''
# s = [1,2,3,4,5,6,7,8,9,10]
s = [x for x in ''PYTHON'']
print s
z = permutations(s)
try:
while True:
# time.sleep(0.0001)
print next(z)
except StopIteration:
print ''Done''
[''P'', ''Y'', ''T'', ''H'', ''O'', ''N'']
[''Y'', ''P'', ''T'', ''H'', ''O'', ''N'']
[''T'', ''P'', ''Y'', ''H'', ''O'', ''N'']
[''P'', ''T'', ''Y'', ''H'', ''O'', ''N'']
[''Y'', ''T'', ''P'', ''H'', ''O'', ''N'']
[''T'', ''Y'', ''P'', ''H'', ''O'', ''N'']
[''H'', ''Y'', ''P'', ''T'', ''O'', ''N'']
[''Y'', ''H'', ''P'', ''T'', ''O'', ''N'']
[''P'', ''H'', ''Y'', ''T'', ''O'', ''N'']
[''H'', ''P'', ''Y'', ''T'', ''O'', ''N'']
[''Y'', ''P'', ''H'', ''T'', ''O'', ''N'']
[''P'', ''Y'', ''H'', ''T'', ''O'', ''N'']
[''T'', ''Y'', ''H'', ''P'', ''O'', ''N'']
[''Y'', ''T'', ''H'', ''P'', ''O'', ''N'']
[''H'', ''T'', ''Y'', ''P'', ''O'', ''N'']
[''T'', ''H'', ''Y'', ''P'', ''O'', ''N'']
[''Y'', ''H'', ''T'', ''P'', ''O'', ''N'']
[''H'', ''Y'', ''T'', ''P'', ''O'', ''N'']
[''P'', ''Y'', ''T'', ''H'', ''O'', ''N'']
.
.
.
[''Y'', ''T'', ''N'', ''H'', ''O'', ''P'']
[''N'', ''T'', ''Y'', ''H'', ''O'', ''P'']
[''T'', ''N'', ''Y'', ''H'', ''O'', ''P'']
[''Y'', ''N'', ''T'', ''H'', ''O'', ''P'']
[''N'', ''Y'', ''T'', ''H'', ''O'', ''P'']
public class PermutationGenerator
{
private LinkedList<List<int>> _permutationsList;
public void FindPermutations(List<int> list, int permutationLength)
{
_permutationsList = new LinkedList<List<int>>();
foreach(var value in list)
{
CreatePermutations(value, permutationLength);
}
}
private void CreatePermutations(int value, int permutationLength)
{
var node = _permutationsList.First;
var last = _permutationsList.Last;
while (node != null)
{
if (node.Value.Count < permutationLength)
{
GeneratePermutations(node.Value, value, permutationLength);
}
if (node == last)
{
break;
}
node = node.Next;
}
List<int> permutation = new List<int>();
permutation.Add(value);
_permutationsList.AddLast(permutation);
}
private void GeneratePermutations(List<int> permutation, int value, int permutationLength)
{
if (permutation.Count < permutationLength)
{
List<int> copyOfInitialPermutation = new List<int>(permutation);
copyOfInitialPermutation.Add(value);
_permutationsList.AddLast(copyOfInitialPermutation);
List<int> copyOfPermutation = new List<int>();
copyOfPermutation.AddRange(copyOfInitialPermutation);
int lastIndex = copyOfInitialPermutation.Count - 1;
for (int i = lastIndex;i > 0;i--)
{
int temp = copyOfPermutation[i - 1];
copyOfPermutation[i - 1] = copyOfPermutation[i];
copyOfPermutation[i] = temp;
List<int> perm = new List<int>();
perm.AddRange(copyOfPermutation);
_permutationsList.AddLast(perm);
}
}
}
public void PrintPermutations(int permutationLength)
{
int count = _permutationsList.Where(perm => perm.Count() == permutationLength).Count();
Console.WriteLine("The number of permutations is " + count);
}
}
void permutate(char[] x, int i, int n){
x=x.clone();
if (i==n){
System.out.print(x);
System.out.print(" ");
counter++;}
else
{
for (int j=i; j<=n;j++){
// System.out.print(temp); System.out.print(" "); //Debugger
swap (x,i,j);
// System.out.print(temp); System.out.print(" "+"i="+i+" j="+j+"/n");// Debugger
permutate(x,i+1,n);
// swap (temp,i,j);
}
}
}
void swap (char[] x, int a, int b){
char temp = x[a];
x[a]=x[b];
x[b]=temp;
}
Creé este. basado en la investigación también permutada (qwe, 0, qwe.length-1); Para que lo sepas, puedes hacerlo con o sin retroceder