Neuanordnen einer Reihe von Zahlen in der Reihenfolge

8

Die Frage

Erstellen Sie bei einem Satz von 9 Zahlen, m[]die nur die Zahlen 1 bis 9 in zufälliger Reihenfolge enthalten, wobei keine zwei Zahlen gleich sind, ein Programm in einer beliebigen Sprache, das die Zahl in numerischer Reihenfolge neu anordnet (1, 2, 3, usw. usw.) durch nur das Umschalten von zwei nebeneinander liegenden Zahlen (dh 1, 3, 2 → 1, 2, 3).

Regeln

  • Sie können das Set nur ändern, indem Sie zwei nebeneinander liegende Nummern wechseln
  • Die Endnummern (1 bis 9 in der Reihenfolge) sollten in enthalten sein m[]
  • Sie können jede Sprache verwenden, die Sie möchten
  • Die Antwort mit der geringsten Anzahl von Bytes gewinnt

Bearbeiten:

Ihr Code muss die Ausgabe nicht drucken, aber das neu angeordnete Array muss sich in befinden m[].

Miau Mix
quelle
6
Also im Grunde ein Bubble Sort Algorithmus?
Optimierer
@ Optimizer Richtig
Meow Mix
1
Müssen Sie die Zwischenschritte drucken?
xnor
Können Sie weitere Beispiele zeigen?
Ismael Miguel
7
können wir nur 1,2,3,4,5,6,7,8,9 zurückgeben?
Ewan

Antworten:

10

CJam, 15 Bytes

q~A{{a+$~}*]}*p

Wie es funktioniert:

q~                     e# Read the CJam styled input array (For ex. [1 3 4 2 5 6 8 7 9])
  A{        }*         e# Run the loop 10 times. This is enough times for a 10 length
                       e# input array in a bubble sort
    {    }*            e# reduce
     a+$~              e# Rearrange the pair so that they are sorted
           ]           e# After each loop, wrap the numbers back into the array
              p        e# Print the array after the loops are done

Probieren Sie es hier online aus

Optimierer
quelle
9

Mathematica, 38 Bytes

#//.{a___,b_,c_,d___}/;b>c:>{a,c,b,d}&

Dies ist eine unbenannte Funktion, die ein Array verwendet, das eine Ersetzungsregel anwendet, bis das Muster nicht mehr gefunden werden kann. Das Muster ist eine Liste , die zwei aufeinander folgende Elemente hat bund cwo b > c, und die Regel , sagt der tauschen bund caber ansonsten lassen Sie das Array unangetastet.

Es gibt hier viel syntaktischen Zucker, aber der Code ist tatsächlich sehr gut lesbar, wenn Sie ein bisschen Mathematica kennen:

# //. {a___,b_,c_,d___} /; b>c :> {a,c,b,d} &
^  ^     ^   ^          ^      ^            ^
|  |     |   |          |      |            |
|  |     |   | Declares an unnamed function |
|  |     |   |          |      |
| The function's argument      |
   |     |   |          |      |
   | Replace while possible... |
         |   |          |      |
         | Zero or more list elements.
             |          |      |
             | A single list element
                        |      |
                        | A condition for the pattern
                               |
                               | What to replace the pattern with
Martin Ender
quelle
9

Python 3, 72 Bytes

from random import*
while m!=sorted(m):p=randrange(8);m[p:p]=m.pop(p+1),

Der Bogosort-Ansatz (auch bekannt als dumme Sortierung): Tauschen Sie benachbarte Elemente nach dem Zufallsprinzip aus, bis das Array sortiert wird. Läuft normalerweise unter einer Sekunde.

2 Bytes dank @xnor.

randomra
quelle
4

Python 2, 45

for i in range(8)*8:m[i:i+2]=sorted(m[i:i+2])

Durchläuft die Liste und sortiert aufeinanderfolgende Elementpaare. Der Index idurchläuft 0,1,2,3,4,5,6,7acht Mal, wodurch garantiert wird, dass alle Elemente durchblasen und die Liste sortiert wird.

xnor
quelle
4

Pyth, 13 - 15 Bytes

Lösung, die den angeforderten Austausch durchführt und keine Ausgabe erzeugt:

#X=Qhf>FT.:Q2

Lösung, die den angeforderten Austausch durchführt und bei jedem Schritt den Zwischenzustand der Liste ausgibt:

#QX=Qhf>FT.:Q2

Lösung, die den angeforderten Austausch durchführt und den endgültigen Status der Liste druckt:

#X=Qhf>FT.:Q2;Q

Demonstration der mittleren Lösung oben.

Die Methode zum Austauschen benachbarter Werte stammt aus der Antwort von @ Jakube.

Das Programm verwendet #die Schleife bis zur Fehleranweisung, um ein benachbartes Paar falsch geordneter Elemente auszutauschen, bis kein solches Paar mehr vorhanden ist. An diesem Punkt löst die hKopffunktion einen Fehler aus und beendet das Programm.

isaacg
quelle
Die Ausgabe zusätzlicher Dinge, die von der Frage nicht angefordert wurden, wird als Standardlücke angesehen.
Optimierer
@Optimizer Eigentlich erwähnt das OP die Ausgabe überhaupt nicht. Es geht lediglich darum, eine Reihe von Zahlen zu ändern. Daher könnte der gleiche Einwand gegen die meisten Antworten hier erhoben werden. Ich werde dies in meiner Antwort vermerken.
isaacg
Sie sollten stattdessen das OP fragen. Ich habe nur gefragt. Aber ich denke, es ist gegeben und Sie missbrauchen einfach die Stille, um Ihr Programm zu verkürzen: P
Optimizer
@Optimizer Meine Antwort wurde entsprechend aktualisiert.
isaacg
1
Ich stimme für die erste Version, das Set ist sortiert und es ist keine Ausgabe erforderlich. Es ist nützlich, eine Ausgabe hinzuzufügen, um zu überprüfen, ob das Programm funktioniert, aber ob es Teil eines Tests ist und nicht gezählt werden soll.
edc65
3

Retina , 95 93 Bytes

Nicht besonders wettbewerbsfähig (und wahrscheinlich immer noch golffähig), aber los geht's ...

(.)1
1$1
([^1])2
2$1
([4-9])3
3$1
([5-9])4
4$1
([6-9])5
5$1
([7-9])6
6$1
(8|9)7
7$1
)`98
89
<empty>
<empty>

Wo <empty>sollte eine leere Zeile sein.

Da alle Zahlen einstellig sind, wird nur eine Zeichenfolge mit allen 9 Ziffern als Eingabe erwartet und 123456789nach erfolgreicher Sortierung gedruckt . Jede Stufe führt einen einzelnen Tausch durch und das )1`zeigt an, dass alle bis auf die letzte Stufe wiederholt werden sollten, bis sich das Ergebnis nicht mehr ändert.

Die leere Stufe am Ende ist notwendig, da wir sonst jedes Mal, wenn die 98Stufe verarbeitet wird , Zwischenergebnisse erhalten würden .

Hier sind alle Zwischenergebnisse (wann immer sie sich ändern) für einen Beispiellauf:

451629387
451269387
451263987
451263978
415263978
412563978
412536978
412536798
412536789
142536789
124536789
124356789
123456789

(Ich habe dies durch Hinzufügen der :Option zu jeder Stufe erhalten und aufeinanderfolgende Duplikate manuell entfernt.)

Martin Ender
quelle
3

Pyth, 17 Bytes

uXGhaf>FT.:G2]Z)Q

Das Wechseln von Elementen in einer Liste ist in Pyth sehr teuer. Hier ist also eine unterhaltsame Lösung, die die Regeln ein wenig erweitert. Es ist wahrscheinlich nicht gültig.

Probieren Sie es online aus: Pyth Compiler / Executor

Erläuterung

Zuallererst ist die zeitliche Komplexität meines Codes O(n^3). Dies ist jedoch nicht der interessante Teil. Die Frage sagt nichts über die Komplexität aus.

Der entscheidende Teil ist, wie ich zwei Elemente in der Liste wechsle. Angenommen, ich möchte die Elemente m[3]und wechseln m[4]. Ich kümmere mich nicht um die Indizes 3und 4überhaupt. Ich erstelle einfach eine zweite Liste, die jedes Element, das gleich ist, m[3]durch die Zahl m[4]und jede Zahl, die gleich m[4]dem Wert ist, ersetzt m[3]. Da die Liste keine Duplikate enthält, wird das Umschalten dieser beiden Werte simuliert. Wenn es Duplikate wie in der Eingabe [1, 3, 2, 2]gäbe, wäre die Ausgabe [1, 2, 3, 3]. Und wenn Sie die Eingabe geben [1, 2, 1], würde sie in einer Endlosschleife enden. Ich erstelle die zweite Liste nicht explizit, sie ist nur ein Teil von Pyths Implementierung der Übersetzungsmethode. Wenn Sie die aktuellen Listen ausdrucken ( siehe hier) gibt es die richtigen Werte, die Sie erwarten würden.

                   implicit: Q = input list
u               Q  set G = Q, update G as long with the following statements, 
                   until it stops changing: 
         .:G2         all pairs (G[i],G[i+1])
     f>FT             filter for pairs T, where T[0] > T[1]
    a        ]Z       add to this list of pairs [0] 
                      (ensures that the filtered list is always non-empty)
   h                  take the first element
 XG            )      translate G by this pair (switches the values T[0] with T[1])
                   print implicitly at the end 
Jakube
quelle
2

JavaScript (ES6) 56

Eine rekursive Funktion, die die angegebene Liste neu anordnet.

F=l=>l.some((v,i)=>v>l[++i]&&[l[i-1]=l[i],l[i]=v])&&F(l)

Anmerkungen

  • In JS gilt für jeden numerischen Wert v: v> undefined == false, v <undefined == false. Das Überschreiten der Array-Grenzen ist also kein Problem, wenn wir den richtigen Vergleich verwenden

  • Wenn das Array endlich sortiert ist, gibt die Funktion in 'some' false zurück und die Rekursion endet

  • Der im Falle eines Swaps zurückgegebene Wert ist ein Array mit 2 Elementen, und sein Wert ist immer "wahr". Dies funktioniert auch dann, wenn ein oder mehrere Array-Elemente 0 sind

  • Tatsächlich funktioniert die Funktion mit jeder numerischen Eingabe, nicht nur mit einzelnen und nicht wiederholten Ziffern. Es wurde keine Möglichkeit gefunden, diese OP-Einschränkung zu nutzen.

Test mit Snippet (in Firefox) - Die Snippet-Version gibt bei jedem Schritt die aktuellen Listenwerte aus.

F=l=>(log('L='+l), l.some((v,i)=>v>l[++i]&&[l[i-1]=l[i],l[i]=v])&&F(l))

function log(x) {
   L.innerHTML = L.innerHTML +x+'\n' 
}

function go() {
  l = I.value.split(/\D+/g).map(x=>x|0)
  F(l)
  O.innerHTML = '' + l
}  

go()
Unsorted: <input id=I value="2 8 4 7 5 3 9 1 6"><button onclick="go()">-></button>
<br>Sorted: <span id=O></span>
<br>Operations log:<br>
<pre id=L></pre>

edc65
quelle
1

Javascript ( ES6 ), 66 61 53 Bytes

Dank der neuen Regel kann ich noch weiter reduzieren :)

f=x=>x.map((a,i)=>a<(b=x[--i])&&f(x,x[i]=a,x[i+1]=b))


// Snippet demo: (Firefox only)
f(z=prompt().split(/\D+/).map(x=>+x))
alert(z.join(', '));

Kommentiert

f=x=> // recursive function f
    x.map( // map function to array
        (a, i)=> // a = current value, i = current index
            a < (b = x[--i]) && // poll value of previous index, compare less than
                                // comparison always false at first index as undefined will always be less
                f(x, x[i] = a, x[i + 1] = b) // if true, swap values and call f
    )
nderscore
quelle
0

C, 183

main(c,d,s){int a[10];for(c=0;c<10;c++)scanf("%d", &a[c]);for (c=0;c<10;c++){for(d=0;d<10-c-1;d++){if(a[d]>a[d+1]){s=a[d];a[d]=a[d+1];a[d+1]=s;}}}for(c=0;c<10;c++)printf("%d", a[c]);}

Es wird noch nicht gespielt, außer Variablennamen.

Joshpbarron
quelle
0

Haskell, 59 Bytes

s e(h:t)=min e h:max e h:t
f l=iterate(init.foldr s[9])l!!9

Die Funktion ssetzt ein Element evor oder an die zweite Stelle einer Liste, je nachdem, ob es kleiner oder größer als das erste Element der Liste ist. Durch das Einklappen sin die Eingabeliste wird das kleinste Element nach vorne gesprudelt. Ich falte in eine Liste mit einer Single, 9die ich sofort danach entferne init, damit ich nicht nach leeren Listen suchen muss s. iteratewiederholt den Faltvorgang für immer und erstellt eine Liste mit Zwischenergebnissen. Das Endergebnis ist das 9. Element dieser Liste.

Nimi
quelle
0

Perl, 68 Bytes

{for(0..7){if($m[$_]>$m[$_+1]){splice@m,$_,2,$m[$_+1],$m[$_];redo}}}

Ungolfed Code

 {                                             # Block runs once unless redo is called

     for (0..7) {                                 # Loop index is in $_

         if ($m[$_] > $m[$_+1]) {                 # Check if swap needed

             splice @m, $_, 2, $m[$_+1], $m[$_];  # Replace a two element slice of
                                                  # the array with those 
                                                  # two elements reversed

             redo                                 # Restart the block over
         }
     }
}
Ralph Marshall
quelle