Ist es zu schwer , Sudoku zu lösen ? Auch die Brute-Force- Version? Hier ist eine Codierungsübung, die etwas einfacher ist. Ich hoffe. :-P

Schreiben Sie die kürzeste Funktion, um Bogosort zu implementieren. Im Einzelnen sollte Ihre Funktion:

• Nehmen Sie ein Array (oder das Äquivalent Ihrer Sprache) als Eingabe
• Überprüfen Sie, ob die Elemente sortiert sind. Wenn ja, geben Sie das Array zurück
• Wenn nicht, mische die Elemente und beginne erneut

Der kürzeste Eintrag gewinnt. Bei einem Unentschieden wird eine Funktion bevorzugt, die einen benutzerdefinierten Komparator (und / oder einen Pseudozufallszahlengenerator) unterstützt. Verbleibende Bindungen werden durch Bevorzugung der früheren Einreichung gelöst.

Erläuterungen: Sie können jeden gewünschten Elementtyp verwenden, sofern Sie diese natürlich auf irgendeine Weise bestellen können. Auch das Mischen muss gleichmäßig sein; nichts davon "Ich werde es nur schnell sortieren und es gemischt nennen". :-)

APL (Dyalog), 20

{⍵≡⍵[⍋⍵]:⍵⋄∇⍵[?⍨⍴⍵]}

Erläuterung

⍵ist das (rechte) Argument
⍵≡⍵[⍋⍵]: Prüft, ob ⍵sortiert gleich ⍵ist
:⍵: Wenn ja, dann gebe zurück ⍵
∇⍵[?⍨⍴⍵]: Andernfalls generiere ein Array von 1 bis ⍴⍵(Länge von ⍵) in zufälliger Reihenfolge, ordne ⍵danach neu ( ⍵[...]) und wende die Funktion darauf an ( ∇)

Plötzlich wieder dieses Problem und ...

APL (Dyalog), 19

{∧/2≤/⍵:⍵⋄∇⍵[?⍨⍴⍵]}

Wenn man nur darüber nachdenkt, ein Array in der Prüfung zu sortieren, macht es irgendwie sinnlos (nicht zu sagen, dass Bogosort sinnvoll ist), wäre dies eine genauere Implementierung ∧/2≤/⍵, und das senkt zufällig die Anzahl der Zeichen.

Perl 6: 23 Zeichen

@s.=pick(*)until[<=] @s

APL (22)

{(⍳X←⍴⍵)≡⍋⍵:⍵⋄∇⍵[X?X]}

Verwendung:

    {(⍳X←⍴⍵)≡⍋⍵:⍵⋄∇⍵[X?X]} 3 2 1
1 2 3

Erläuterung:

• ⍋⍵: Gibt die Indizes der Elemente in sortierter Reihenfolge, so ⍋30 10 20gibt2 1 3
• (⍳X←⍴⍵)≡⍋⍵:⍵Speichern Sie die Länge der Eingabeliste in X. Wenn der Bereich [1..X]der sortierten Indexreihenfolge entspricht, wird die Liste sortiert. Geben Sie sie daher zurück.
• ⋄∇⍵[X?X]: Wenn dies nicht der Fall ist, verwenden Sie ein gemischtes Array.

Ruby - 33 Zeichen

g=->l{l.shuffle!!=l.sort ?redo:l}

Mathematica , 40 37

NestWhile[RandomSample,#,Sort@#!=#&]&

Mit Leerzeichen:

NestWhile[RandomSample, #, Sort@# != # &] &

J - 34 27

f=:({~?~@#)^:(1-(-:/:~))^:_

z.B:

f 5 4 1 3 2
1 2 3 4 5

f 'hello'
ehllo

Der Teil {~? ~ @ # Mischt die Eingabe:

({~ ?~@#) 1 9 8 4
4 8 9 1
({~ ?~@#) 'abcd'
bdca

Python 61

Sortiert an Ort und Stelle.

import random
def f(l):
 while l!=sorted(l):random.shuffle(l)

Python 94

from itertools import*
def f(a):return [x for x in permutations(a) if x==tuple(sorted(a))][0]

Andere Python-Antworten verwenden random.shuffle (). In der Dokumentation des Python-Zufallsmoduls heißt es:

Beachten Sie, dass die Gesamtzahl der Permutationen von x für selbst kleine len (x) größer ist als die Periode der meisten Zufallszahlengeneratoren; Dies impliziert, dass die meisten Permutationen einer langen Sequenz niemals erzeugt werden können.

K 31, 25

{while[~x~x@<x;x:x@(-#x)?#x];x}

{x@(-#x)?#x}/[{~x~x@<x};]

.

k){x@(-#x)?#x}/[{~x~x@<x};] 3 9 5 6 7 9 1
`s#1 3 5 6 7 9 9

.

k){x@(-#x)?#x}/[{~x~x@<x};] "ascsasd"
`s#"aacdsss"

Python (69 Zeichen)

from random import*
def f(a):
 while a>sorted(a):shuffle(a)
 return a

Sortiert ganze Zahlen in aufsteigender numerischer Reihenfolge. Beachten Sie, dass rekursive Lösungen wie

from random import*;f=lambda a:a>sorted(a)and(shuffle(a)or f(a))or a

schlägt aufgrund eines Stapelüberlaufs auch bei kleinen Eingaben (z. B. N> 5) fehl, da Python keine Tail-Call-Optimierung durchführt.

D ohne benutzerdefinierten Komparator: 59 Zeichen

R f(R)(R r){while(!isSorted(r))r.randomShuffle();return r;}

Mehr leserlich:

R f(R)(R r)
{
    while(!r.isSorted)
        r.randomShuffle();

    return r;
}

D mit benutzerdefiniertem Komparator: 69 Zeichen

R f(alias p,R)(R r){while(!isSorted!p(r))r.randomShuffle();return r;}

Mehr leserlich:

R f(alias p, R)(R r)
{
    while(!isSorted!p(r))
        r.randomShuffle();

    return r;
}

Scala 73:

def s(l:Seq[Int]):Seq[Int]=if(l==l.sorted)l else s(util.Random.shuffle l)

In Scala können wir überprüfen, ob der Compiler eine Tail-Call-Optimierung durchgeführt hat:

@annotation.tailrec
def s(l:Seq[Int]):Seq[Int]=if(l==l.sorted)l else s(util.Random shuffle l)

und ja, das tat es. Für eine kurze Liste von 100 Werten:

val rList = (1 to 100).map(x=>r.nextInt (500))
s(rList) 

Die Fertigstellung dauerte fast 4 Monate. ;)

C # (184 Zeichen)

T[]S<T>(T[]i)where T:IComparable<T>{T l=default(T);while(!i.All(e=>{var r=e.CompareTo(l)>=0;l=e;return r;})){i=i.OrderBy(a=>Guid.NewGuid()).ToArray();l=default(T);}return i.ToArray();}

Es ist nicht wirklich schön, dies in C # zu tun. Sie müssen Generika unterstützen, um sowohl Wert- als auch Referenztypen zu unterstützen. Es gibt keine Funktion zum Mischen von Arrays oder zum Überprüfen, ob etwas sortiert ist.

Hat jemand Tipps, um dies zu verbessern?

Edit Version, die nur int sortiert (134 Zeichen):

int[]S(int[]i){var l=0;while(!i.All(e=>{var r=e>=l;l=e;return r;})){i=i.OrderBy(a=>Guid.NewGuid()).ToArray();l=0;}return i.ToArray();}

GNU / BASH 65

b(){ IFS=$'\n';echo "$*"|sort -C&&echo "$*"||b $(shuf -e "$@");}

C ++ 11, 150 Zeichen

#include<deque>
#include<algorithm>
void B(std::deque &A){while(!std::is_sorted(A.begin(),A.end())std::random_shuffle(myvector.begin(),myvector.end());}

Nur zum Spaß gemacht.

Python - 61 Zeichen

Rekursiv

from random import*;f=lambda l:l==sorted(l)or shuffle(l)>f(l)

PowerShell , 85 82 56 55 52 Byte

^{-26 Bytes dank mazzy-Vorschlägen
-1 Bytes dank AdmBorkBork
-3 Bytes dank mazzy}

for($l=$args;"$l"-ne($l|sort)){$l=$l|sort{random}}$l

Probieren Sie es online!

PowerShell bietet einen relativ günstigen Array-Vergleich, indem sie in Strings umgewandelt und diese verglichen werden.

Javascript 291 Zeichen

Mindest

function f(e){var t=[].concat(e).sort();t.e=function(e){var n=true;t.forEach(function(t,r){if(t!=e[r])n=false});return n};while(!t.e(e.sort(function(){return Math.floor(Math.random()*2)?1:-1}))){console.log(e)}return e}

un-min

function f(a) {
var b = [].concat(a).sort();
b.e = function (z) {
    var l = true;
    b.forEach(function (v, i) {
        if (v != z[i]) l = false;
    });
    return l
};
while (!b.e(a.sort(function () {
    return Math.floor(Math.random() * 2) ? 1 : -1;
}))) {
    console.log(a);
}
return a;
}

Matlab, 59 Bytes

Relativ unkomplizierter Ansatz:

x=input('');while~issorted(x);x=x(randperm(numel(x)));end;x

J, 22 Bytes

$:@({~?~@#)`]@.(-:/:~)

Dies ist eine rekursive, stillschweigende Monade, die eine Agenda verwendet. So funktioniert das:

Sei yunsere Liste. Erstens ist das Verb auf der rechten Seite der Tagesordnung -:/:~. Dieses Verb wurde uns freundlicherweise von Leaky Nun zur Verfügung gestellt . Es stimmt überein ( -:), ob die Eingabe /:~mit einem monadischen Hook sortiert ( ) ist oder nicht . ( (f g) y = y f (g y)) Dies gibt dementsprechend eine Eins oder eine Null zurück. Die linke Seite der Agenda besteht aus zwei Gerundien: Auf der rechten Seite befindet sich das Identitätsverb ]und auf der linken Seite findet die Rekursion statt. Die Agenda wählt entweder die Identität Verb in der Position , 1wenn die Liste wird sortiert, und je länger Verb in der Position , 0wenn die Liste ist nicht sortiert.

$:@({~?~@#)Calls $:(das längste Verb, in dem es enthalten ist) auf dem Ergebnis von {~?~@#on y. Dies mischt die Liste, wobei ?~@#die Permutationen der Länge von yzufällig sortierten Indizes von genommen werden y. {~Gibt in einem monadischen Hook eine Liste zurück, yderen Indizes das richtige Argument sind. Diese gemischte Liste wird dann mit der Agenda erneut aufgerufen und wiederholt, bis sie sortiert ist.

C ++ 14, 158 Bytes

#include <algorithm>
#include <random>
[](int*a,int s){std::random_device r;for(std::knuth_b g(r());!std::is_sorted(a,a+s);std::shuffle(a,a+s,g));return a;};

Jelly , 6 Bytes, Sprachnachstellung

ẊŒ¿’$¿

Probieren Sie es online!

Erläuterung

ẊŒ¿’$¿
     ¿  While
 Œ¿’$     the input is not in its earliest possible permutation (i.e. sorted)
Ẋ       shuffle it

Œ¿weist jeder Permutation einer Liste eine Nummer zu; 1 ist sortiert, 2 hat die letzten beiden Elemente ausgetauscht usw., bis zur Fakultät der Listenlänge (die die Liste in umgekehrter Reihenfolge ist). Für eine sortierte Liste hat diese den Wert 1, und wir können sie mit dekrementieren ’, um einen "nicht sortierten" Test zu erstellen, der als Boolescher Wert in einer while-Schleifenbedingung verwendet werden kann. Das $ist auf Grund der Zustand als eine Gruppe zu analysieren.

Brachylog (v2), 5 Bytes, Sprachnachstellung

≤₁|ṣ↰

Probieren Sie es online!

Funktionsübergabe. (Die TIO-Verknüpfung verwendet ein Befehlszeilenargument, das eine Funktion automatisch in ein vollständiges Programm umschließt.)

Erläuterung

≤₁|ṣ↰
≤₁      Assert that {the input} is (nonstrictly) sorted in ascending order
  |     Output it
  |     Exception handler: if an assertion fails:
   ṣ      Randomly shuffle {the input}
    ↰     and run this function recursively on it, {outputting its output}

Prolog (die Sprache, in die Brachylog kompiliert) ist rekursiv, sodass diese Funktion in einer engen Schleife kompiliert wird.

C ++, 166 Bytes

Meh.

#import<algorithm>
#import<random>
#define r b.begin(),b.end()
template<class v>
v f(v b){auto a=std::mt19937();while(!std::is_sorted(r))std::shuffle(r,a);return b;}

Dies sollte für alle STL-Container mit begin()und funktionieren end().

Ungolfed:

#include <algorithm>
#include <random>
template <class v>
v f(v b) {
    auto a = std::mt19937();
    while (!std::is_sorted(b.begin(),b.end()))
        std::shuffle(b.begin(),b.end(),a);

    return b;
}

APL (Dyalog Extended) , 15 Byte

(?⍨∘≢⊇⊢)⍣{⍺≡∧⍺}

Probieren Sie es online!

Brachylog , 5 Bytes

∈&ṣ≤₁

Probieren Sie es online!

Als ich zum ersten Mal die Brachylog-Antwort von ais523 sah (im Gegensatz zu seiner Jelly-Antwort, denn wenn ich mich nicht irre, war user62131 auch er), fragte ich mich, was passiert, wenn Backtracking anstelle von Rekursion verwendet wird? Also versuchte ich es zuerst ṣ≤₁. Es stellt sich heraus, dass das Shuffle-Prädikat ṣnicht rückverfolgt werden kann, da die zufällige Auswahl von etwas weniger mehrere Ausgaben erzeugt, als dass es nur eine Ausgabe erzeugt, die nicht deterministisch ist. Wenn Sie das Glück haben, es richtig zu mischen, schlägt die Ausführung einfach fehl beim ersten versuch. Danach habe ich versucht pṣ≤₁, was die meiste Zeit funktioniert hat, aber da eine endlich lange Liste endlich viele Permutationen hat, ist sie manchmal immer noch nach dem Zufallsprinzip gescheitert. Nachdem ich das Ziel der Längenreduzierung aufgegeben hatte, kam ich zu folgendem Schluss:

         The input
∈        is an element of
         an unused implicit variable,
 &       and the input
  ṣ      shuffled randomly
   ≤₁    which is increasing
         is the output.

(Demonstration der Zufälligkeit)

Obwohl es tatsächlich etwas kürzer sein kann, wenn wir uns mit I / O ein paar Freiheiten nehmen ...

Brachylog , 4 Bytes

⊆ṣ≤₁

Probieren Sie es online!

Damit die Ausgabe nützlich ist, darf die Eingabe keine doppelten Elemente enthalten, da dieses falsche Prädikat zusätzlich zur Sortierung der Eingabe eine zufällige Anzahl doppelter Elemente und Nullen hinzufügt. (Hypothetisch könnte es alles ergänzen, aber es tut es einfach nicht.) Normalerweise würde ich nicht die Mühe machen, etwas zu erwähnen, das nicht richtig funktioniert, aber ich denke, es ist im Geiste der Herausforderung.

⊆        An ordered superset of the input
 ṣ       shuffled randomly
  ≤₁     which is increasing
         is the output.

Perl 6 , 28 Bytes

{({.pick(*)}...~.sort).tail}

Probieren Sie es online!

Anonymer Codeblock, der die Liste mischt, bis sie sortiert ist. Beachten Sie, dass die Liste mindestens einmal sortiert wird, was zulässig ist. Und nein, das {.pick(*)}kann man nicht ersetzen*.pick(*)

Pyth , 11 Bytes

Wn=Q.SQSQ;Q

Ziemlich zufrieden damit, kann wahrscheinlich ein bisschen mehr golfen werden

Erläuterung

Wn=Q.SQSQ;Q
W    While
  =Q.SQ    Variable Q (input variable) shuffled 
 n  Does not equal
       SQ    Variable Q sorted
             ;  Do nothing (loop ends)
              Q    And output variable Q

Probieren Sie es online!

Japt , 11 9 Bytes

_eZñ}a@öx

Versuch es

_eZñ}a@öx     :Implicit input of array U
_             :Function taking an array as argument via parameter Z
 e            :  Test Z for equality with
  Zñ          :  Z sorted
    }         :End function
     a        :Repeat and return the first result that returns true
      @       :Run this function each time and pass the result to the first function
       öx     :  Random permutation of U

C (203 Zeichen, keine Eingabeschleife: nur die Funk)

#include <stdio.h>
#define P (int*a,int n){
#define F for(i=0;i<n;i++){
int i,j,v;s P F if(a[i]>a[i+1])return 0;}return 1;}void h P F v=a[i];a[i]=a[j=rand()%n];a[j]=v;}}void b P while(!s(a,n-1))h(a,n);}

Dies ist dasselbe wie im Folgenden, wo wir auch das Array von stdin lesen und das sortierte Array ausschreiben. Da hat der Q nach der Funktion gefragt und nicht ein ganzes Programm ...

C (296 Zeichen)

#include <stdio.h>
#define P (int*a,int n){
#define F for(i=0;i<n;i++){
int i,j,n,v,x[999];s P F if(a[i]>a[i+1])return 0;}return 1;}void h P F j=rand()%n;v=a[i];a[i]=a[j];a[j]=v;}}void b P while(!s(a,n-1))h(a,n);}main(){while(scanf("%d",&v)==1)x[n++]=v;if(!s(x,n))b(x,n);F printf("%d\n",x[i]);}}

Das Kompilieren kann eine Warnung geben (implizite Deklarationen). Beschränkung der Größe des hartcodierten Arrays auf 999 Elemente. Zerbrechlich.

Wenn es nicht erforderlich ist, vorab zu prüfen, ob das Array sortiert ist, kann dies in 284 erfolgen.

C (251 Zeichen, war 284)

#include <stdio.h>
#define F for(i=0;i<n;i++){
int i,j,n,v,a[999];s(int n){F if(a[i]>a[i+1])return 0;}return 1;}void h(){F v=a[i];a[i]=a[j=rand()%n];a[j]=v;}}void b(){while(!s(n-1))h();}main(){while(scanf("%d",&a[n++])>0);b();F printf("%d\n",a[i]);}}

(Verwenden von Globalen anstelle von Funktionsargumenten).