Czy rozwiązywanie Sudoku jest zbyt trudne? Nawet wersja z brutalną siłą ? Oto ćwiczenie kodowania, które jest trochę łatwiejsze. Mam nadzieję. :-P

Napisz najkrótszą funkcję, aby zaimplementować bogosort. W szczególności twoja funkcja powinna:

• Weź tablicę (lub odpowiednik twojego języka) jako dane wejściowe
• Sprawdź, czy jego elementy są posortowane; jeśli tak, zwróć tablicę
• Jeśli nie, potasuj elementy i zacznij od nowa

Najkrótszy wpis wygrywa. W przypadku remisu preferowana jest funkcja obsługująca niestandardowy komparator (i / lub generator liczb pseudolosowych). Wszelkie pozostałe powiązania są rozwiązywane przez faworyzowanie wcześniejszego zgłoszenia.

Wyjaśnienia: Możesz użyć dowolnego typu elementu, o ile oczywiście istnieje sposób na ich zamówienie. Ponadto tasowanie musi być jednolite; nic z tego „po prostu posortuję to i nazwałbym to przetasowaniem”. :-)

APL (Dyalog), 20

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

Wyjaśnienie

⍵jest (prawy) argument
⍵≡⍵[⍋⍵]: sprawdza, czy ⍵posortowane jest ⍵samo
:⍵: Jeśli tak, to zwróć ⍵
∇⍵[?⍨⍴⍵]: W przeciwnym razie wygeneruj tablicę od 1 do ⍴⍵(długość ⍵) w kolejności losowej, uporządkuj ⍵zgodnie z tym ( ⍵[...]) i zastosuj do niej funkcję ( ∇)

Nagle przeglądam ten problem i ...

APL (Dyalog), 19

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

Samo myślenie o posortowaniu tablicy w czeku sprawia, że ​​jest to trochę bezcelowe (nie mówiąc, że Bogosort ma sens), byłaby bardziej dokładna implementacja ∧/2≤/⍵, a to bywa, że ​​obniża liczbę znaków.

Perl 6: 23 znaków

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

APL (22)

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

Stosowanie:

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

Wyjaśnienie:

• ⍋⍵: zwraca indeksy pozycji w posortowanej kolejności, więc ⍋30 10 20daje2 1 3
• (⍳X←⍴⍵)≡⍋⍵:⍵Zachowaj długość listy danych wejściowych w X. Jeśli zakres [1..X]jest równy posortowanej kolejności indeksu, lista jest sortowana, więc ją zwróć.
• ⋄∇⍵[X?X]: jeśli tak nie jest, powtórz z tasowaną tablicą.

Ruby - 33 znaki

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

Mathematica , 40 37

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

Z białymi znakami:

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

J - 34 27

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

na przykład:

f 5 4 1 3 2
1 2 3 4 5

f 'hello'
ehllo

Część {~? ~ @ # Tasuje dane wejściowe:

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

Python 61

Sortuje na miejscu.

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]

Inne odpowiedzi w Pythonie używają random.shuffle (). Dokumentacja losowego modułu python stwierdza:

Zauważ, że nawet dla dość małej wartości len (x) całkowita liczba permutacji x jest większa niż okres większości generatorów liczb losowych; oznacza to, że nigdy nie można wygenerować większości permutacji długiej sekwencji.

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 znaków)

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

Sortuje liczby całkowite w kolejności numerycznej. Zauważ, że rozwiązania rekurencyjne, takie jak

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

zawiedzie z powodu przepełnienia stosu nawet dla małych danych wejściowych (powiedzmy N> 5), ponieważ Python nie wykonuje optymalizacji wywołania ogona.

D bez niestandardowego komparatora: 59 znaków

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

Bardziej czytelnie:

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

    return r;
}

D z niestandardowym komparatorem: 69 znaków

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

Bardziej czytelnie:

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)

W Scali możemy sprawdzić, czy kompilator wykonał optymalizację wywołania ogona:

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

i tak się stało. Jednak w przypadku krótkiej listy 100 wartości:

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

zajęło prawie 4 miesiące. ;)

C # (184 znaki)

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();}

To nie jest naprawdę miłe robić to w C #. Musisz obsługiwać ogólne, aby obsługiwać zarówno typy wartości, jak i typy referencyjne. Nie ma funkcji losowej tablicy ani funkcji sprawdzającej, czy coś jest posortowane.

Czy ktoś ma jakieś wskazówki, aby to poprawić?

Edytuj wersję, która sortuje tylko int (134 znaki):

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 znaków

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

Po prostu ... stworzony dla zabawy.

Python - 61 znaków

Rekurencyjne

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

PowerShell , 85 82 56 55 52 bajtów

^{-26 bajtów dzięki sugestiom Mazzy
-1 bajtów dzięki AdmBorkBork
-3 bajtów dzięki mazzy}

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

Wypróbuj online!

PowerShell ma stosunkowo tanie porównanie tablic, rzutując je na łańcuchy i porównując.

Javascript 291 znaków

min

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 bajtów

Względnie proste podejście:

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

J, 22 bajty

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

Jest to rekurencyjna, milcząca monada wykorzystująca porządek obrad. Oto jak to działa:

Pozwól ynam być naszą listą. Po pierwsze, czasownik po prawej stronie porządku dziennego to -:/:~. To czasownik łaskawie podany przez Leaky Nun . Dopasowuje ( -:), czy dane wejściowe są sortowane ( /:~) za pomocą monadycznego haka. ( (f g) y = y f (g y)) Zwraca odpowiednio jeden lub zero. Po lewej stronie porządku dziennego znajduje się gerund dwóch czasowników: po prawej stronie jest czasownik tożsamości ], a po lewej następuje rekursja. Agenda wybiera albo czasownik tożsamości na pozycji, 1jeśli lista jest posortowana, a dłuższy czasownik na pozycji, 0jeśli lista nie jest posortowana.

$:@({~?~@#)wywołań $:(najdłuższy czasownik, w którym się znajduje) na szczycie wyniku {~?~@#on y. To przetasowuje listę, podobnie jak ?~@#permutacje długości y, będąc losowo posortowanymi wskaźnikami y. {~, w monadycznym haczyku, zwraca listę, z yktórej indeksów jest odpowiedni argument. Ta przetasowana lista jest następnie ponownie wywoływana z porządkiem obrad i powtarza się, aż zostanie posortowana.

C ++ 14, 158 bajtów

#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;};

Galaretka , 6 bajtów, wyzwanie dla postdate języka

ẊŒ¿’$¿

Wypróbuj online!

Wyjaśnienie

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

Œ¿przypisuje liczbę do każdej permutacji listy; 1 jest sortowane, 2 ma wymieniane dwa ostatnie elementy itd., Aż do silni długości listy (która jest listą w odwrotnej kolejności). Tak więc dla posortowanej listy ma ona wartość 1 i możemy ją zmniejszyć za pomocą ’w celu wygenerowania testu „nieposortowanego”, który można wykorzystać jako wartość logiczną w pętli while. Spowoduje $to, że warunek zostanie przeanalizowany jako grupa.

C ++, 166 bajtów

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;}

Powinno to działać na wszystkich kontenerach STL, które mają begin()i end().

Nie golfowany:

#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 bajtów

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

Wypróbuj online!

Brachylog , 5 bajtów

∈&ṣ≤₁

Wypróbuj online!

Kiedy po raz pierwszy zobaczyłem odpowiedź Brachylog ais523 (w przeciwieństwie do jego odpowiedzi Jelly, bo jeśli się nie mylę, użytkownik 62131 był również nim), zastanawiałem się, co by było, gdyby używał cofania zamiast rekurencji? Na początku próbowałem ṣ≤₁. Okazuje się, że ponieważ losowe wybranie czegoś nie daje wielu wyników, ponieważ powoduje tylko jedno wyjście w sposób nieokreślony, predykatu losowania ṣnie można cofnąć, więc uruchomienie nie powiedzie się, chyba że masz szczęście, aby to poprawnie przetasować za pierwszym razem. Potem próbowałem pṣ≤₁, co działało przez większość czasu, ale ponieważ skończona długa lista ma skończenie wiele permutacji, nadal czasami zawodziła losowo. Po porzuceniu celu zmniejszenia długości w końcu wpadłem na to:

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

(Demonstracja losowości)

Chociaż w rzeczywistości może być nieco krótszy, jeśli weźmiemy trochę wolności z I / O ...

Brachylog , 4 bajty

⊆ṣ≤₁

Wypróbuj online!

Aby dane wyjściowe były użyteczne, dane wejściowe nie mogą zawierać żadnych zduplikowanych elementów, ponieważ oprócz sortowania danych wejściowych ten predykat bogosort dodaje losową liczbę zduplikowanych elementów i zer. (Hipotetycznie może dodać wszystko, ale po prostu tak nie jest.) Zwykle nie zawracałbym sobie głowy wspominaniem czegoś tak dalekiego od prawidłowego funkcjonowania, ale czuję, że jest to zgodne z duchem wyzwania.

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

Perl 6 , 28 bajtów

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

Wypróbuj online!

Anonimowy blok kodu, który przetasowuje listę aż do jej posortowania. Pamiętaj, że sortuje listę co najmniej raz, co jest dozwolone. I nie, {.pick(*)}nie można tego zastąpić*.pick(*)

Pyth , 11 bajtów

Wn=Q.SQSQ;Q

Zadowolony z tego, prawdopodobnie można grać w golfa jeszcze trochę

Wyjaśnienie

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

Wypróbuj online!

Japt , 11 9 bajtów

_eZñ}a@öx

Spróbuj

_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

Brachylog (v2), 5 bajtów

≤₁|ṣ↰

Wypróbuj online!

Podanie funkcji. (Łącze TIO używa argumentu wiersza poleceń, który automatycznie pakuje funkcję w pełny program.)

Wyjaśnienie

≤₁|ṣ↰
≤₁      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 (język, w którym kompiluje się Brachylog) jest rekurencyjny, więc ta funkcja kończy się kompilacją w ciasną pętlę.

C (203 znaków, brak pętli wejściowej: tylko func)

#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);}

Jest to to samo co poniżej, w którym czytamy również tablicę ze standardowego wejścia i wypisujemy posortowaną tablicę. Ponieważ Q poprosił o funkcję, a nie cały program ...

C (296 znaków)

#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]);}}

Kompilacja może dać ostrzeżenie (niejawne deklaracje). Hardencoded limit rozmiaru tablicy 999 elementów. Kruchy.

jeśli nie ma potrzeby wstępnego sprawdzania, czy tablica jest posortowana, można to zrobić w 284.

C (251 znaków, było 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]);}}

(używając globali zamiast argumentów funkcji).