Kroki permutacji

10

Napisz funkcję, która pobiera zestaw liczb całkowitych i wypisuje każdą permutację zestawu, a zamiana jest wykonywana pomiędzy każdym krokiem

Wejście

zestaw liczb całkowitych, na przykład (0, 1, 2)

Wynik

lista permutacji i zamian w formacie (zestaw) (zamiana) (zestaw) ...

Przypadek testowy

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)

Zasady

  • Możesz sformatować zestaw liczb w dowolny sposób.
  • Możesz wykonywać swapy w dowolnej kolejności
  • Możesz powtarzać permutacje i zamiany, aby uzyskać nową
  • Twój kod nie musi tak naprawdę wykonywać swapów, dane wyjściowe muszą tylko pokazywać, co zostało zrobione między ostatnim a ostatnim wyjściem
  • Twój kod musi działać tylko w przypadku zestawów zawierających 2 lub więcej elementów
  • Podany zestaw nie będzie zawierał powtarzających się elementów (np. (0, 1, 1, 2) jest nieprawidłowy)

To jest golf golfowy, więc wygrywa najkrótszy kod!

Billyoyo
źródło
Czy możemy użyć losowości?
Zgarb
Masz na myśli po prostu ładowanie losowych swapów, dopóki nie osiągniesz wszystkich permutacji? Tak, ale musisz mieć pewność, że wszystkie permutacje zostały wydrukowane
Billyoyo
3
Witamy w PPCG! Ładne pierwsze wyzwanie. Sugerowałbym edytowanie przykładu, aby elementy nie zostały pomylone z indeksami, np. Użyj zestawu (3, 1, 4)lub tak - czytając go za pierwszym razem byłem bardzo zdezorientowany, ponieważ pierwsza zamiana 0,1zamieniła elementy, 0,1ale także indeksy 0,1, ale potem następna swap nie postępował zgodnie z tym wzorem. Wskażę ci także piaskownicę, w której możesz publikować wyzwania i uzyskiwać opinie przed opublikowaniem ich na głównej stronie.
AdmBorkBork
2
@ TimmyD dzięki za sugestię, zmieniłem przykład. Widziałem link do piaskownicy zaraz po tym, jak to opublikowałem, odtąd będę tam pierwszy!
Billyoyo
1
Steinhaus-Johnsona Trotter algorytm generuje minimalnej niezbędnej sekwencji.
Neil

Odpowiedzi:

3

Mathematica, 102 bajty

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

Przykłady

// Kolumna dla wyraźniejszego wyniku

%[{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
źródło
3

Java, 449 426 bajtów

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+")");}}

Podejście brutalnej siły. Wykonuje losowe zamiany, dopóki nie zostaną wykonane wszystkie możliwe permutacje. Używa zestawu reprezentacji ciągu tablicy, aby sprawdzić, ile różnych stanów zostało wygenerowanych. Dla n różnych liczb całkowitych jest n! = 1 * 2 * 3 * .. * n odrębne permutacje.

Aktualizacja

  • Postępowałem zgodnie z sugestiami Kevina Cruijssena, aby nieco bardziej zagrać w golfa.

Nie golfowany:

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 + ")");
    }
}

Stosowanie:

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

Jak widać, jest o wiele więcej swapów niż niezbędne minimum. Ale wydaje się, że działa :-D

Jako bonus działa również z łańcuchami, tj

$ java P 'one' 'two'
[one, two]
(two,one)
[two, one]
Master_ex
źródło
czy masz wersję bez gry w golfa, abyśmy mogli przyjrzeć się twojej metodzie?
Billyoyo
@Billyoyo: Dodano kod bez golfa. Nie ma tu jednak nic szczególnego :-)
Master_ex
Możesz trochę zagrać w golfa. Nie ma potrzeby ostrzeżeń naprawić, więc można usunięte zestaw deklaracji: Set s=new HashSet();. Twój kod w metodzie nmoże być pojedynczy zwrot: static int n(int x){return x==1?1:x*n(x-1);}. I można wymienić String zw sposób orodzajowy zamiast: static<T>void o(T z){System.out.println(z);s.add(z);}. Wszystko razem spadłoby do 426 bajtów .
Kevin Cruijssen
1

JavaScript (ES6), 186 bajtów

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`,`)>

Uwaga: Nie jestem pewien, jak elastyczny jest format wyjściowy, być może mógłbym to zrobić dla 171 bajtów:

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}

Działa poprzez wykonanie algorytmu Steinhaus – Johnson – Trotter na tablicy losowej indeksów i przełożenie z powrotem na tablicę wejściową. Nie golfowany:

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
źródło
1

Rubinowy, 86 bajtów

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

Haskell - 135 bajtów

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

wynik:

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

Korzystam ze standardowej permutationsfunkcji, która nie jest oparta na zamianie, więc biorę permutacje permutacji i znajduję taką, która jest łańcuchem swapów.

Gajówka
źródło