Schritte der Permutation

10

Schreiben Sie eine Funktion, die einen Satz von Ganzzahlen verwendet und jede Permutation des Satzes und den zwischen jedem Schritt durchgeführten Austausch druckt

Eingang

eine Menge von ganzen Zahlen, zum Beispiel (0, 1, 2)

Ausgabe

die Liste der Permutationen und Swaps im Format (Set) (Swap) (Set) ...

Testfall

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)

Regeln

  • Sie können den Satz von Zahlen beliebig formatieren.
  • Sie können die Swaps in beliebiger Reihenfolge durchführen
  • Sie können Permutationen und Swaps wiederholen, um eine neue zu erhalten
  • Ihr Code muss die Swaps nicht tatsächlich ausführen, die Ausgabe muss nur anzeigen, welcher Swap zwischen Ihrer letzten und Ihrer aktuellen Ausgabe durchgeführt wurde
  • Ihr Code muss nur für Mengen mit 2 oder mehr Elementen funktionieren
  • Der Satz, den Sie erhalten, enthält keine sich wiederholenden Elemente (z. B. (0, 1, 1, 2) ist ungültig).

Dies ist Code-Golf, also gewinnt der kürzeste Code!

Billyoyo
quelle
Können wir Zufälligkeit verwenden?
Zgarb
Sie meinen, machen Sie einfach eine Menge zufälliger Swaps, bis Sie alle Permutationen erreicht haben? Ja, aber Sie müssen sicher sein, dass alle Permutationen gedruckt wurden
Billyoyo
3
Willkommen bei PPCG! Schöne erste Herausforderung. Ich würde vorschlagen, das Beispiel so zu bearbeiten, dass die Elemente nicht mit den Indizes verwechselt werden, wie z. B. use set (3, 1, 4)oder so - ich habe es das erste Mal gelesen, als ich sehr verwirrt war, weil der erste Austausch 0,1die Elemente, 0,1aber auch die Indizes 0,1, aber dann den nächsten vertauschte Swap folgte nicht diesem Muster. Ich werde Sie auch auf die Sandbox verweisen, in der Sie Herausforderungen posten und Feedback erhalten können, bevor Sie sie auf der Hauptseite veröffentlichen.
AdmBorkBork
2
@TimmyD danke für den Vorschlag, ich habe das Beispiel geändert. Ich habe den Link zum Sandkasten gesehen, kurz nachdem ich dies gepostet habe. Ich werde von nun an zuerst dort posten!
Billyoyo
1
Der Steinhaus-Johnson-Trotter-Algorithmus generiert die minimal erforderliche Sequenz.
Neil

Antworten:

3

Mathematica, 102 Bytes

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

Beispiele

// Spalte für ein klareres Ergebnis

%[{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
quelle
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+")");}}

Brute-Force-Ansatz. Es werden so lange zufällige Swaps durchgeführt, bis alle möglichen Permutationen stattgefunden haben. Es wird ein Satz der Zeichenfolgendarstellung des Arrays verwendet, um zu überprüfen, wie viele verschiedene Zustände generiert wurden. Für n verschiedene ganze Zahlen gibt es n! = 1 * 2 * 3 * .. * n verschiedene Permutationen.

Aktualisieren

  • Ich folgte Kevin Cruijssens Vorschlägen, ein bisschen mehr Golf zu spielen.

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

Verwendungszweck:

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

Wie Sie sehen, gibt es viel mehr Swaps als das erforderliche Minimum. Aber es scheint zu funktionieren :-D

Als Bonus funktioniert es auch mit Strings, dh

$ java P 'one' 'two'
[one, two]
(two,one)
[two, one]
Master_ex
quelle
Haben Sie eine Version ohne Golf, mit der wir uns Ihre Methode ansehen können?
Billyoyo
@ Billyoyo: Der Code ohne Golf wurde hinzugefügt. Nichts
Besonderes
Sie können es ein bisschen Golf spielen. Sie müssen keine Warnungen korrigieren, sodass Sie die Set-Deklarationen entfernen können : Set s=new HashSet();. Ihr Code in der Methode nkann eine einzelne Rückgabe sein : static int n(int x){return x==1?1:x*n(x-1);}. Und Sie können String zin Ihrer Methode ostattdessen durch ein generisches ersetzen : static<T>void o(T z){System.out.println(z);s.add(z);}. Alles zusammen würde es auf 426 Bytes kommen .
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`,`)>

Hinweis: Ich bin mir nicht sicher, wie flexibel das Ausgabeformat ist. Möglicherweise kann ich dies für 171 Byte tun:

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}

Funktioniert, indem der Steinhaus-Johnson-Trotter- Algorithmus für das Shuffle-Array von Indizes ausgeführt und in das Eingabearray zurückübersetzt wird. 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
quelle
1

Ruby, 86 Bytes

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

Ausgabe:

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

Ich verwende die Standardfunktion permutations, die nicht auf Swaps basiert, also nehme ich die Permutationen der Permutationen und finde eine, die zufällig eine Kette von Swaps ist.

BlackCap
quelle