Ordenar por Bozos

8

Introducción

Este desafío se trata de tres (malos) algoritmos de clasificación: Bogosorty otras dos variantes que se me ocurrieron (pero probablemente otros han pensado en algún momento): Bogoswap(AKA Bozosort) y Bogosmart.

Bogosortfunciona barajando completamente la matriz al azar y verificando si se ordena (ascendente). Si no, repite.

Bogoswapfunciona seleccionando dos elementos, aleatoriamente, e intercambiándolos. Repita hasta que esté ordenado (ascendente).

Bogosmartfunciona seleccionando dos elementos, aleatoriamente, y solo intercambiándolos si hace que la matriz esté más cerca de ser ordenada (ascendente), es decir. si el elemento con el índice más bajo era originalmente más grande que el que tenía el índice más alto. Repita hasta que esté ordenado.

El reto

Este desafío explora la eficiencia (o falta de) de cada uno de estos tres algoritmos de clasificación. El código de golf será

  1. generar una matriz aleatoria de 8 elementos de los enteros 1-8 inclusive (sigue leyendo para ver cómo debes hacer esto);

  2. aplicar cada algoritmo a esta matriz; y

  3. muestra la matriz original, seguida del número de cálculos necesarios para cada algoritmo, separados por un espacio (espacio final, ok), en el formato <ARRAY> <BOGOSORT> <BOGOSWAP> <BOGOSMART>.

El programa producirá 10 casos de prueba; puede generar los diez al principio o generar uno a la vez, lo que sea. Ejemplo de salida a continuación.

Detalles:

Para Bogosort, debe registrar el número de veces que se barajó la matriz.

Para Bogoswap, debe registrar el número de intercambios realizados.

Para Bogosmart, debe registrar el número de intercambios realizados.

Salida de ejemplo:

87654321 1000000 100 1
37485612 9050000 9000 10
12345678 0 0 0 
28746351 4344 5009 5
18437256 10000 523 25
15438762 10000 223 34
18763524 58924 23524 5
34652817 9283 21 445
78634512 5748 234 13
24567351 577 24 34

Yo inventé estos números; por supuesto, su programa imprimirá diferentes resultados pero en el mismo formato.

Reglas

  • Toda aleatoriedad utilizada en su programa debe provenir de generadores de números pseudoaleatorios disponibles para usted, y de lo contrario no deben ser ampliamente calculados por usted. No tienes que preocuparte por las semillas.
  • No hay límite de tiempo en los programas.
  • Las matrices se deben clasificar de forma ascendente.
  • Los espacios finales o una nueva línea adicional no son gran cosa.
  • Para Bogosort, la matriz se baraja utilizando cualquier algoritmo de barajado imparcial como Fisher-Yates o Knuth Shuffling , especificado explícitamente en su explicación. Los métodos de barajado integrados no están permitidos. Genere sus matrices de prueba de la misma manera.
  • Si después de barajar o cambiar la matriz sigue siendo la misma, todavía cuenta y debe incluirse en la cuenta del programa. Por ejemplo, barajar la matriz a sí mismo por coincidencia cuenta como una combinación aleatoria, e intercambiar un elemento consigo mismo cuenta como un intercambio, aunque ninguna de estas operaciones cambie la matriz.
  • Si mi memoria me sirve correctamente, una matriz de 8 elementos no debería llevar mucho tiempo para ninguno de los tres algoritmos. De hecho, creo que algunas veces para una matriz de 10 elementos, cuando lo probé,Bogoswap solo requería unos pocos miles (o menos) de barajaduras reales y bastante menos de 10 segundos.
  • Su código debe ordenar los arreglos, no solo dé los valores esperados o los cálculos matemáticos para una respuesta esperada.
  • Este es un desafío de código de golf, por lo que gana el programa más corto en bytes.

Aquí hay algunos pasos de muestra para cada algoritmo de clasificación:

BOGOSORT
56781234
37485612
28471653
46758123
46758123
12685734
27836451
12345678

BOGOSWAP
56781234
16785234
17685234
12685734
12685743
12685734
12485763
12385764
12385764
12345768
12345678

BOGOSMART
56781234
16785234
12785634
12785364
12785364
12385764
12385674
12345678

En este caso, el programa saldría 56781234 7 10 7y luego haría lo mismo 10 veces. No tiene que imprimir las matrices mientras se realiza la clasificación, pero le di los pasos de muestra anteriores para que pueda comprender cómo funciona cada algoritmo y cómo contar los cálculos.

Faraz Masroor
fuente
2
Hay 8! = 40,320 órdenes posibles para una matriz de 8 elementos. Mi matemática no es lo suficientemente buena como para traducir esto en el número esperado (promedio) de pasos de bogosort. Pero intuitivamente, debe estar al menos dentro de un orden de magnitud de ese número. Mi teoría es que bogosort y bogoswap requerirán el mismo número promedio de pasos. Solo ese paso de bogoswap es más barato, por lo que el tiempo será menor.
Reto Koradi
He hecho esto antes, y créeme, te sorprenderá lo diferentes que son tus pensamientos de la realidad. Descubrirá que, como era de esperar, Bogosort tiene la mayor cantidad de cálculos, luego sorprendentemente Bogoswap tiene una menor, y por supuesto Bogosmart toma aún menos. También te sorprenderá la cantidad de cálculos que Bogosort necesita, muy por debajo de 40320.
Faraz Masroor
En resumen, no espero que este desafío arruine su computadora o arruine su memoria.
Faraz Masroor
2
Relacionado. (Por la parte de barajar y Bogosort.)
Martin Ender
¿Podemos generar el número de pasos de la distribución matemáticamente correcta sin hacer la clasificación?
xnor

Respuestas:

3

Pyth, 62 60 bytes

VTjd[jkKJ=boO0=ZS8fqZ=KoO0K0fqZ=XJO.CJ2)0fqZ=Xb*>F=NO.Cb2N)0

Esto fue muy divertido. No estoy seguro de si esto es válido, probablemente estoy usando algunas lagunas no escritas.

Una salida de muestra sería:

23187456 22604 23251 110
42561378 125642 115505 105
62715843 10448 35799 69
72645183 7554 53439 30
61357428 66265 6568 77
62348571 1997 105762 171
78345162 96931 88866 241
17385246 51703 7880 80
74136582 36925 19875 100
26381475 83126 2432 25

Explicación:

Mi función aleatoria utiliza la función incorporada order-by. Básicamente, asigno a cada elemento de la lista un número aleatorio del intervalo [0-1)y clasifico la lista por ellos. Esto me da una mezcla aleatoria imparcial.

Bucle exterior

Al VTprincipio repite el siguiente código 10 veces.

Preparación

jkKJ=boO0=ZS8
           S8        create the list [1, 2, 3, 4, 5, 6, 7, 8]
         =Z          and store in Z
      oO0            shuffle
    =b               and store in b
   J                 and store in J
  K                  and store in K (3 copies of the same shuffled array)
jkK                  join K with ""

Bogosort

fqZ=KoO0K0 
     oO0K            shuffle K
   =K                and store the result in K
f        0           repeat ^ until:
 qZ K                  Z == K
                     and give the number of repeats

Bogoswap

fqZ=XJO.CJ2)0  
       .CJ2          give all possible pairs of elements of J
      O              take a random one
    XJ     )         swap these two elements in J
   =                 and store the result in J
f           0        repeat ^ until:
 qZ K                  Z == K
                     and give the number of repeats

Bogosmart

fqZ=Xb*>F=NO.Cb2N)0
            .Cb2     give all possible pairs of elements of b
           O         take a random one
         =N          assign it to N
       >F N          check if N[0] > N[1]
      *         N    multiply the boolean with N
    Xb           )   swap the two (or zero) values in b
   =                 and assign to b
f                 0  repeat ^ until:
 qZ                    Z == b
                     and give the number of repeats

Impresión

jd[
  [                  put all 4 values in a list
jd                    join by spaces and print
Jakube
fuente
=JXJO.cJ2)es lo mismo que =XJO.cJ2)- asignación aumentada. Lo mismo vale para =bXbmás tarde. Además, creo que se supone que los swaps tienen los pares elegidos con reemplazo ( .C)
isaacg
@isaacg Gracias, cosas corregidas. No estoy seguro si está permitido .co .Cno. Por ejemplo .C[3 1 2)2, no devuelve el par [2, 1]. Lo cual es una propiedad que estoy explotando en mi algoritmo.
Jakube
tal vez *JJentonces? También es un personaje más corto, lo cual es bueno.
isaacg
2

JavaScript ( ES6 ), 319 345

Como era de esperar, esto es bastante largo.

Para aleatorio aleatorio, créditos a @ core1024 (mejor que el mío para el mismo chellenge)

Pruebe a ejecutar el fragmento (Firefox solo como de costumbre)

// FOR TEST : redefine console
var console = { log: (...p)=>O.innerHTML += p.join(' ')+'\n' }
// END 

// Solution
R=n=>Math.random()*n|0, 
S=a=>(a.map((c,i)=>(a[i]=a[j=R(++i)],a[j]=c)),a), // shuffle
T=f=>{for(a=[...z];a.join('')!=s;)f(a)}, // apply sort 'f'  algorithm until sorted

s='12345678';
for(i=0;i<10;i++)
  z=S([...s]),
  n=l=m=0,
  T(a=>S(a,++n)),
  T(a=>(t=a[k=R(8)],a[k]=a[j=R(8)],a[j]=t,++m)),
  T(a=>(t=a[k=R(8)],u=a[j=R(8)],(t<u?j<k:k<j)&&(a[k]=u,a[j]=t,++l))),
  console.log(z.join(''),n,m,l)
<pre id=O></pre>

edc65
fuente
El enlace "Ejecutar fragmento de código" no funciona para mí. No estoy seguro de si es mi navegador / sistema, pero los enlaces de fragmentos me han funcionado en el pasado.
Reto Koradi
Igual, el fragmento de código no funciona en mi navegador
Faraz Masroor
2
@Reto et al EcmaScript 6: ejecutar solo en Firefox.
edc65