É resolver Sudoku muito difícil? Até a versão da força bruta ? Aqui está um exercício de codificação um pouco mais fácil. Eu espero. :-P

Escreva a função mais curta para implementar o bogosort. Especificamente, sua função deve:

• Pegue uma matriz (ou o equivalente do seu idioma) como entrada
• Verifique se seus elementos estão em ordem classificada; Nesse caso, retorne a matriz
• Caso contrário, embaralhe os elementos e comece novamente

A entrada mais curta vence. No caso de empate, é preferida uma função que suporte um comparador personalizado (e / ou gerador de números aleatórios pseudo). Quaisquer laços restantes são resolvidos favorecendo o envio anterior.

Esclarecimentos: Você pode usar qualquer tipo de elemento que desejar, desde que haja alguma maneira de solicitá-los, é claro. Além disso, o embaralhamento deve ser uniforme; nada disso "vou classificá-lo rapidamente e chamá-lo de embaralhado". :-)

APL (Dyalog), 20

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

Explicação

⍵é o argumento (à direita)
⍵≡⍵[⍋⍵]: verifica se a ⍵classificação é igual a ⍵si mesma
:⍵: se sim, retorne ⍵
∇⍵[?⍨⍴⍵]: Senão, gere uma matriz de 1 a ⍴⍵(comprimento de ⍵) em ordem aleatória, reordene de ⍵acordo com isso ( ⍵[...]) e aplique a função a ele ( ∇)

De repente, revisitando esse problema e ...

APL (Dyalog), 19

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

Só de pensar em classificar uma matriz na verificação torna-o meio inútil (sem dizer que o Bogosort é significativo), uma implementação mais precisa seria ∧/2≤/⍵e isso acontece para diminuir a contagem de caracteres.

Caracteres do Perl 6: 23

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

APL (22)

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

Uso:

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

Explicação:

• ⍋⍵: retorna os índices dos itens na ordem classificada, portanto ⍋30 10 20fornece2 1 3
• (⍳X←⍴⍵)≡⍋⍵:⍵Armazene o comprimento da lista de entrada em X. Se o intervalo [1..X]for igual à ordem de índice classificada, a lista é classificada, então retorne-a.
• ⋄∇⍵[X?X]: se não for esse o caso, recorra com a matriz aleatória.

Ruby - 33 caracteres

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

Mathematica , 40 37

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

Com espaço em branco:

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

J - 34 27

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

por exemplo:

f 5 4 1 3 2
1 2 3 4 5

f 'hello'
ehllo

A parte {~? ~ @ # Embaralha a entrada:

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

Python 61

Classifica no lugar.

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]

Outras respostas python usam random.shuffle (). A documentação do módulo aleatório python afirma:

Observe que, mesmo para len muito pequeno (x), o número total de permutações de x é maior que o período da maioria dos geradores de números aleatórios; isso implica que a maioria das permutações de uma longa sequência nunca pode ser gerada.

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 caracteres)

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

Classifica números inteiros em ordem numérica crescente. Observe que soluções recursivas, como

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

falhará devido ao estouro da pilha, mesmo para pequenas entradas (por exemplo, N> 5), porque o Python não faz otimização de chamada de cauda.

D sem comparador personalizado: 59 caracteres

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

Mais legivelmente:

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

    return r;
}

D com comparador personalizado: 69 caracteres

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

Mais legivelmente:

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)

No Scala, podemos verificar se o compilador fez uma otimização de chamada de cauda:

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

e sim, fez. No entanto, para uma lista curta de 100 valores:

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

demorou quase 4 meses para concluir. ;)

C # (184 caracteres)

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

Não é muito bom fazer isso em c #. Você precisa oferecer suporte a genéricos para oferecer suporte aos tipos de valor e referência. Não há função ou função de reprodução aleatória de matriz para verificar se algo está classificado.

Alguém tem alguma dica para melhorar isso?

Edite a versão que classifica apenas int (134 caracteres):

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 caracteres

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

Apenas .. feito por diversão.

Python - 61 caracteres

Recursivo

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

PowerShell , 85 82 56 55 52 bytes

^{-26 bytes graças às sugestões de mazzy
-1 byte graças a AdmBorkBork
-3 bytes graças a mazzy}

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

Experimente online!

O PowerShell tem uma comparação de matriz relativamente barata convertendo-a em cadeias e comparando isso.

Javascript 291 caracteres

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 bytes

Abordagem relativamente direta:

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

J, 22 bytes

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

Esta é uma mônada recursiva e tácita, usando uma agenda. Veja como funciona:

Vamos yser a nossa lista. Primeiro, o verbo à direita da agenda é -:/:~. Este é um verbo graciosamente fornecido por Leaky Nun . Corresponde a ( -:) se a entrada é ou não classificada ( /:~) usando um gancho monádico. ( (f g) y = y f (g y)) Isso retorna um um ou um zero de acordo. O lado esquerdo da agenda é um gerúndio de dois verbos: à direita está o verbo de identidade ]e à esquerda é o local onde ocorre a recursão. A agenda seleciona o verbo de identidade na posição 1se a lista estiver classificada e o verbo mais longo na posição 0se a lista não estiver classificada.

$:@({~?~@#)chama $:(o verbo mais longo em que está contido) sobre o resultado de {~?~@#on y. Isso embaralha a lista, conforme ?~@#as permutações do comprimento de y, sendo índices aleatoriamente ordenados de y. {~, em um gancho monádico, retorna uma lista ycujos índices são o argumento correto. Essa lista embaralhada é chamada novamente com a agenda e se repete até que seja classificada.

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

Geleia , 6 bytes, desafio de pós-datas de idiomas

ẊŒ¿’$¿

Experimente online!

Explicação

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

Œ¿atribui um número a cada permutação de uma lista; 1 é classificado, 2 tem os dois últimos elementos trocados, etc., até o fatorial do comprimento da lista (que é a lista na ordem inversa). Portanto, para uma lista classificada, ele tem o valor 1, e podemos diminuí-lo usando ’para produzir um teste "não classificado" que pode ser usado como um booleano em uma condição de loop while. O $objetivo é fazer com que a condição seja analisada como um grupo.

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

Isso deve funcionar em todos os contêineres STL que possuem begin()e 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 bytes

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

Experimente online!

Braquilog , 5 bytes

∈&ṣ≤₁

Experimente online!

Quando vi pela primeira vez a resposta Brachylog do ais523 (em oposição à sua resposta Jelly, porque se não me engano o user62131 também era ele), pensei: e se ele usasse retrocesso em vez de recursão? Então, no começo, eu tentei ṣ≤₁. Acontece que, como escolher algo aleatoriamente não produz várias saídas, mas produz apenas uma saída de forma não-determinística, o predicado de reprodução aleatória ṣnão pode ser retrocedido, portanto, executar isso simplesmente falhará a menos que você tenha sorte o suficiente para reproduzi-la corretamente. na primeira tentativa. Depois disso, tentei pṣ≤₁, o que funcionou na maior parte do tempo, mas como uma lista finitamente longa tem muitas permutações finitas, ela ainda falhava aleatoriamente às vezes. Depois de ter abandonado o objetivo de obter redução de comprimento, finalmente cheguei a isso:

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

(Demonstração de aleatoriedade)

Embora na verdade possa ser um pouco mais curto se tomarmos algumas liberdades com E / S ...

Braquilog , 4 bytes

⊆ṣ≤₁

Experimente online!

Para que a saída seja útil, a entrada não deve conter nenhum elemento duplicado, pois, além de classificar a entrada, esse predicado bogosort adiciona um número aleatório de elementos duplicados e zeros. (Hipoteticamente, poderia acrescentar algo, mas simplesmente não funciona.) Normalmente, eu não me incomodaria em mencionar algo tão longe de funcionar corretamente, mas acho que está no espírito do desafio.

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

Perl 6 , 28 bytes

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

Experimente online!

Bloco de código anônimo que embaralha a lista até que ela seja classificada. Observe que ele classifica a lista pelo menos uma vez, o que é permitido. E não, {.pick(*)}não pode ser substituído por*.pick(*)

Pitão , 11 bytes

Wn=Q.SQSQ;Q

Muito feliz com isso, provavelmente pode ser jogado um pouco mais

Explicação

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

Experimente online!

Japonês , 11 9 bytes

_eZñ}a@öx

Tente

_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

Braquilog (v2), 5 bytes

≤₁|ṣ↰

Experimente online!

Envio de função. (O link TIO usa um argumento de linha de comando que agrupa automaticamente uma função em um programa completo.)

Explicação

≤₁|ṣ↰
≤₁      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}

O prólogo (a linguagem na qual o Brachylog compila) é recursivo da cauda, ​​portanto, essa função acaba sendo compilada em um loop restrito.

C (203 caracteres, sem loop de entrada: apenas a função)

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

É o mesmo que se segue, onde também lemos a matriz do stdin e escrevemos a matriz classificada. Como o Q pediu a função e não um programa inteiro ...

C (296 caracteres)

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

A compilação pode dar aviso (declarações implícitas). Limite de tamanho de matriz com código rígido de 999 elementos. Frágil.

se não for necessário verificar previamente se a matriz está classificada, isso pode ser feito em 284.

C (251 caracteres, era 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]);}}

(usando globais em vez da função args).