La résolution du Sudoku est-elle trop difficile? Même la version brute force ? Voici un exercice de codage un peu plus simple. J'espère. :-P

Écrivez la fonction la plus courte pour implémenter bogosort. En particulier, votre fonction devrait:

• Prenez un tableau (ou l'équivalent de votre langue) comme entrée
• Vérifiez si ses éléments sont triés; si oui, retournez le tableau
• Sinon, mélangez les éléments et recommencez

L'entrée la plus courte gagne. En cas d'égalité, une fonction prenant en charge un comparateur personnalisé (et / ou un générateur de nombres pseudo-aléatoires) est privilégiée. Tout lien restant est résolu en favorisant la soumission antérieure.

Clarifications: Vous pouvez utiliser n'importe quel type d'élément que vous voulez, tant qu'il existe un moyen de les commander, bien sûr. De plus, le brassage doit être uniforme; rien de tout cela "je vais simplement le trier rapidement et l'appeler mélangé". :-)

APL (Dyalog), 20

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

Explication

⍵est l'argument (à droite)
⍵≡⍵[⍋⍵]: vérifie si le ⍵tri est égal à ⍵lui
:⍵- même : si oui, alors retournez ⍵
∇⍵[?⍨⍴⍵]: sinon, générez un tableau de 1 à ⍴⍵(longueur de ⍵) dans un ordre aléatoire, réorganisez-le en ⍵fonction de cela ( ⍵[...]) et appliquez-lui la fonction ( ∇)

Revoir soudain ce problème et ...

APL (Dyalog), 19 ans

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

Penser simplement à trier un tableau dans le chèque le rend un peu inutile (ne pas dire que Bogosort est significatif), une implémentation plus précise serait ∧/2≤/⍵, et cela arrive à réduire le nombre de caractères.

Perl 6: 23 caractères

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

APL (22)

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

Usage:

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

Explication:

• ⍋⍵: renvoie les index des éléments dans l'ordre trié, ⍋30 10 20donne donc2 1 3
• (⍳X←⍴⍵)≡⍋⍵:⍵Stockez la longueur de la liste d'entrée dans X. Si la plage [1..X]est égale à l'ordre d'index trié, la liste est triée, alors renvoyez-la.
• ⋄∇⍵[X?X]: si ce n'est pas le cas, recurse avec un tableau mélangé.

Ruby - 33 caractères

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

Mathematica , 40 37

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

Avec espace:

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

J - 34 27

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

par exemple:

f 5 4 1 3 2
1 2 3 4 5

f 'hello'
ehllo

La partie {~? ~ @ # Mélange la saisie:

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

Python 61

Trie en place.

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]

D'autres réponses en python utilisent random.shuffle (). La documentation du module aléatoire python indique:

Notez que même pour un len (x) assez petit, le nombre total de permutations de x est plus grand que la période de la plupart des générateurs de nombres aléatoires; cela implique que la plupart des permutations d'une longue séquence ne peuvent jamais être générées.

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 caractères)

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

Trie les entiers dans l'ordre numérique croissant. Notez que les solutions récursives, comme

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

échouera en raison d'un débordement de pile, même pour de petites entrées (disons N> 5), car Python ne fait pas d'optimisation d'appel de fin.

D sans comparateur personnalisé: 59 caractères

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

Plus lisiblement:

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

    return r;
}

D avec comparateur personnalisé: 69 caractères

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

Plus lisiblement:

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)

Dans Scala, nous pouvons vérifier si le compilateur a fait une optimisation d'appel final:

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

et oui, il l'a fait. Cependant, pour une courte liste de 100 valeurs:

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

a pris près de 4 mois pour terminer. ;)

C # (184 caractères)

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

Ce n'est pas vraiment sympa de faire ça en C #. Vous devez prendre en charge les génériques pour prendre en charge les types de valeur et de référence. Il n'y a pas de fonction de lecture aléatoire de tableau ou de fonction pour vérifier si quelque chose est trié.

Quelqu'un a-t-il des conseils pour améliorer cela?

Modifier la version qui ne trie que l'int (134 caractères):

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 caractères

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

Juste .. fait pour le plaisir.

Python - 61 caractères

Récursif

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

PowerShell , 85 82 56 55 52 octets

^{-26 octets grâce aux suggestions
de mazzy -1 octet grâce à AdmBorkBork
-3 octets grâce à mazzy}

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

Essayez-le en ligne!

PowerShell propose une comparaison de tableaux relativement bon marché en les convertissant en chaînes et en les comparant.

Javascript 291 caractères

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 octets

Approche relativement simple:

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

J, 22 octets

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

Il s'agit d'une monade récursive et tacite utilisant un agenda. Voici comment cela fonctionne:

Soit ynotre liste. Tout d'abord, le verbe à droite de l'ordre du jour est -:/:~. C'est un verbe gracieusement fourni par Leaky Nun . Il correspond à ( -:) que l'entrée soit triée ( /:~) ou non à l' aide d'un crochet monadique. ( (f g) y = y f (g y)) Cela renvoie un un ou un zéro en conséquence. Le côté gauche de l'agenda est un gérondif de deux verbes: à droite se trouve le verbe d'identité ], et à gauche se trouve la récurrence. L'agenda sélectionne soit le verbe d'identité en position 1si la liste est triée, soit le verbe plus long en position 0si la liste n'est pas triée.

$:@({~?~@#)appelle $:(le verbe le plus long dans lequel il se trouve) au sommet du résultat de {~?~@#on y. Cela mélange la liste, tout comme ?~@#les permutations de la longueur de y, étant des indices triés au hasard de y. {~, dans un crochet monadique, renvoie une liste ydont les indices sont l'argument de droite. Cette liste mélangée est ensuite rappelée avec l'ordre du jour et répétée jusqu'à ce qu'elle soit triée.

C ++ 14, 158 octets

#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 octets, défi de postdates de langue

ẊŒ¿’$¿

Essayez-le en ligne!

Explication

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

Œ¿attribue un numéro à chaque permutation d'une liste; 1 est trié, 2 a les deux derniers éléments échangés, etc., jusqu'à la factorielle de la longueur de la liste (qui est la liste dans l'ordre inverse). Ainsi, pour une liste triée, celle-ci a la valeur 1, et nous pouvons la décrémenter en utilisant ’afin de produire un test "non trié" utilisable comme booléen dans une condition de boucle while. Le $est de provoquer l'analyse de la condition en tant que groupe.

C ++, 166 octets

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

Cela devrait fonctionner sur tous les conteneurs STL qui ont begin()et end().

Non golfé:

#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 octets

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

Essayez-le en ligne!

Brachylog , 5 octets

∈&ṣ≤₁

Essayez-le en ligne!

Quand j'ai vu pour la première fois la réponse Brachylog de ais523 (par opposition à sa réponse Jelly, parce que si je ne me trompe pas, l'utilisateur 62131 était aussi lui), je me suis demandé, et s'il utilisait le retour arrière au lieu de la récursivité? Alors au début, j'ai essayé ṣ≤₁. Il s'avère que choisir quelque chose au hasard ne produit pas plusieurs sorties autant qu'il ne produit qu'une seule sortie de manière non déterministe, le prédicat de shuffle ṣne peut pas être inversé, donc l'exécution qui échouera simplement à moins que vous n'ayez la chance de le mélanger correctement du premier coup. Après cela, j'ai essayé pṣ≤₁, ce qui fonctionnait la plupart du temps, mais comme une liste finement longue a fini de nombreuses permutations, elle échouait parfois au hasard parfois. Après avoir abandonné l'objectif de réduction de la longueur, j'ai finalement trouvé ceci:

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

(Démonstration de l'aléatoire)

Bien que cela puisse être un peu plus court si nous prenons quelques libertés avec les E / S ...

Brachylog , 4 octets

⊆ṣ≤₁

Essayez-le en ligne!

Pour que la sortie soit utile, l'entrée ne doit contenir aucun élément en double, car en plus de trier l'entrée, ce prédicat de bogosort ajoute un nombre aléatoire d'éléments en double et de zéros. (Hypothétiquement, cela pourrait ajouter quelque chose, mais ce n'est pas le cas.) Normalement, je ne prendrais pas la peine de mentionner quelque chose de si loin de fonctionner correctement, mais je pense que c'est dans l'esprit du défi.

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

Perl 6 , 28 octets

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

Essayez-le en ligne!

Bloc de code anonyme qui mélange la liste jusqu'à ce qu'elle soit triée. Notez qu'il trie la liste au moins une fois, ce qui est autorisé. Et non, le {.pick(*)}ne peut pas être remplacé par*.pick(*)

Pyth , 11 octets

Wn=Q.SQSQ;Q

Assez content de cela, peut probablement être joué un peu plus

Explication

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

Essayez-le en ligne!

Japt , 11 9 octets

_eZñ}a@öx

Essayez-le

_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 octets

≤₁|ṣ↰

Essayez-le en ligne!

Soumission de fonction. (Le lien TIO utilise un argument de ligne de commande qui encapsule automatiquement une fonction dans un programme complet.)

Explication

≤₁|ṣ↰
≤₁      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 (le langage dans lequel Brachylog compile) est récursif en queue, donc cette fonction finit par être compilée en une boucle serrée.

C (203 caractères, pas de boucle d'entrée: uniquement la fonction)

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

C'est la même chose que la suivante, où nous lisons également le tableau à partir de stdin et écrivons le tableau trié. Depuis que le Q a demandé la fonction et non un programme entier ...

C (296 caractères)

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

La compilation peut donner un avertissement (déclarations implicites). Limite de taille de tableau codée en dur de 999 éléments. Fragile.

s'il n'est pas nécessaire de pré-vérifier si le tableau est trié, cela peut être fait en 284.

C (251 caractères, 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]);}}

(en utilisant des globaux au lieu d'arguments de fonction).