Generar un trastorno aleatorio.

30

Descripción del desafío

Un "trastorno" de una secuencia es una permutación donde ningún elemento aparece en su posición original. Por ejemplo, ECABDes un trastorno de ABCDE, pero CBEDAno es:

ABCDE
 | |   <- B and D are in their orignal positions
CBEDA

Dada una secuencia, genera un desorden aleatorio de la misma.

Notas

  • Puede tomar una cadena como entrada o una matriz / lista de elementos (enteros, caracteres, objetos ...)

  • En lugar de devolver un nuevo objeto, puede modificar uno existente intercambiando sus elementos

  • Cada trastorno debe tener la misma probabilidad de ser generado

  • Puede suponer que hay más de un elemento en la secuencia y ninguno aparece más de una vez

shooqie
fuente
44
¿Relacionado?
Addison Crump
3
@VoteToClose: jaja, totalmente reventado
shooqie
No sé mucho sobre todo esto, pero ¿está relacionado de alguna manera con el teorema del punto fijo ... según el cual las cosas siempre terminarán en su propia posición o algo así ...? Apuesto a que estoy equivocado, pero que alguien me corrija :)
Farhan Anam
¿Hay alguna garantía de que los elementos serán únicos o pueden contener duplicados?
Carcigenicate
1
@Carcigenicate: está justo ahí en la descripción; puede suponer que no hay duplicados
shooqie

Respuestas:

12

CJam , 14 bytes

q:X{mr_X.=:|}g

Pruébalo en línea!

Sigue barajando la entrada hasta que sea un trastorno.

Explicación

q:X   e# Read input and store it in X.
{     e# While the condition at the end of the loop is truthy...
  mr  e#   Shuffle the string.
  _X  e#   Duplicate it and push the input.
  .=  e#   Element-wise equality check.
  :|  e#   Reduce OR over the list, gives something truthy if any character
      e#   remained in its original position.
}g
Martin Ender
fuente
1
Ojalá OP hubiera especificado que las soluciones tendrían que garantizar que siempre terminen.
John Dvorak
44
@ JanDvorak Bueno, la probabilidad de que esto no termine es 0. Pero tienes razón en que requerir un tiempo de ejecución determinista habría hecho que el desafío fuera más interesante.
Martin Ender
¿Es la probabilidad realmente 0? La operación aleatoria no será perfecta, ¿cómo funciona realmente? Creo que esto probablemente es una buena aproximación de lo que solicitó el OP, pero dudo que las probabilidades de cada desorden sean las mismas (probablemente depende de algún valor inicial del PRNG que probablemente sea utilizado por la operación aleatoria).
Nadie
3
@ Nadie, dudo que pueda obtener resultados perfectamente uniformes de un PRNG utilizando cualquier algoritmo. Sin embargo, suponiendo que la barajadura en sí misma sea uniforme (que los documentos de Java garantizan con "Todas las permutaciones ocurren con aproximadamente la misma probabilidad"), una solución basada en rechazo también producirá alteraciones uniformes, porque cada alteración es una permutación, y cada una La permutación tiene la misma probabilidad.
Martin Ender
1
@ Nadie Math nerd aquí. Una condición que tiene éxito o falla se llama un ensayo de Bernoulli en estadísticas. Esto implica que la probabilidad de necesitar k pruebas para el primer éxito es (1 - p) ^ (k - 1) * p, donde p es la probabilidad de un trastorno exitoso. Es fácil ver que a medida que k se hace más grande, la probabilidad de necesitar k pruebas se vuelve muy pequeña. Por lo tanto, decimos que el algoritmo se detiene con probabilidad 1 ("casi seguro"), pero no es imposible que nunca se detenga.
maservant
9

Jalea , 6 bytes

Ẋ=³S$¿

Pruébalo en línea!

Explicación

Ẋ    ¿    Shuffle the given list while this is nonzero for it:
    $       A two-step process:
 =³           Element-wise equality of it and L (the original list)...
   S          Sum the ones in this binary array.

Jonathan Allan salvó un byte.

Lynn
fuente
55
Entonces, ¿tienes tu sombrero Winter Bash con anticipación? :-)
Luis Mendo
2
Es hora de dibujar una nueva imagen agradable, Ẋ=³S$¿ahorra un byte.
Jonathan Allan
2
Huh, nunca supe eso $. ¡Gracias!
Lynn
Son 6 caracteres, pero más de 6 bytes. Ẋ = ³S $ ¿las longitudes de bytes son: 312112. Entonces 10 bytes en total.
mxfh
6

Python, 85 bytes

Modifica la lista que se le pasa (permitido por meta y en la pregunta).

from random import*
def D(l):
 o=l[:]
 while any(x==y for x,y in zip(o,l)):shuffle(l)

Pruébelo en línea aquí!

FlipTack
fuente
1
Si especifica Python 2, creo que se podría reemplazar def D(l):con l=input()y luego guardar los espacios de sangría en las siguientes líneas (por lo que tiene un programa en lugar de una función). Sin embargo, ¡no voté en contra!
Mathmandan
@mathmandan es una buena idea, pero luego tendría que volver a imprimirlo si es un programa completo, que cuesta más bytes.
FlipTack
1
Bien si tú lo dices. Supongo que la especificación parecía estar diciendo que no tenía que imprimir o devolver el resultado, que tomar una lista [de la entrada del usuario] y barajarla sería suficiente. Pero es razonable leer "existente" como "existente antes de ejecutar cualquiera de sus códigos", en cuyo caso estoy de acuerdo con usted. (Tal vez hay un consenso bien establecido sobre esto.) :)
Mathmandan
5

ES6 (Javascript), 71, 69 bytes

La entrada y la salida son matrices, deberían funcionar con cualquier tipo de elemento (cadenas, números, etc.), siempre que puedan compararse con "==".

Golfed

F=s=>(r=[...s]).sort(_=>Math.random()-.5).some((e,i)=>s[i]==e)?F(s):r

Prueba

F=s=>(r=[...s]).sort(_=>Math.random()-.5).some((e,i)=>s[i]==e)?F(s):r

F(['A','B','C','D'])
Array [ "D", "C", "A", "B" ]

F(['A','B','C','D'])
Array [ "D", "A", "B", "C" ]

F(['A','B','C','D'])
Array [ "C", "D", "B", "A" ]

F(['A','B','C','D'])
Array [ "D", "C", "B", "A" ]

F(['A','B','C','D'])
Array [ "C", "D", "B", "A" ]

Fragmento interactivo

F=s=>(r=[...s]).sort(_=>Math.random()-.5).some((e,i)=>s[i]==e)?F(s):r

function G() {
    console.log(F(T.value.split``).join``); 
}
<input id=T value="ABCDEF"><button id=G onclick="G()">GENERATE</button>

zepelín
fuente
5

Perl 6 , 33 bytes

{first (*Zne$_).all,.pick(*)xx *}

Una lambda que toma una lista de enteros o caracteres como entrada y devuelve una nueva lista.

Si debe admitir listas de valores arbitrarios , nedebería reemplazarse por !eqv(+2 bytes).

( Pruébelo en línea )

Explicación:

  • { }: Define una lambda.
  • .pick(*): Genera un aleatorio aleatorio de la lista de entrada.
  • .pick(*) xx *: Crea una secuencia infinita perezosa de tales barajaduras.
  • (* Zne $_).all: Una lambda que comprime dos listas (su argumento *y el argumento de la lambda externa $_) con el neoperador (igualdad de cadena negativa), produciendo una lista de booleanos, y luego crea una allunión para colapsarlos a un solo estado booleano.
  • first PREDICATE, SEQUENCE: Toma el primer elemento de nuestra secuencia infinita de permutaciones que cumple con la prueba de "trastorno".
smls
fuente
4

Brachylog , 19 18 15 13 bytes

@~.:?z:#da;?&

Pruébalo en línea!

Explicación

@~.                Output is a shuffle of the input
  .:?z             Zip the output with the input
      :#da         All couples of integers of the zip must be different
          ;      Or
           ?&      Call recursively this predicate with the same input
Fatalizar
fuente
3

Perl 6 , 45 bytes

{(@^a,{[.pick(*)]}...{none @a Zeqv@$_})[*-1]}
{(@^a,{[.pick(*)]}...{!sum @a Zeqv@$_})[*-1]}

Intentalo

La entrada es una matriz de cualquier cosa.

Expandido:

{
  (

    @^a,          # declare parameter, and seed sequence generator

    {             # lambda with implicit parameter 「$_」
      [           # store into an array
        .pick(*)  # shuffle 「$_」
      ]
    }

    ...           # keep generating the sequence until

    {
      none        # none
      @a          # of the outer blocks input
      Z[eqv]      # is zip equivalent
      @$_         # with the current value being tested
    }

  )[ * - 1 ]      # return the last value
}
Brad Gilbert b2gills
fuente
3

MATL, 7 bytes

Esta es una traducción de mi publicación Octave (y similar a algunas de las otras presentaciones aquí). Publiqué mi primera publicación MATL ayer (crack CNR), así que supongo que esto no es óptimo, pero es lo mejor que tengo hasta ahora.

Para ser honesto, no estoy completamente seguro de que tsea ​​necesario, pero es la única forma en que puedo hacer que esto funcione. Se utiliza para poder comparar la entrada del usuario (recuperada con G), con la permutación aleatoria. Creo que podría comparar los dos sin él, pero ...?

De todos modos, aquí va:

`Z@tG=a

`          % Loop
 Z@        % Random permutation of input
   t       % Duplicating the stack
    G      % Paste from clipboard G (user input)
     =     % Comparing the random permutation with the input (retrieved from clipboard)
      a    % any(input == random permutation)
           % Implicit end and display

Pruébalo en línea!

Stewie Griffin
fuente
¿Alguna mejora? ¿Realmente necesito tallí o puedo deshacerme de él? Fue divertido intentar jugar al golf en MATL ... :)
Stewie Griffin
:-) No veo cómo deshacerme de eso t(o equivalentemente otro G) Necesitas dejar algo en la pila para la próxima iteración o como resultado final
Luis Mendo
3

En realidad , 13 bytes

;;WX╚│♀=ΣWX)X

Pruébalo en línea!

Explicación:

;;WX╚│♀=ΣWX)X
;;             make two copies of input
  WX╚│♀=ΣW     while top of stack is truthy:
   X             discard top of stack
    ╚            shuffle array
     │           duplicate entire stack
      ♀=         compare corresponding elements in shuffled and original for equality
        Σ        sum (truthy if any elements are in the same position, else falsey)
          X)X  discard everything but the derangement
Mego
fuente
2

Octava, 56 55 bytes

x=input('');while any(x==(y=x(randperm(nnz(x)))));end,y

Tenemos que usar input('')ya que esto no es una función. Además, dado que puedo elegir tener la entrada como una cadena, podemos usar el truco que nnz(x)==numel(x).

Explicación:

x=input('')            % Self-explanatory
while any(x==y)        % Loop until x==y has only 0s (i.e. no elements are equal)
y=x(randperm(nnz(x)))  % Continue to shuffle the indices and assign x(indices) to y
end                    % End loop
y                      % Display y

Gracias a Luis por notar que la entrada puede ser una cadena, por lo que podría usar en nnzlugar de numelguardar dos bytes.

Stewie Griffin
fuente
Nota personal: lea la pregunta completa la próxima vez :) ¡Gracias!
Stewie Griffin
1
Eso me pasa todo el tiempo :-)
Luis Mendo
2

MATL, 13 bytes

Este es un esfuerzo conjunto de @LuisMendo y yo. A diferencia de muchas otras respuestas aquí, esta es determinista en el sentido de que no muestrea permutaciones aleatorias hasta que obtiene un trastorno, pero genera todos los trastornos y elige uno aleatoriamente.

Y@tG-!Af1ZrY)

¡Pruébelo en línea!

Explicación

Y@tG-!Af1ZrY)
Y@             generate all permutatoins
  t            create a duplicate
   G-!A        find the (logical) indices of all valid derangements (where no character of the string is in the same position as the original string)
       f       convert logical to linear indices
        1Zr    choose one of those indices randomly
           Y)  get the derangement (from the ones we generated earlier) at this index
falla
fuente
2

Pyth - 10 9 bytes

Esto sigue barajando la entrada mientras cualquiera de los caracteres es igual a los caracteres en su índice en la entrada.

.WsqVHQ.S

Pruébelo en línea aquí .

.W           Iterate while
 s           Sum, this is works as any() on a boolean list
  qV         Vectorized equality
   H         The lambda variable for the check step
   Q         The input
 .S          Shuffle
  (Z)        Lambda variable, implicit
 (Q)         Start .W with input, implicit
Maltysen
fuente
¿Puedes por favor agregar una explicación? Quería escribir una respuesta pyth. No sé mucho al respecto.
Gurupad Mamadapur
@GurupadMamadapur seguro, también sería feliz.
Maltysen
1
@GurupadMamadapur agregado. Tenemos un tutorial . Está bastante desactualizado, pero le enseñará lo básico. Si necesita ayuda con algo relacionado con pyth, no dude en enviarme un ping en el chat.
Maltysen
2

Mathematica, 57 bytes

#/.x_:>RandomChoice@Select[Permutations@x,FreeQ[#-x,0]&]&

Función sin nombre que toma una lista de lo que sea como entrada y genera una lista. Después de generar todas las permutaciones #de la entrada x, conservamos solo aquellas para las cuales el conjunto #-xde diferencias entre elementos no contiene a 0; entonces hacemos una elección aleatoria (uniformemente) de ese conjunto.

Greg Martin
fuente
1
¡bonito! Ligeramente más largo, #/.x_:>NestWhile[RandomSample[#,Length@#]&,#,Not@FreeQ[#-x,0]&]&obviamente, más rápido en la práctica para cuerdas largas
martin
Espera, ¿me estás diciendo que no hay cambios incorporados en Mathematica? : o
shooqie
Estaba medio esperando un incorporado yo mismo :)
Greg Martin
0

PHP, 85 bytes

for($a=$b=str_split($argv[1]);array_diff_assoc($a,$b)!=$a;)shuffle($b);echo join($b);

Copia el argumento de cadena en dos matrices, baraja una de ellas hasta que la diferencia entre ellas (también comparando índices de los elementos) sea igual a la otra. Corre con -r.

Tito
fuente
0

R, 59 bytes

z=x=1:length(y<-scan(,""));while(any(x==z))z=sample(x);y[z]

Lee una lista de elementos en STDIN, toma la longitud de la lista y comienza los rangos de muestreo de 1 a la longitud, hasta que encuentra uno que no comparte lugares con la lista ordenada. Luego imprime esa lista.

JAD
fuente
0

Maravilla , 32 bytes

f\@[/>#I zip#=[#0a\shuf#0]?f a?a

Uso:

f\@[/>#I zip#=[#0a\shuf#0]?f a?a];f[1 2 3 4 5]

Explicación

Más legible:

f\@[
  some #I zip #= [#0; a\ shuf #0]
    ? f a
    ? a
]

Función recursiva f. Hace una comparación por elementos entre fla lista de entrada de y una versión aleatoria de la lista de entrada. Si la comparación arroja algún valor igual, fse llama a la lista aleatoria. De lo contrario, simplemente devolvemos la lista aleatoria.

Mama Fun Roll
fuente
0

Ruby, 67 bytes

def f a
while (a.zip(o=a.shuffle).map{|x,y|x-y}.index 0);end
o
end
Daniel deprimido
fuente
0

Octava, 54 53 bytes

@(a)((p=perms(a))(L=!any(p==a,2),:))(randi(sum(L)),:)

Genere todas las permutaciones de ay seleccione aleatoriamente una fila que no tenga un elemento común cona .

nota: ¡Es accidentalmente lo mismo que @flawr MATL answer!

rahnema1
fuente
0

Clojure, 94 90 79 bytes

#(let[s(shuffle %)](if(not(some(fn[[x y]](= x y))(map vector % s)))s(recur %)))

-4 bytes cambiando el condicional dentro de la reducción a un and , y en línea done?.

-11 bytes convirtiendo la reducción a some .

WOOT! Batir PHP.

Método de fuerza bruta. Baraja la lista mientras no es válida. Esto termina estúpidamente rápido considerando que es un método de fuerza bruta que no hace nada para evitar intentos duplicados. Encontró 1000 dearangments de una larga lista de 1000 elementos en menos de un segundo.

Sin golf:

(defn dearang [ls]
  (let [s (shuffle ls)
        bad? (some (fn [[x y]] (= x y))
                (map vector ls s))]
    (if (not bad?) s (recur ls))))
Carcigenicate
fuente
0

Clojure, 56 bytes

#(let[s(shuffle %)](if((set(map = % s))true)(recur %)s))

Tenga en cuenta que una cadena no se puede mezclar, se debe pasar por seqo vec.

Originalmente lo intenté #(first(remove(fn[s]((set(map = % s))true))(iterate shuffle %)))perorecur enfoque es más cortoiterate .

La magia es que (set(map = % s))devuelve un conjunto de falso, un conjunto de verdadero o un conjunto de verdadero y falso. Esto puede usarse como una función, si contiene, trueentonces la respuesta es true, de lo contrario, es falsa nil. =se complace en tomar dos argumentos de entrada, no es necesario envolverlo con algo.

((set [false]) true)
nil

¿Quizás haya una forma aún más corta de verificar si alguno de los valores es verdadero?

NikoNyrh
fuente
0

APL, 11 bytes.

Con la cadena en el argumento correcto:

⍵[⍋(⍴⍵)?⍴⍵]

Explicación

ρ⍵ obtiene la longitud (o forma) del argumento correcto.

?devuelve una matriz aleatoria (⍴⍵)de estos números.

devuelve el orden de ellos para garantizar que no haya duplicados.

⍵[..] representa el surtido aleatorio de la cadena usando este índice.

Jacob Utley
fuente
Bienvenido a PPCG! Requerimos que todas las entradas sean funciones válidas o programas completos, por lo que su respuesta debe recibir información a través de un argumento de función o método de entrada.
ETHproductions
Creo que debería cumplir con los requisitos ahora. Toma el argumento correcto, o .
Jacob Utley