Implementar Bogosort

29

¿ Resolver Sudoku es demasiado difícil? ¿Incluso la versión de fuerza bruta ? Aquí hay un ejercicio de codificación que es un poco más fácil. Espero. :-PAGS

Escriba la función más corta para implementar bogosort. En concreto, su función debería:

  • Tome una matriz (o el equivalente de su idioma) como entrada
  • Verifique si sus elementos están ordenados; si es así, devuelve la matriz
  • Si no, baraja los elementos y comienza de nuevo

La entrada más corta gana. En el caso de un empate, se favorece una función que admita un comparador personalizado (y / o un generador de números pseudoaleatorios). Cualquier vínculo restante se resuelve favoreciendo la presentación anterior.


Aclaraciones: puede usar cualquier tipo de elemento que desee, siempre que haya alguna forma de ordenarlos, por supuesto. Además, la mezcla debe ser uniforme; nada de este asunto de "lo ordenaré rápidamente y lo llamaré barajado" :-)

Chris Jester-Young
fuente
¿Cuáles son los tipos de elementos? int o cadenas?
Alexandru
@Alexandru: Cualquiera de los dos está bien. Tu eliges.
Chris Jester-Young
Agregar un comparador personalizado aumentará la longitud del código, por lo que una entrada ganadora no tendrá un comparador personalizado. Creo que romper el empate no tiene sentido.
Alexandru
1
Es posible que este algoritmo falle cuando se usa un generador pseudoaleatorio. Por ejemplo, cuando la longitud de la lista excede digamos 2000, ¡hay 2000! estados para la lista que pueden exceder el número de estados internos del prng.
gnibbler
2
Sí, la cita relevante de Wikipedia "Sin embargo, si se utiliza un generador de números pseudoaleatorios en lugar de una fuente aleatoria, es posible que nunca termine, ya que exhiben un comportamiento cíclico a largo plazo".
gnibbler

Respuestas:

8

APL (Dyalog), 20

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

Explicación

es el argumento (correcto)
⍵≡⍵[⍋⍵]: Comprueba si ordenado es igual a sí mismo
:⍵: en caso afirmativo, devuelve
∇⍵[?⍨⍴⍵]: De lo contrario, genera una matriz de 1 a ⍴⍵(longitud de ) en orden aleatorio, reordena de acuerdo con eso ( ⍵[...]) y aplica la función a él ( )


De repente revisando este problema y ...

APL (Dyalog), 19

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

Solo pensar en ordenar una matriz en el cheque lo hace algo inútil (sin decir que Bogosort es significativo), sería una implementación más precisa ∧/2≤/⍵, y eso pasa a reducir el recuento de caracteres.

TwiNight
fuente
15

Perl 6: 23 caracteres

@s.=pick(*)until[<=] @s
Ming-Tang
fuente
1
¿Es esta una función en perl? Se ve bien :)
Eelvex
1
Si no sabe, [<=]comprueba si una lista está ordenada: [<=] (1, 2, 3,) == (1 <= 2 <= 3) == (1 <= 2) and (2 <= 3)y .pick(n)elige n elementos aleatorios de una lista, y .pick(*)permite que Perl elija todos los elementos. use.perl.org/~masak/journal/40459
Ming-Tang
Esto debe ser Perl 6. Nunca he visto pickusado antes, y mucho menos [<=]. ¿En qué parte de la documentación están esos?
Sr. Llama
@GigaWatt Este es Perl 6 (no Perl 5). []es reducir operador que lleva al operador entre corchetes. Por ejemplo, [<=] 1, 2, 3es 1 <= 2 <= 3(y sí, haces rangos como este en Perl 6). En este caso, se usa para determinar si los elementos están en orden. .pick(*)El método baraja la lista ( pick(N)selecciona Nelementos de la lista). .=llama al método y asigna el resultado a la variable. En cuanto a la documentación, bueno, por ahora solo existe la especificación Perl 6: feather.perl6.nl/syn , pero existe.
Konrad Borowski
7

APL (22)

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

Uso:

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

Explicación:

  • ⍋⍵: devuelve los índices de los elementos en orden, por lo que ⍋30 10 20da2 1 3
  • (⍳X←⍴⍵)≡⍋⍵:⍵Almacene la longitud de la lista de entrada en X. Si el rango [1..X]es igual al orden de índice ordenado, la lista se ordena, así que devuélvala.
  • ⋄∇⍵[X?X]: si este no es el caso, recurse con una matriz aleatoria.
marinus
fuente
7

Ruby - 33 caracteres

g=->l{l.shuffle!!=l.sort ?redo:l}
Nemo157
fuente
1 char menos:g=proc{|l|0until l.sort==l.shuffle!}
AShelly
@ AShelly, tu versión no funciona. Mi versión (5 caracteres menos) f=->l{l.sort!=l.shuffle!?redo:l}(Ruby 1.9)
Hauleth
¿Alguien puede explicarme por qué redofunciona con un procmétodo clásico pero no con def...end? Pensé que redosolo funciona con bucles?
Patrick Oscity
1
Ok, no importa, encontré algo en el libro 'El lenguaje de programación de Ruby': " redo[...] transfiere el control al principio del proceso o lambda". Simplemente es así.
Patrick Oscity
6

Mathematica , 40 37

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

Con espacios en blanco:

NestWhile[RandomSample, #, Sort@# != # &] &
Señor mago
fuente
Si ignora los errores, puede guardar tres bytes con#//.l_/;Sort@l!=l:>RandomSample@l&
Martin Ender
13sh bytes en Mthmca.
Michael Stern
5

J - 34 27

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

p.ej:

f 5 4 1 3 2
1 2 3 4 5

f 'hello'
ehllo

La parte {~? ~ @ # Baraja la entrada:

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

Python 61

Se ordena en su lugar.

import random
def f(l):
 while l!=sorted(l):random.shuffle(l)
Alexandru
fuente
Su función no devuelve la matriz en caso de éxito.
hallvabo 03 de
Se ordena en su lugar. La matriz pasada se modifica.
Alexandru
Sin embargo, la pregunta dice que se supone que la función debe devolver la matriz, incluso si no es técnicamente necesario para obtener el resultado.
Jonathan M Davis
1
from random import*puede guardar un char.
ugoren
1
Es posible que esto no siempre funcione: (de la documentación del módulo aleatorio de Python): "Tenga en cuenta que, incluso para len (x), el número total de permutaciones de x es mayor que el período de la mayoría de los generadores de números aleatorios; esto implica que la mayoría de las permutaciones de nunca se puede generar una secuencia larga ".
Matt
3

Python 94

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

Otras respuestas de Python usan random.shuffle (). La documentación del módulo aleatorio python establece:

Tenga en cuenta que incluso para len bastante pequeño (x), el número total de permutaciones de x es mayor que el período de la mayoría de los generadores de números aleatorios; Esto implica que la mayoría de las permutaciones de una secuencia larga nunca se pueden generar.

Mate
fuente
Haz una lambda en su lugar; Creo que sería más corto. También tenga en cuenta que puede hacer return[x...lo contrario return [x.... Lo mismo con permutations(a) if- podría ser permutations(a)if.
0WJYxW9FMN
lambda a: [x for x in __import__("itertools").permutations(a) if x==tuple(sorted(a))][0]es 88 bytes
famoso1622
3

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"
tmartin
fuente
2

Python (69 caracteres)

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

Ordena enteros en orden numérico creciente. Tenga en cuenta que las soluciones recursivas, como

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

fallará debido al desbordamiento de la pila incluso para entradas pequeñas (digamos N> 5), porque Python no hace la optimización de llamadas de cola.

hallvabo
fuente
2

D sin comparador personalizado: 59 caracteres

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

Más legible:

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

    return r;
}

D con comparador personalizado: 69 caracteres

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

Más legible:

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

    return r;
}
Jonathan M Davis
fuente
2

Scala 73:

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

En Scala, podemos verificar si el compilador hizo una optimización de cola:

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

Y sí, lo hizo. Sin embargo, para una lista corta de 100 valores:

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

tardó casi 4 meses en completarse. ;)

usuario desconocido
fuente
2

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

No es realmente bueno hacer esto en C #. Debe admitir genéricos para admitir tanto los tipos de valor como los de referencia. No hay una función de arrastre aleatorio o función para verificar si algo está ordenado.

¿Alguien tiene algún consejo para mejorar esto?

Editar versión que solo clasifica 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();}
JJoos
fuente
2

GNU / BASH 65

b(){ IFS=$'\n';echo "$*"|sort -C&&echo "$*"||b $(shuf -e "$@");}
kojiro
fuente
Hmm, ¿puedo obtener una excepción especial para devolver la regla de matriz ya que las funciones bash solo pueden devolver literalmente un byte sin signo?
kojiro
2

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

Solo ... hecho por diversión.


fuente
1
std :: random_shuffle no es uniforme. En las aclaraciones se dice: "Además, la mezcla debe ser uniforme"
STDQ
Está bien ... no sabía que no era uniforme.
Se basa en rand (), que no es uniforme; vea open-std.org/jtc1/sc22/wg21/docs/papers/2014/n3924.pdf . Parece que no hay muchas otras personas que sigan, así que supongo que no es gran cosa.
STDQ
Entonces, si uso uno completamente aleatorio como usar srand (time (0)), ¿entonces cuenta?
El problema es que no se garantiza que rand tenga una buena calidad de números aleatorios y mucho menos uniformidad, algunos producen bits no aleatorios de bajo orden. Supongo que al final no importa ni debería importar. Solo obtuve 8 bytes más usando un distribuidor uniforme con std :: shuffle y demás, lo suficientemente bueno para mí.
STDQ
2

Python - 61 caracteres

Recursivo

from random import*;f=lambda l:l==sorted(l)or shuffle(l)>f(l)
gnibbler
fuente
Su función devuelve Verdadero o Falso, no la matriz.
hallvabo 03 de
2
También tenga en cuenta que las soluciones recursivas están condenadas al fracaso incluso para entradas pequeñas.
hallvabo
1
@hallvabo: De hecho, quiero escribir una solución recursiva de cola en Scheme, que por supuesto no agotará su pila.
Chris Jester-Young
@hallvabo, Alexandru ya había hecho la solución obvia de Python, así que solo buscaba algo diferente aquí. Por supuesto, la solución recursiva es solo por diversión y no un competidor serio
gnibbler
from random import*podría ser más corto
0WJYxW9FMN
2

PowerShell , 85 82 56 55 52 bytes

-26 bytes gracias a las sugerencias de mazzy
-1 byte gracias a AdmBorkBork
-3 bytes gracias a mazzy

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

Pruébalo en línea!

PowerShell tiene una comparación de matriz relativamente barata al convertirlos en cadenas y comparar eso.

Veskah
fuente
2
Mueva su paraminicialización a su forinicialización para guardar un byte -for($l=$args;
AdmBorkBork
1
bonito. -neconvierte el operador derecho en un tipo escalar del operador izquierdo. por lo tanto, puede guardar algunos bytes: ¡ Pruébelo en línea!
mazzy
1

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;
}
Profesor Allman
fuente
Tengo la sensación de haber dicho esto antes, pero puedes eliminar todos los varmensajes. Simplemente conviértalos en globales implícitos, se trata de hacer que el código sea lo más breve posible.
gcampbell
1

Matlab, 59 bytes

Enfoque relativamente sencillo:

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

J, 22 bytes

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

Esta es una mónada recursiva y tácita que usa una agenda. Así es como funciona:

Deja que ysea ​​nuestra lista. Primero, el verbo a la derecha de la agenda es -:/:~. Este es un verbo proporcionado gentilmente por Leaky Nun . Coincide ( -:) si la entrada está ordenada o no ( /:~) usando un gancho monádico. ( (f g) y = y f (g y)) Esto devuelve uno o cero en consecuencia. El lado izquierdo de la agenda es un gerundio de dos verbos: a la derecha está el verbo de identidad ], y a la izquierda es donde tiene lugar la recursión. La agenda selecciona el verbo de identidad en la posición 1si la lista está ordenada y el verbo más largo en la posición 0si la lista no está ordenada.

$:@({~?~@#)llamadas $:(el verbo más largo que contiene) encima del resultado de {~?~@#on y. Esto baraja la lista, ya que ?~@#toma las permutaciones de la longitud de los yíndices, que se ordenan aleatoriamente y. {~, en un gancho monádico, devuelve una lista de ycuyos índices son el argumento correcto. Esta lista aleatoria se vuelve a llamar con la agenda y se repite hasta que se ordena.

Conor O'Brien
fuente
1

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;};
STDQ
fuente
1

Jelly , 6 bytes, desafío de postdates de idioma

ẊŒ¿’$¿

Pruébalo en línea!

Explicación

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

Œ¿asigna un número a cada permutación de una lista; 1 está ordenado, 2 tiene los dos últimos elementos intercambiados, etc., hasta el factorial de la longitud de la lista (que es la lista en orden inverso). Por lo tanto, para una lista ordenada, tiene el valor 1, y podemos disminuirla usando para producir una prueba "no ordenada" que se pueda usar como booleana en una condición de bucle while. El $es hacer que la condición se analice como un grupo.


fuente
1

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

Esto debería funcionar en todos los contenedores STL que tienen begin()yend() .

Sin 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;
}
qookie
fuente
1

Brachylog , 5 bytes

∈&ṣ≤₁

Pruébalo en línea!

Cuando vi por primera vez la respuesta de Brachylog de ais523 (a diferencia de su respuesta de Jelly, porque si no me equivoco, el usuario62131 también era él), me preguntaba, ¿qué pasaría si usara retroceso en lugar de recursión? Así que al principio lo intenté ṣ≤₁. Resulta que, dado que elegir algo al azar no produce múltiples salidas, sino que solo produce una salida de forma no determinista, el predicado aleatorio no se puede rastrear, por lo que ejecutarlo simplemente fallará a menos que tenga la suerte de mezclarlo correctamente en el primer intento. Después de eso, lo intenté pṣ≤₁, lo que funcionó la mayor parte del tiempo, pero dado que una lista finitamente larga tiene muchas permutaciones, a veces todavía falla al azar. Después de haber abandonado el objetivo de lograr la reducción de longitud, finalmente se me ocurrió esto:

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

(Demostración de aleatoriedad)

Aunque en realidad puede ser un poco más corto si nos tomamos algunas libertades con E / S ...

Brachylog , 4 bytes

⊆ṣ≤₁

Pruébalo en línea!

Para que la salida sea útil, la entrada no debe contener elementos duplicados, porque además de ordenar la entrada, este predicado bogosort agrega un número aleatorio de elementos duplicados y ceros. (Hipotéticamente, podría agregar cualquier cosa, pero simplemente no lo hace). Por lo general, no me molestaría en mencionar algo que está lejos de funcionar correctamente, pero siento que está en el espíritu del desafío.

⊆        An ordered superset of the input
 ṣ       shuffled randomly
  ≤₁     which is increasing
         is the output.
Cadena no relacionada
fuente
1

Perl 6 , 28 bytes

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

Pruébalo en línea!

Bloque de código anónimo que baraja la lista hasta que se ordena. Tenga en cuenta que ordena la lista al menos una vez, lo cual está permitido. Y no, {.pick(*)}no se puede reemplazar con*.pick(*)

Jo King
fuente
1

Pyth , 11 bytes

Wn=Q.SQSQ;Q

Bastante contento con esto, probablemente se pueda jugar un poco más al golf

Explicación


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

Pruébalo en línea!

EdgyNerd
fuente
Puede acortar =Q.SQa =.SQ-1 byte (también funciona con otros operadores, como =QhQ-> =hQ)
ar4093
1

Japt , 11 9 bytes

_eZñ}a@öx

Intentalo

_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
Lanudo
fuente
1

Brachylog (v2), 5 bytes

≤₁|ṣ↰

Pruébalo en línea!

Presentación de funciones. (El enlace TIO utiliza un argumento de línea de comandos que envuelve automáticamente una función en un programa completo).

Explicación

≤₁|ṣ↰
≤₁      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 (el lenguaje en el que se compila Brachylog) es recursivo en la cola, por lo que esta función termina siendo compilada en un ciclo cerrado.

ais523
fuente
0

C (203 caracteres, sin bucle de entrada: solo el 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);}

Esto es lo mismo que lo siguiente, donde también leemos la matriz de stdin y escribimos la matriz ordenada. Dado que la Q solicitó la función y no un programa completo ...

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

La compilación puede dar advertencia (declaraciones implícitas). Límite de tamaño de matriz codificada de 999 elementos. Frágil.

Si no es necesario verificar previamente si la matriz está ordenada, se puede hacer en 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 globales en lugar de argumentos de función).

ShinTakezou
fuente