Etapas da permutação

10

Escreva uma função que pegue um conjunto de números inteiros e imprima todas as permutações do conjunto, e a troca seja realizada entre cada etapa

Entrada

um conjunto de números inteiros, por exemplo (0, 1, 2)

Resultado

a lista de permutações e swaps no formato (conjunto) (swap) (conjunto) ...

Caso de teste

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)

Regras

  • Você pode formatar o conjunto de números da maneira que desejar.
  • Você pode fazer as trocas em qualquer ordem
  • Você pode repetir permutações e swaps para obter um novo
  • Seu código não precisa executar os swaps, a saída precisa apenas mostrar qual troca foi feita entre sua última saída e a atual
  • Seu código precisa funcionar apenas para conjuntos com 2 ou mais elementos
  • O conjunto fornecido não terá elementos repetitivos (por exemplo, (0, 1, 1, 2) é inválido)

Isso é código-golfe, então o código mais curto vence!

Billyoyo
fonte
Podemos usar aleatoriedade?
Zgarb
Você quer dizer apenas fazer uma carga de trocas aleatórias até conseguir todas as permutações? Sim, mas você tem que ter certeza de que todas as permutações foram impressos
Billyoyo
3
Bem-vindo ao PPCG! Bom primeiro desafio. Sugiro editar o exemplo para que os elementos não se confundam com os índices, como use set (3, 1, 4)ou algo assim - lendo-o pela primeira vez, fiquei muito confuso porque a primeira troca 0,1trocou os elementos, 0,1mas também os índices 0,1, mas depois a próxima A troca não seguiu esse padrão. Também apontarei para o Sandbox, onde é possível postar desafios e obter feedback antes de publicá-los no site principal.
AdmBorkBork
2
@ TimmyD obrigado pela sugestão, mudei o exemplo. Eu vi o link para a caixa de areia logo depois que eu postei isso, eu vou postar lá primeiro a partir de agora!
Billyoyo
11
O algoritmo Steinhaus – Johnson – Trotter gera a sequência mínima necessária.
Neil

Respostas:

3

Mathematica, 102 bytes

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

Exemplos

// Coluna para um resultado mais 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
fonte
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+")");}}

Abordagem de força bruta. Ele continua fazendo trocas aleatórias até que todas as permutações possíveis tenham ocorrido. Ele usa um conjunto da representação de string da matriz para verificar quantos estados diferentes foram gerados. Para n números inteiros diferentes, existem n! = 1 * 2 * 3 * .. * n permutações distintas.

Atualizar

  • Seguiu as sugestões de Kevin Cruijssen para jogar um pouco mais.

Ungolfed:

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 você pode ver, existem muito mais swaps do que o mínimo necessário. Mas parece funcionar :-D

Como bônus, ele também funciona com strings, ou seja,

$ java P 'one' 'two'
[one, two]
(two,one)
[two, one]
Master_ex
fonte
você tem uma versão não-golfe para dar uma olhada no seu método usando?
Billyoyo
@ Billyoyo: Adicionado o código não golfe. Fantasia nada lá no entanto :-)
Master_ex
Você pode jogar um pouco de golfe. Não há necessidade de avisos de correção, para que possa removido as declarações Set: Set s=new HashSet();. Seu código no método npode ser um único retorno: static int n(int x){return x==1?1:x*n(x-1);}. E você pode substituir String zem seu método ocom um genérico em vez disso: static<T>void o(T z){System.out.println(z);s.add(z);}. Tudo combinado reduziria 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: Não tenho certeza de quão flexível é o formato de saída; posso fazer isso por 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 executando o algoritmo Steinhaus – Johnson – Trotter na matriz aleatória de índices e convertendo de volta para a matriz de entrada. Ungolfed:

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
fonte
1

Ruby, 86 bytes

puts (2..(a=gets.scan(/\d+/).uniq).size).map{|i|a.permutation(i).map{|e|?(+e*", "+?)}}
cia_rana
fonte
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

resultado:

> 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))]

Estou usando a permutationsfunção padrão , que não é baseada em swaps, por isso estou fazendo as permutações das permutações e encontrando uma que por acaso é uma cadeia de swaps.

BlackCap
fonte