Herausforderung:

Eingabe: Eine Liste eindeutiger positiver Ganzzahlen im Bereich $[1, \text{list-size}]$ .

Ausgabe: Eine Ganzzahl: Gibt an, wie oft die Liste gemischt wird . Für eine Liste bedeutet dies, dass die Liste in zwei Hälften aufgeteilt ist und diese Hälften verschachtelt sind (dh, ein [1,2,3,4,5,6,7,8,9,10]einmaliges Mischen der Liste würde zu Riffle führen [1,6,2,7,3,8,4,9,5,10], was für diese Herausforderung die Eingabe [1,6,2,7,3,8,4,9,5,10]zur Folge hätte 1).

Herausforderungsregeln:

• Sie können davon ausgehen, dass die Liste nur positive Ganzzahlen im Bereich $[1, \text{list-size}]$ (oder $[0, \text{list-size}-1]$ wenn Sie sich für 0-indizierte Eingabelisten entscheiden).
• Sie können davon ausgehen, dass alle Eingabelisten entweder eine gültige Riffle-Shuffled-Liste oder eine sortierte Liste sind, die nicht gemischt wird (in diesem Fall ist die Ausgabe 0).
• Sie können davon ausgehen, dass die Eingabeliste mindestens drei Werte enthält.

Schritt für Schritt Beispiel:

Eingang: [1,3,5,7,9,2,4,6,8]

Das einmalige Entmischen wird zu:, [1,5,9,4,8,3,7,2,6]weil jedes gerade 0-indizierte Element zuerst [1, ,5, ,9, ,4, ,8]kommt und danach alle ungeraden 0-indizierten Elemente [ ,3, ,7, ,2, ,6, ].
Die Liste ist noch nicht bestellt, also fahren wir fort:

Das Entmischen der Liste wird wieder: [1,9,8,7,6,5,4,3,2]
Wieder wird: [1,8,6,4,2,9,7,5,3]
Dann: [1,6,2,7,3,8,4,9,5]
Und schließlich [1,2,3,4,5,6,7,8,9]:, was eine geordnete Liste ist, also sind wir fertig mit dem Entmischen.

Wir haben das Original [1,3,5,7,9,2,4,6,8]fünf Mal neu gemischt , um es zu erreichen [1,2,3,4,5,6,7,8,9], daher ist die Ausgabe 5in diesem Fall.

Allgemeine Regeln:

• Das ist Code-Golf , also gewinnt die kürzeste Antwort in Bytes.
  Lassen Sie sich von Code-Golf-Sprachen nicht davon abhalten, Antworten mit Nicht-Codegolf-Sprachen zu veröffentlichen. Versuchen Sie, für jede Programmiersprache eine möglichst kurze Antwort zu finden.
• Für Ihre Antwort gelten Standardregeln mit Standard-E / A-Regeln. Daher dürfen Sie STDIN / STDOUT, Funktionen / Methoden mit den richtigen Parametern und vollständige Programme vom Rückgabetyp, verwenden. Ihr Anruf.
• Standardlücken sind verboten.
• Fügen Sie nach Möglichkeit einen Link mit einem Test für Ihren Code hinzu (z. B. TIO ).
• Außerdem wird dringend empfohlen, eine Erklärung für Ihre Antwort hinzuzufügen.

Testfälle:

Input                                                   Output

[1,2,3]                                                 0
[1,2,3,4,5]                                             0
[1,3,2]                                                 1
[1,6,2,7,3,8,4,9,5,10]                                  1
[1,3,5,7,2,4,6]                                         2
[1,8,6,4,2,9,7,5,3,10]                                  2
[1,9,8,7,6,5,4,3,2,10]                                  3
[1,5,9,4,8,3,7,2,6,10]                                  4
[1,3,5,7,9,2,4,6,8]                                     5
[1,6,11,5,10,4,9,3,8,2,7]                               6
[1,10,19,9,18,8,17,7,16,6,15,5,14,4,13,3,12,2,11,20]    10
[1,3,5,7,9,11,13,15,17,19,2,4,6,8,10,12,14,16,18,20]    17
[1,141,32,172,63,203,94,234,125,16,156,47,187,78,218,109,249,140,31,171,62,202,93,233,124,15,155,46,186,77,217,108,248,139,30,170,61,201,92,232,123,14,154,45,185,76,216,107,247,138,29,169,60,200,91,231,122,13,153,44,184,75,215,106,246,137,28,168,59,199,90,230,121,12,152,43,183,74,214,105,245,136,27,167,58,198,89,229,120,11,151,42,182,73,213,104,244,135,26,166,57,197,88,228,119,10,150,41,181,72,212,103,243,134,25,165,56,196,87,227,118,9,149,40,180,71,211,102,242,133,24,164,55,195,86,226,117,8,148,39,179,70,210,101,241,132,23,163,54,194,85,225,116,7,147,38,178,69,209,100,240,131,22,162,53,193,84,224,115,6,146,37,177,68,208,99,239,130,21,161,52,192,83,223,114,5,145,36,176,67,207,98,238,129,20,160,51,191,82,222,113,4,144,35,175,66,206,97,237,128,19,159,50,190,81,221,112,3,143,34,174,65,205,96,236,127,18,158,49,189,80,220,111,2,142,33,173,64,204,95,235,126,17,157,48,188,79,219,110,250]
                                                        45

Gelee , 8 Bytes

ŒœẎ$ƬiṢ’

Probieren Sie es online!

Wie?

ŒœẎ$ƬiṢ’ - Link: list of integers A
    Ƭ    - collect up until results are no longer unique...
   $     -   last two links as a monad:
Œœ       -     odds & evens i.e. [a,b,c,d,...] -> [[a,c,...],[b,d,...]]
  Ẏ      -     tighten                         -> [a,c,...,b,d,...]
     Ṣ   - sort A
    i    - first (1-indexed) index of sorted A in collected shuffles
      ’  - decrement

JavaScript (ES6), 44 Byte

Kürzere Version von @nwellnhof vorgeschlagen

Erwartet ein Deck mit 1-indizierten Karten als Eingabe.

f=(a,x=1)=>a[x]-2&&1+f(a,x*2%(a.length-1|1))

Probieren Sie es online!

Ausgehend von einem Deck $[c_0,\ldots,c_{L-1}]$ der Länge $L$ definieren wir:

Und wir suchen nach $n$ so dass $c_{x_n}=2$ .

JavaScript (ES6),  57 52  50 Bytes

Erwartet ein Deck mit 0-indizierten Karten als Eingabe.

f=(a,x=1,k=a.length-1|1)=>a[1]-x%k&&1+f(a,x*-~k/2)

Probieren Sie es online!

Wie?

Da JS keine native Unterstützung für das Extrahieren von Array-Slices mit benutzerdefinierten Schritten bietet, wäre die Simulation des gesamten Riffle-Shuffle wahrscheinlich recht kostspielig (aber um ehrlich zu sein, habe ich es nicht einmal versucht). Die Lösung kann jedoch auch durch einen Blick auf die 2. Karte und die Gesamtzahl der Karten im Stapel gefunden werden.

Bei einem Deck der Länge $L$ sucht dieser Code nach $n$ so dass:

wo $c_2$ die zweite Karte ist und$k$ folgt definiert ist:

Python 2 , 39 Bytes

f=lambda x:x[1]-2and-~f(x[::2]+x[1::2])

Probieren Sie es online!

-4 Dank an Jonathan Allan .

R , 58 55 45 Bytes

a=scan();while(a[2]>2)a=matrix(a,,2,F<-F+1);F

Probieren Sie es online!

Simuliert den Sortiervorgang. Die Eingabe ist 1-indiziert und gibt FALSE0 zurück.

Perl 6 , 34 32 Bytes

-2 Bytes dank Jo King

{(.[(2 X**^$_)X%$_-1+|1]...2)-1}

Probieren Sie es online!

Ähnlich wie bei Arnauld . Der Index der zweiten Karte nach n Mischen ist 2**n % kmit k wie in Arnauld's Antwort definiert.

APL (Dyalog Unicode) , 35 26 23 22 Byte ^SBCS

{⍵≡⍳≢⍵:0⋄1+∇⍵[⍒2|⍳⍴⍵]}

Probieren Sie es online!

Dank an Adám für die Hilfe, Erik der Outgolfer für -3 und ngn für -1.

Der TIO-Link enthält zwei Testfälle.

Erläuterung:

{⍵≡⍳≢⍵:0⋄1+∇⍵[⍒2|⍳⍴⍵]}
{⍵≡⍳≢⍵:0⋄1+∇⍵[⍒2|⍳⍴⍵]} ⍝ function takes one argument: ⍵, the array
 ⍵≡⍳≢⍵                 ⍝ if the array is sorted:
 ⍵≡⍳≢⍵                 ⍝ array = 1..length(array)
      :0               ⍝ then return 0
        ⋄              ⍝ otherwise
         1+            ⍝ increment
           ∇           ⍝ the value of the recursive call with this argument:
            ⍵[      ]  ⍝ index into the argument with these indexes:
                 ⍳⍴⍵   ⍝ - generate a range from 1 up to the size of ⍵
               2|      ⍝ - %2: generate a binary mask like [1 0 1 0 1 0]
              ⍒        ⍝ - grade (sorts but returns indexes instead of values), so we have the indexes of all the 1s first, then the 0s.

¹

Perl 6 , 36 34 32 Bytes

-2 Bytes dank nwellnhof

$!={.[1]-2&&$!(.sort:{$++%2})+1}

Probieren Sie es online!

Reverse Riffle Shuffles, indem Sie nach dem Index Modulo 2 sortieren, bis die Liste sortiert ist. Anschließend wird die Länge der Sequenz zurückgegeben.

Es ist lustig, ich versuche normalerweise nicht die rekursive Methode für Perl 6, aber diesmal war sie kürzer als das Original.

Erläuterung:

$!={.[1]-2&&$!(.sort:{$++%2})+1}
$!={                           }   # Assign the anonymous code block to $!
    .[1]-2&&                       # While the list is not sorted
            $!(             )      # Recursively call the function on
               .sort:{$++%2}       # It sorted by the parity of each index
                             +1    # And return the number of shuffles

05AB1E (Legacy) , 9 Byte

[DāQ#ι˜]N

Probieren Sie es online!

Erläuterung

[   #  ]     # loop until
  ā          # the 1-indexed enumeration of the current list
 D Q         # equals a copy of the current list
     ι˜      # while false, uninterleave the current list and flatten
        N    # push the iteration index N as output

Java (JDK) , 59 Byte

a->{int c=0;for(;a[(1<<c)%(a.length-1|1)]>2;)c++;return c;}

Probieren Sie es online!

Funktioniert zuverlässig nur für Arrays mit einer Größe von weniger als 31 oder für Lösungen mit weniger als 31 Iterationen. Eine allgemeinere Lösung finden Sie in der folgenden Lösung mit 63 Byte:

a->{int i=1,c=0;for(;a[i]>2;c++)i=i*2%(a.length-1|1);return c;}

Probieren Sie es online!

Erläuterung

Bei einem Riffle ist die nächste Position das vorherige Modulo (eins mal zwei), entweder Länge, wenn es ungerade ist, oder Länge - 1, wenn es gerade ist.

Ich durchlaufe also alle Indizes mit dieser Formel, bis ich den Wert 2 im Array finde.

Credits

• -8 Bytes dank Kevin Cruijssen . (Vorheriger Algorithmus unter Verwendung eines Arrays)
• -5 Bytes danke an Arnauld .

J , 28 26 Bytes

-2 Bytes danke an Jonah!

 1#@}.(\:2|#\)^:(2<1{])^:a:

Probieren Sie es online!

Inspiriert von der APL-Lösung von Ven.

Erläuterung:

               ^:       ^:a:   while 
                 (2<1{])       the 1-st (zero-indexed) element is greater than 2   
     (        )                do the following and keep the intermediate results
          i.@#                 make a list form 0 to len-1
        2|                     find modulo 2 of each element
      /:                       sort the argument according the list of 0's and 1's
1  }.                          drop the first row of the result
 #@                            and take the length (how many rows -> steps)     

K (ngn / k) , 25 Bytes

Danke an ngn für den Rat und für seinen K-Dolmetscher!

{#1_{~2=x@1}{x@<2!!#x}\x}

Probieren Sie es online!

APL (NARS), Zeichen 49, Bytes 98

{0{∧/¯1↓⍵≤1⌽⍵:⍺⋄(⍺+1)∇⍵[d],⍵[i∼d←↑¨i⊂⍨2∣i←⍳≢⍵]}⍵}

Warum in der tiefsten Schleife ein Algo verwenden, das nlog (n) sein sollte, wenn wir ein lineares n verwenden können? nur für ein paar Bytes mehr? [⍵≡⍵ [⍋⍵] O (nlog n) und die Konfrontation jedes Elements für see sind nach ∧ / ¯1 ↓ ⍵≤1⌽⍵ O (n)] geordnet:

  f←{0{∧/¯1↓⍵≤1⌽⍵:⍺⋄(⍺+1)∇⍵[d],⍵[i∼d←↑¨i⊂⍨2∣i←⍳≢⍵]}⍵}
  f ,1
0
  f 1 2 3
0
  f 1,9,8,7,6,5,4,3,2,10
3
  f 1,3,5,7,9,11,13,15,17,19,2,4,6,8,10,12,14,16,18,20
17

Ruby , 42 Bytes

f=->d,r=1{d[r]<3?0:1+f[d,r*2%(1|~-d.max)]}

Probieren Sie es online!

Wie:

Suchen Sie nach Nummer 2 innerhalb des Arrays: Wenn es auf der zweiten Position ist, wurde das Deck nicht gemischt, andernfalls überprüfen Sie die Positionen, an denen aufeinanderfolgende Mischen es platzieren würden.

R , 70 72 Bytes

x=scan();i=0;while(any(x>sort(x))){x=c(x[y<-seq(x)%%2>0],x[!y]);i=i+1};i

Probieren Sie es online!

Behandelt jetzt den Null-Shuffle-Fall.

C (GCC) 64 63 Bytes

-1 Byte vom Nwellnhof

i,r;f(c,v)int*v;{for(i=r=1;v[i]>2;++r)i=i*2%(c-1|1);return~-r;}

Dies ist eine drastisch kürzere Antwort, basierend auf den Antworten von Arnauld und Olivier Grégoire. Ich lasse meine alte Lösung unten, da sie das etwas allgemeinere Problem von Decks mit nicht zusammenhängenden Karten löst.

Probieren Sie es online aus

C (GCC) 162 Bytes

a[999],b[999],i,r,o;f(c,v)int*v;{for(r=0;o=1;++r){for(i=c;i--;(i&1?b:a)[i/2]=v[i])o=(v[i]>v[i-1]|!i)&o;if(o)return r;for(i+=o=c+1;i--;)v[i]=i<o/2?a[i]:b[i-o/2];}}

Probieren Sie es online aus

a[999],b[999],i,r,o; //pre-declare variables
f(c,v)int*v;{ //argument list
    for(r=0;o=1;++r){ //major loop, reset o (ordered) to true at beginning, increment number of shuffles at end
        for(i=c;i--;(i&1?b:a)[i/2]=v[i]) //loop through v, split into halves a/b as we go
            o=(v[i]>v[i-1]|!i)&o; //if out of order set o (ordered) to false
        if(o) //if ordered
            return r; //return number of shuffles
        //note that i==-1 at this point
        for(i+=o=c+1;i--;)//set i=c and o=c+1, loop through v
            v[i]=i<o/2?a[i]:b[i-o/2];//set first half of v to a, second half to b
    }
}

R, 85 Bytes

s=scan();u=sort(s);k=0;while(any(u[seq(s)]!=s)){k=k+1;u=as.vector(t(matrix(u,,2)))};k

Probieren Sie es online aus.

Erläuterung

Dumme Methode (Brute Force), viel weniger elegant, als der Karte Nr. 2 zu folgen.

Anstatt die Eingabe zu mischen s, beginnen wir mit einem sortierten Vektor u, den wir schrittweise mischen, bis er mit identisch ist s. Dies gibt Warnungen (aber die Zufallszahlen sind immer noch korrekt) für ungerade Längen der Eingabe aus, da ein Vektor mit ungerader Länge in eine 2-Spalten-Matrix gefaltet wird. In diesem Fall wird in R der fehlende Datenpunkt durch Rückführung des ersten Eingabeelements gefüllt.

Die Schleife wird niemals enden, wenn wir einen Vektor bereitstellen, der nicht unmischbar ist.

Nachtrag: Sie speichern ein Byte, wenn Sie stattdessen das Mischen aufheben. Anders als in der obigen Antwort ist es nicht erforderlich, mit zu transponieren t(), die Reihenfolge ist jedoch byrow=TRUEder Grund, warum in Tangezeigt wird matrix().

R 84 Bytes

s=scan();u=sort(s);k=0;while(any(s[seq(u)]!=u)){k=k+1;s=as.vector(matrix(s,,2,T))};k

Probieren Sie es online!

PowerShell , 116 114 108 84 78 Byte

-24 Bytes dank Erik der Outgolfer ‚s Lösung .

-6 bytes dank mazzy .

param($a)for(;$a[1]-2){$n++;$t=@{};$a|%{$t[$j++%2]+=,$_};$a=$t.0+$t.1;$j=0}+$n

Probieren Sie es online!

Wolfram Language (Mathematica) , 62 Byte

c=0;While[Sort[a]!=a,a=a[[1;;-1;;2]]~Join~a[[2;;-1;;2]];c++];c

Probieren Sie es online!

Erläuterung

Die Eingabeliste ist a. Es wird ungerührt und mit der sortierten Liste verglichen, bis sie übereinstimmen.

Rot , 87 79 78 Bytes

func[b][c: 0 while[b/2 > 2][c: c + 1 b: append extract b 2 extract next b 2]c]

Probieren Sie es online!

Perl 5 -pa , 77 Bytes

map{push@{$_%2},$_}0..$#F;$_=0;++$_,@s=sort{$a-$b}@F=@F[@0,@1]while"@F"ne"@s"

Probieren Sie es online!

Pyth , 18 Bytes

L?SIb0hys%L2>Bb1
y

Probieren Sie es online!

-2 danke an @Erik den Outgolfer.

Das Skript hat zwei Zeilen: Die erste definiert eine Funktion y, die zweite Zeile ruft ymit dem impliziten Q(evaluierten stdin) Argument auf.

L?SIb0hys%L2>Bb1
L                function y(b)
 ?               if...
  SIb            the Invariant b == sort(b) holds
     0           return 0
      h          otherwise increment...
       y         ...the return of a recursive call with:
             B   the current argument "bifurcated", an array of:
              b   - the original argument
            >  1  - same with the head popped off
          L      map...
         % 2     ...take only every 2nd value in each array
        s         and concat them back together

¹

PowerShell , 62 71 70 66 Byte

+9 Bytes, wenn Testfälle mit einer geraden Anzahl von Elementen hinzugefügt werden.

-1 byte mit splatting.

-4 Bytes: Umhüllen Sie den Ausdruck mit $i, $jin einen neuen Bereich.

for($a=$args;$a[1]-2;$a=&{($a|?{++$j%2})+($a|?{$i++%2})}){$n++}+$n

Probieren Sie es online!

Japt , 13, 11 10 Bytes

Nehmen Sie meinen glänzenden, neuen , sehr in Arbeit befindlichen Dolmetscher für eine Probefahrt mit.

ÅÎÍ©ÒßUñÏu

Probieren Sie es aus oder führen Sie alle Testfälle aus

ÅÎÍ©ÒßUñÏu     :Implicit input of integer array U
Å              :Slice the first element off U
 Î             :Get the first element
  Í            :Subtract from 2
   ©           :Logical AND with
    Ò          :  Negation of bitwise NOT of
     ß         :  A recursive call to the programme with input
      Uñ       :    U sorted
        Ï      :    By 0-based indices
         u     :    Modulo 2

Python 3, 40 Bytes

f=lambda x:x[1]-2and 1+f(x[::2]+x[1::2])  # 1-based
f=lambda x:x[1]-1and 1+f(x[::2]+x[1::2])  # 0-based

Probieren Sie es online!

Ich muss die Seite häufiger aktualisieren: Ich habe Erik the Outgolfer's Edit verpasst, der einen ähnlichen Trick macht =)