Gere um desarranjo aleatório

30

Descrição do Desafio

Um "desarranjo" de uma sequência é uma permutação em que nenhum elemento aparece em sua posição original. Por exemplo, ECABDé um distúrbio de ABCDE, mas CBEDAnão é:

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

Dada uma sequência, gere um desarranjo aleatório.

Notas

  • Você pode usar uma string como entrada ou uma matriz / lista de elementos (números inteiros, caracteres, objetos ...)

  • Em vez de retornar um novo objeto, você pode modificar um existente trocando seus elementos

  • Cada desarranjo deve ter uma probabilidade igual de ser gerado

  • Você pode assumir que há mais de um elemento na sequência e nenhum aparece mais de uma vez

shooqie
fonte
4
Relacionado?
Addison Crump
3
@VoteToClose: haha, totalmente eliminado
shooqie
Eu não sei muito sobre tudo isso, mas isso está de alguma forma relacionado ao teorema do ponto fixo ... segundo o qual as coisas sempre terminam em sua própria posição ou algo assim ...? Aposto que estou errado, mas alguém, por favor, me corrija :)
Farhan Anam
Existe alguma garantia de que os elementos serão exclusivos ou podem conter duplicatas?
Carcigenicate
1
@Carcigenicate: está ali na descrição; você pode supor que não há duplicatas #
shooqie

Respostas:

12

CJam , 14 bytes

q:X{mr_X.=:|}g

Experimente online!

Continua a embaralhar a entrada até que seja um distúrbio.

Explicação

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
fonte
1
Eu gostaria que a OP tivesse especificado que as soluções teriam que garantir que elas sempre terminassem.
John Dvorak
4
@JanDvorak Bem, a probabilidade de que isso não termine é 0. Mas você está certo que exigir um tempo de execução determinístico tornaria o desafio mais interessante.
Martin Ender
A probabilidade é realmente 0? A operação de reprodução aleatória não será perfeita, como realmente funciona? Acho que essa provavelmente é uma boa aproximação do que o OP solicitou, mas duvido que as probabilidades de cada desarranjo sejam as mesmas (provavelmente depende de algum valor inicial do PRNG que provavelmente é usado pela operação de reprodução aleatória).
Ninguém
3
@ Ninguém duvido que você possa obter resultados perfeitamente uniformes de um PRNG usando qualquer algoritmo que seja. No entanto, supondo que o shuffle em si seja uniforme (que os Java documentam como garantia com "Todas as permutações ocorrem com probabilidade aproximadamente igual".), Uma solução baseada em rejeição também produzirá desarranjos uniformes, porque cada desarranjo é uma permutação e cada permutação tem a mesma probabilidade.
Martin Ender
1
@Nobody Math nerd aqui. Uma condição que é bem-sucedida ou falha é chamada de julgamento de Bernoulli nas estatísticas. Isso implica que a probabilidade de k ser necessário para o primeiro sucesso é (1 - p) ^ (k - 1) * p, onde p é a probabilidade de um desarranjo bem-sucedido. É fácil perceber que, à medida que o k cresce, a probabilidade de precisar de k testes se torna muito pequena. Portanto, dizemos que o algoritmo para com probabilidade 1 ("quase certamente"), mas não é impossível que ele nunca pare.
maservant
9

Gelatina , 6 bytes

Ẋ=³S$¿

Experimente online!

Explicação

Ẋ    ¿    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 salvou um byte.

Lynn
fonte
5
Então, você adquiriu seu chapéu Winter Bash antes do tempo? :-)
Luis Mendo
2
Hora de desenhar uma bela imagem nova, Ẋ=³S$¿economiza um byte.
Jonathan Allan
2
Huh, eu nunca soube disso $. Obrigado!
Lynn
São 6 caracteres, mas mais de 6 bytes. Length = ³S $ ¿comprimentos de bytes são: 312112. Portanto, 10 bytes no total.
Mxfh
6

Python, 85 bytes

Modifica a lista passada para ele (permitida pela meta e na pergunta).

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

Experimente online aqui!

FlipTack
fonte
1
Se você especificar Python 2, eu acho que você poderia substituir def D(l):com l=input()e depois salvar os espaços de recuo nas seguintes linhas (para você ter um programa em vez de uma função). Mas não diminuiu o voto!
mathmandan
@ mathmandan boa ideia, mas precisaria imprimi-lo novamente se for um programa completo, que custa mais bytes.
FlipTack
1
OK se você está dizendo. Eu acho que a especificação parecia estar dizendo que você não precisava imprimir ou retornar o resultado - que pegar uma lista [da entrada do usuário] e embaralhá-la seria suficiente. Mas é razoável ler "existente" como "existente antes da execução de qualquer código"; nesse caso, eu concordo com você. (Talvez exista um consenso bem estabelecido sobre isso.) :) #
mathmandan
5

ES6 (Javascript), 71, 69 bytes

Entrada e saída são matrizes, devem funcionar com qualquer tipo de elemento (seqüências de caracteres, números etc.), desde que possam ser comparados com "==".

Golfe

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

Teste

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" ]

Snippet interativo

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>

zepelim
fonte
5

Perl 6 , 33 bytes

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

Um lambda que recebe uma lista de números inteiros ou caracteres como entrada e retorna uma nova lista.

Se ele deve suportar listas de valores arbitrários , neteria que ser substituído por !eqv(+2 bytes).

( Experimente online. )

Explicação:

  • { }: Define um lambda.
  • .pick(*): Gera uma aleatória aleatória na lista de entrada.
  • .pick(*) xx *: Cria uma sequência infinita e preguiçosa de tais shuffles.
  • (* Zne $_).all: Um lambda que fecha duas listas (seu argumento *e o argumento do lambda externo $_) com o neoperador (igualdade de string negativa), produzindo uma lista de booleanos e, em seguida, cria uma alljunção para recolhê-las em um único estado booleano.
  • first PREDICATE, SEQUENCE: Obtém o primeiro elemento de nossa sequência infinita de permutações que cumpre o teste de "desarranjo".
smls
fonte
4

Brachylog , 19 18 15 13 bytes

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

Experimente online!

Explicação

@~.                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
fonte
3

Perl 6 , 45 bytes

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

Tente

Entrada é uma matriz de qualquer coisa.

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
fonte
3

MATL, 7 bytes

Esta é uma tradução do meu post no Oitava (e semelhante a alguns dos outros envios aqui). Eu publiquei meu primeiro post sobre MATL ontem (CNR crack), então acho que isso não é o ideal, mas é o melhor que tenho até agora.

Para ser sincero, não tenho muita certeza de que té necessário, mas é a única maneira de fazer isso funcionar. É usado para que eu possa comparar a entrada do usuário (recuperada com G), com a permutação aleatória. Eu acho que poderia comparar os dois sem ele, mas ...?

Enfim, aqui vai:

`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

Experimente online!

Stewie Griffin
fonte
Alguma melhoria? Eu realmente preciso de tlá ou posso me livrar dele? Foi divertido tentar golfe em MATL ... :)
Stewie Griffin
:-) Não vejo como se livrar de que t(ou equivalentemente outra G) Você precisa deixar algo na pilha para a próxima iteração ou como resultado final
Luis Mendo
3

Na verdade , 13 bytes

;;WX╚│♀=ΣWX)X

Experimente online!

Explicação:

;;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
fonte
2

Oitava, 56 55 bytes

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

Temos que usar, input('')pois isso não é uma função. Além disso, como eu posso optar por ter a entrada como uma string, podemos usar o truque nnz(x)==numel(x).

Explicação:

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

Agradeço ao Luis por perceber que a entrada pode ser uma string, portanto, eu poderia usar em nnzvez de numelsalvar dois bytes.

Stewie Griffin
fonte
Nota para si mesmo: Leia toda a pergunta da próxima vez :) Obrigado!
Stewie Griffin
1
Isso acontece comigo o tempo todo :-) #
44745 Luis Mendo
2

MATL, 13 bytes

Este é um esforço conjunto de @LuisMendo e eu. Em contraste com muitas outras respostas aqui, essa é determinística no sentido de que não coleta permutações aleatórias até obter um desarranjo, mas gera todos os desarranjos e escolhe um aleatoriamente.

Y@tG-!Af1ZrY)

Experimente Online!

Explicação

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
flawr
fonte
2

Pitão - 10 9 bytes

Isso continua embaralhando a entrada enquanto qualquer um dos caracteres é igual aos caracteres em seu índice na entrada.

.WsqVHQ.S

Experimente online aqui .

.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
fonte
Você pode, por favor, adicionar uma explicação. Eu queria escrever uma resposta pyth. Eu não sei muito sobre isso.
Gurupad Mamadapur
@GurupadMamadapur com certeza, também ficaria feliz.
Maltysen
1
@GurupadMamadapur adicionou. Temos um tutorial . É bastante desatualizado, mas ensinará o básico. Se você precisar de ajuda com qualquer coisa relacionada ao pyth, sinta-se à vontade para me enviar um ping no chat.
Maltysen
2

Mathematica, 57 bytes

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

Função sem nome, tendo uma lista de itens como entrada e saída de uma lista. Após gerar todas as permutações #da entrada x, mantemos apenas aquelas para as quais o conjunto #-xde diferenças entre elementos não contém a 0; então fazemos uma escolha aleatória (uniformemente) desse conjunto.

Greg Martin
fonte
1
legais! Ligeiramente mais longo #/.x_:>NestWhile[RandomSample[#,Length@#]&,#,Not@FreeQ[#-x,0]&]&, obviamente, mais rápido na prática, para longas seqüências
martin
Espere, você está me dizendo que não há problemas internos no Mathematica? : o
shooqie
Eu estava meio que esperando um built-in me :)
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 o argumento da string para duas matrizes, embaralha uma delas até que a diferença entre elas (também comparando índices dos elementos) seja igual à outra. Corra com -r.

Titus
fonte
0

R, 59 bytes

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

Lê uma lista de elementos para STDIN, pega o comprimento da lista e inicia os intervalos de amostragem de 1 ao comprimento, até encontrar um que não compartilhe lugares com a lista ordenada. Em seguida, imprime essa lista.

JAD
fonte
0

Maravilha , 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]

Explicação

Mais legível:

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

Função recursiva f. Faz uma comparação entre elementos entre fa lista de entrada da e uma versão aleatória da lista de entrada. Se a comparação produzir valores iguais, isso fserá chamado na lista aleatória. Caso contrário, simplesmente retornamos a lista aleatória.

Mama Fun Roll
fonte
0

Ruby, 67 bytes

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

Oitava, 54 53 bytes

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

Gere todas as permutações de ae selecione aleatoriamente uma linha que não possui um elemento comum a.

nota: é acidentalmente o mesmo que a resposta do @flawr MATL!

rahnema1
fonte
0

Clojure, 94 90 79 bytes

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

-4 bytes, alterando o condicional dentro da redução para an and, e inliningdone? .

-11 bytes convertendo a redução para some.

WOOT! Bata o PHP.

Método de força bruta. Embaralha a lista enquanto ela é inválida. Isso termina estupidamente rápido, considerando que é um método de força bruta que não faz nada para impedir tentativas duplicadas. Encontrou 1000 preconceitos de uma lista longa de 1000 elementos em menos de um segundo.

Ungolfed:

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

Clojure, 56 bytes

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

Observe que uma sequência não pode ser embaralhada, deve ser passada por seqou vec.

Originalmente eu tentei, #(first(remove(fn[s]((set(map = % s))true))(iterate shuffle %)))mas a recurabordagem é realmente mais curta que iterate.

A mágica é que (set(map = % s))retorna um conjunto de falso, conjunto de verdadeiro ou conjunto de verdadeiro e falso. Isso pode ser usado como uma função, se contiver, trueentão a resposta é true, caso contrário, é falso nil. =tem o prazer de receber dois argumentos de entrada, sem necessidade de envolvê-lo com algo.

((set [false]) true)
nil

Talvez haja uma maneira ainda mais curta de verificar se algum dos valores é verdadeiro?

NikoNyrh
fonte
0

APL, 11 bytes.

Com a string no argumento correto:

⍵[⍋(⍴⍵)?⍴⍵]

Explicação

ρ⍵ obtém o comprimento (ou a forma) do argumento correto.

?retorna uma matriz aleatória (⍴⍵)desses números.

retorna a ordem deles para garantir que não haja duplicatas.

⍵[..] representa a variedade aleatória da string usando este índice.

Jacob Utley
fonte
Bem-vindo ao PPCG! Exigimos que todas as entradas sejam funções válidas ou programas completos, portanto, sua resposta precisa receber informações por meio de um argumento de função ou método de entrada.
ETHproductions
Eu acho que deve atender aos requisitos agora. Aceita o argumento correto, ou .
Jacob Utley