Pasos de permutación

10

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!

Billyoyo
fuente
¿Podemos usar la aleatoriedad?
Zgarb
¿Te refieres a hacer una gran cantidad de intercambios aleatorios hasta lograr todas las permutaciones? Sí, pero debe asegurarse de que todas las permutaciones se hayan impreso
Billyoyo
3
Bienvenido a PPCG! Bonito primer desafío. Sugeriría editar el ejemplo para que los elementos no se confundan con los índices, como usar set (3, 1, 4)o algo así: leerlo la primera vez que estaba muy confundido porque el primer intercambio 0,1intercambió los elementos 0,1pero también los índices 0,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.
AdmBorkBork
2
@TimmyD gracias por la sugerencia, he cambiado el ejemplo. Vi el enlace al sandbox justo después de publicar esto, ¡publicaré allí primero de ahora en adelante!
Billyoyo
1
El algoritmo Steinhaus – Johnson – Trotter genera la secuencia mínima necesaria.
Neil

Respuestas:

3

Mathematica, 102 bytes

<<Combinatorica`
Riffle[#,BlockMap[Pick[#[[1]],#!=0&/@({1,-1}.#)]&,#,2,1]]&@*MinimumChangePermutations

Ejemplos

// Columna para un resultado más claro

%[{1,3,5}]//Column
(*
{1,3,5}
{1,3}
{3,1,5}
{3,5}
{5,1,3}
{5,1}
{1,5,3}
{1,3}
{3,5,1}
{3,5}
{5,3,1}
*)
njpipeorgan
fuente
3

Java, 449 426 bytes

import java.util.*;interface P{static Set s=new HashSet();static void main(String[]a){o(Arrays.toString(a));while(s.size()<n(a.length)){p(a);o(Arrays.toString(a));}}static<T>void o(T z){System.out.println(z);s.add(z);}static int n(int x){return x==1?1:x*n(x-1);}static void p(String[]a){Random r=new Random();int l=a.length,j=r.nextInt(l),i=r.nextInt(l);String t=a[j];a[j]=a[i];a[i]=t;System.out.println("("+a[j]+","+t+")");}}

Enfoque 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

  • Seguí las sugerencias de Kevin Cruijssen para jugar al golf un poco más.

Sin golf:

import java.util.*;

interface P {

    static Set<String> s = new HashSet<>();

    static void main(String[] a) {
        // prints the original input
        o(Arrays.toString(a));
        while (s.size() < n(a.length)) {
            p(a);
            // prints the array after the swap
            o(Arrays.toString(a));
        }
    }

    static void o(String z) {
        System.out.println(z);
        // adds the string representation of the array to the HashSet
        s.add(z);
    }

    // method that calculates n!
    static int n(int x) {
        if (x == 1) {
            return 1;
        }
        return x * n(x - 1);
    }

    // makes a random swap and prints what the swap is
    static void p(String[] a) {
        Random r = new Random();
        int l = a.length, j = r.nextInt(l), i = r.nextInt(l);
        String t = a[j];
        a[j] = a[i];
        a[i] = t;
        System.out.println("(" + a[j] + "," + t + ")");
    }
}

Uso:

$ javac P.java
$ java P 1 2 3
[1, 2, 3]
(2,1)
[2, 1, 3]
(1,1)
[2, 1, 3]
(2,2)
[2, 1, 3]
(3,1)
[2, 3, 1]
(3,1)
[2, 1, 3]
(1,2)
[1, 2, 3]
(1,1)
[1, 2, 3]
(3,2)
[1, 3, 2]
(2,3)
[1, 2, 3]
(3,1)
[3, 2, 1]
(3,1)
[1, 2, 3]
(3,3)
[1, 2, 3]
(1,2)
[2, 1, 3]
(1,3)
[2, 3, 1]
(1,2)
[1, 3, 2]
(3,1)
[3, 1, 2]

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

$ java P 'one' 'two'
[one, two]
(two,one)
[two, one]
Master_ex
fuente
¿Tiene una versión sin golf para que le demos un vistazo a su método?
Billyoyo
@Billyoyo: se agregó el código sin golf. Nada de lujos allí sin embargo :-)
Master_ex
Puedes jugar un poco al golf. No hay necesidad de advertencias fijos, por lo que puede eliminado las declaraciones que figuran: Set s=new HashSet();. Su código en el método npuede ser una sola declaración: static int n(int x){return x==1?1:x*n(x-1);}. Y se puede sustituir String zen su método ocon 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 .
Kevin Cruijssen
1

JavaScript (ES6), 186 bytes

f=
a=>{console.log(a);d=a.slice().fill(-1);s=[...d.keys()];for(i=l=a.length;i;)s[k=(j=s.indexOf(--i))+d[i]]<i?(console.log(a[s[j]=s[k]],a[s[k]=i]),console.log(s.map(n=>a[n])),i=l):d[i]*=-1}
;
<input id=i><input type=button value=Go! onclick=f(i.value.split`,`)>

Nota: No estoy seguro de cuán flexible es el formato de salida, puede ser que pueda hacer esto para 171 bytes:

a=>{console.log(a);d=a.slice().fill(-1);s=[...d.keys()];for(i=l=a.length;i;)s[k=(j=s.indexOf(--i))+d[i]]<i?console.log(a[s[j]=s[k]],a[s[k]=i],s.map(n=>a[n],i=l)):d[i]*=-1}

Funciona realizando el algoritmo Steinhaus – Johnson – Trotter en la matriz aleatoria de índices y traduciendo de nuevo a la matriz de entrada. Sin golf:

function steps(array) {
    console.log(array); // initial row
    var d = a.slice().fill(-1); // direction values
    var s = [...a.keys()]; // initial (identity) shuffle
    var l = a.length;
    for (var i = l; i; ) { // start by trying to move the last element
        var j = s.indexOf(--i);
        var k = j + d[i]; // proposed exchange
        if (s[k] < i) { // only exchange with lower index (within bounds)
            console.log(a[s[k]],a[i]); // show values being exchanged
            s[j] = s[k];
            s[k] = i; // do the exchange on the shuffle
            console.log(s.map(n=>a[n])); // show the shuffled array
            i = l; // start from the last element again
        } else {
            d[i] *= -1; // next time, try moving it the other way
        } // --i above causes previous element to be tried
    } // until no movable elements can be found
}
Neil
fuente
1

Ruby, 86 bytes

puts (2..(a=gets.scan(/\d+/).uniq).size).map{|i|a.permutation(i).map{|e|?(+e*", "+?)}}
cia_rana
fuente
1

Haskell - 135 bytes

p=permutations;f=filter
q(a:b:xs)=(\x->f(uncurry(/=)).zip x)a b:q(b:xs);q _=[]
l=head.f(all((==2).length).q).p.p
f=zip.l<*>map head.q.l

salida:

> f [3,1,5]
[([3,1,5],(3,1)),([1,3,5],(3,5)),([1,5,3],(1,5)),([5,1,3],(1,3)),([5,3,1],(5,3))]

Estoy usando la permutationsfunció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.

Alondra
fuente