Escriba una función que tome un conjunto de enteros e imprima cada permutación del conjunto, y el intercambio realizado entre cada paso
Entrada
un conjunto de enteros, por ejemplo (0, 1, 2)
Salida
la lista de permutaciones y swaps en el formato (conjunto) (intercambio) (conjunto) ...
Caso de prueba
Input:
(3, 1, 5)
Output:
(3, 1, 5)
(3, 1)
(1, 3, 5)
(3, 5)
(1, 5, 3)
(1, 3)
(3, 5, 1)
(3, 5)
(5, 3, 1)
(3, 1)
(5, 1, 3)
Reglas
- Puede formatear el conjunto de números como lo desee.
- Puedes hacer los intercambios en cualquier orden
- Puede repetir permutaciones e intercambios para obtener uno nuevo
- Su código no tiene que realizar realmente los intercambios, la salida solo debe mostrar qué intercambio se realizó entre su última salida y la actual
- Su código solo necesita funcionar para conjuntos con 2 o más elementos
- El conjunto que se le dará no tendrá elementos repetidos (por ejemplo, (0, 1, 1, 2) no es válido)
Este es el código de golf, ¡el código más corto gana!
code-golf
math
permutations
Billyoyo
fuente
fuente
(3, 1, 4)
o algo así: leerlo la primera vez que estaba muy confundido porque el primer intercambio0,1
intercambió los elementos0,1
pero también los índices0,1
, pero luego el siguiente el intercambio no siguió ese patrón. También lo señalaré al Sandbox donde puede publicar desafíos y obtener comentarios antes de publicarlos en el sitio principal.Respuestas:
Mathematica, 102 bytes
Ejemplos
// Columna para un resultado más claro
fuente
Java,
449426 bytesEnfoque de fuerza bruta. Sigue haciendo intercambios aleatorios hasta que se hayan producido todas las permutaciones posibles. Utiliza un conjunto de la representación de cadena de la matriz para verificar cuántos estados diferentes se han generado. Para n enteros diferentes hay n! = 1 * 2 * 3 * .. * n permutaciones distintas.
Actualizar
Sin golf:
Uso:
Como puede ver, hay muchos más intercambios que el mínimo necesario. Pero parece funcionar :-D
Como beneficio adicional, también funciona con cadenas, es decir
fuente
Set s=new HashSet();
. Su código en el métodon
puede ser una sola declaración:static int n(int x){return x==1?1:x*n(x-1);}
. Y se puede sustituirString z
en su métodoo
con un genérico en lugar:static<T>void o(T z){System.out.println(z);s.add(z);}
. Todo combinado se reduciría a 426 bytes .JavaScript (ES6), 186 bytes
Nota: No estoy seguro de cuán flexible es el formato de salida, puede ser que pueda hacer esto para 171 bytes:
Funciona realizando el algoritmo Steinhaus – Johnson – Trotter en la matriz aleatoria de índices y traduciendo de nuevo a la matriz de entrada. Sin golf:
fuente
Ruby, 86 bytes
fuente
Haskell - 135 bytes
salida:
Estoy usando la
permutations
función estándar , que no se basa en intercambios, por lo que estoy tomando las permutaciones de las permutaciones y encuentro una que resulta ser una cadena de intercambios.fuente