Hasilkan kekacauan acak

30

Deskripsi tantangan

"Gangguan" dari urutan adalah permutasi di mana tidak ada elemen yang muncul di posisi aslinya. Misalnya ECABDadalah kekacauan ABCDE, tetapi CBEDAtidak:

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

Dengan diberi urutan, hasilkan kekacauan acak.

Catatan

  • Anda dapat mengambil string sebagai input atau array / daftar elemen (integer, karakter, objek ...)

  • Alih-alih mengembalikan objek baru, Anda dapat memodifikasi yang sudah ada dengan menukar elemen-elemennya

  • Setiap kekacauan harus memiliki probabilitas yang sama untuk dihasilkan

  • Anda dapat mengasumsikan bahwa ada lebih dari satu elemen dalam urutan dan tidak ada yang muncul lebih dari sekali

shooqie
sumber
4
Terkait?
Addison Crump
3
@VoteToClose: haha, benar-benar rusak
shooqie
Saya tidak tahu banyak tentang semua ini tetapi apakah ini terkait dengan teorema titik tetap ... yang menurutnya akan selalu berakhir pada posisi mereka sendiri atau sesuatu seperti itu ...? Saya berani bertaruh saya salah, tapi tolong perbaiki saya :)
Farhan Anam
Apakah ada jaminan bahwa elemen akan unik, atau bisakah mengandung duplikat?
Carcigenicate
1
@Carcigenicate: ada di sana dalam deskripsi; Anda mungkin menganggap tidak ada duplikat
shooqie

Jawaban:

12

CJam , 14 byte

q:X{mr_X.=:|}g

Cobalah online!

Terus mengocok input sampai kekacauan.

Penjelasan

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
sumber
1
Saya berharap OP telah menetapkan bahwa solusi harus menjamin mereka selalu selesai.
John Dvorak
4
@ JanDvorak Yah, probabilitas bahwa ini tidak selesai adalah 0. Tapi Anda benar bahwa memerlukan waktu berjalan yang deterministik akan membuat tantangan lebih menarik.
Martin Ender
Apakah probabilitasnya 0? Operasi shuffle tidak akan sempurna, bagaimana cara kerjanya sebenarnya? Saya pikir ini mungkin perkiraan yang baik dari apa yang diminta OP, tapi saya ragu probabilitas dari setiap kekacauan adalah sama (mungkin itu tergantung pada beberapa nilai awal dari PRNG yang kemungkinan digunakan oleh operasi acak).
Tidak ada yang
3
@ Tidak, saya ragu Anda bisa mendapatkan hasil seragam yang sempurna dari PRNG menggunakan algoritma apa pun. Namun, dengan asumsi bahwa shuffle itu sendiri seragam (di mana dokumen Java semacam menjamin dengan "Semua permutasi terjadi dengan kemungkinan yang kira-kira sama."), Solusi berbasis penolakan juga akan menghasilkan kekacauan seragam, karena setiap kekacauan adalah satu permutasi, dan masing-masing permutasi memiliki probabilitas yang sama.
Martin Ender
1
@Nobody Math nerd di sini. Suatu kondisi yang berhasil atau gagal disebut percobaan Bernoulli dalam statistik. Ini menyiratkan bahwa probabilitas percobaan k yang membutuhkan untuk keberhasilan pertama adalah (1 - p) ^ (k - 1) * p, di mana p adalah probabilitas dari kekacauan yang berhasil. Sangat mudah untuk melihat bahwa ketika k bertambah besar, kemungkinan membutuhkan uji k menjadi semakin kecil. Oleh karena itu, kami katakan algoritma berhenti dengan probabilitas 1 ("hampir pasti"), namun bukan tidak mungkin tidak pernah berhenti.
maservant
9

Jelly , 6 byte

Ẋ=³S$¿

Cobalah online!

Penjelasan

Ẋ    ¿    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 menyimpan satu byte.

Lynn
sumber
5
Jadi, Anda punya topi Musim Dingin Bash Anda sebelumnya? :-)
Luis Mendo
2
Saatnya menggambar gambar baru yang bagus, Ẋ=³S$¿menghemat satu byte.
Jonathan Allan
2
Huh, aku tidak pernah tahu soal itu $. Terima kasih!
Lynn
Ini 6 karakter, tetapi lebih dari 6 byte. Ẋ = ³S $ ¿panjang byte adalah: 312112. Jadi total 10 byte.
mxfh
6

Python, 85 byte

Mengubah daftar yang diteruskan (diizinkan oleh meta dan dalam pertanyaan).

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

Coba online di sini!

FlipTack
sumber
1
Jika Anda menentukan Python 2, saya pikir Anda bisa mengganti def D(l):dengan l=input()dan kemudian menyimpan ruang lekukan di baris berikut (jadi Anda memiliki program alih-alih fungsi). Tapi tidak downvote!
mathmandan
@mathmandan ide bagus, tapi kemudian saya harus mencetaknya kembali jika ini adalah program lengkap, yang harganya lebih banyak byte.
FlipTack
1
Baiklah jika kau bilang begitu. Saya kira bagi saya spek itu sepertinya mengatakan bahwa Anda tidak perlu mencetak atau mengembalikan hasilnya - bahwa mengambil daftar [dari input pengguna] dan mengocoknya sudah cukup. Tetapi masuk akal untuk membaca "ada" sebagai "sudah ada sebelum menjalankan kode Anda", dalam hal ini saya setuju dengan Anda. (Mungkin ada konsensus yang mapan tentang hal ini.) :)
mathmandan
5

ES6 (Javascript), 71, 69 byte

Input dan output adalah array, harus bekerja dengan semua jenis elemen (string, angka, dll), selama mereka dapat dibandingkan dengan "==".

Golf

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

Uji

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

Cuplikan Interaktif

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>

zeppelin
sumber
5

Perl 6 , 33 byte

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

Lambda yang mengambil daftar bilangan bulat atau karakter sebagai input, dan mengembalikan daftar baru.

Jika harus mendukung daftar nilai arbitrer , neharus diganti dengan !eqv(+2 byte).

( Cobalah online. )

Penjelasan:

  • { }: Mendefinisikan lambda.
  • .pick(*): Menghasilkan acak acak dari daftar input.
  • .pick(*) xx *: Membuat urutan tak terbatas malas dari pengocokan tersebut.
  • (* Zne $_).all: Sebuah lambda yang zip dua daftar (argumennya *, dan argumen lambda luar $_) dengan neoperator (kesetaraan string negatif), menghasilkan daftar boolean, dan kemudian membuat allpersimpangan untuk mengelompokkannya ke satu negara boolean.
  • first PREDICATE, SEQUENCE: Mengambil elemen pertama dari urutan permutasi tak terbatas kami yang memenuhi tes "kekacauan".
seseorang
sumber
4

Brachylog , 19 18 15 13 byte

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

Cobalah online!

Penjelasan

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

Perl 6 , 45 byte

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

Cobalah

Input adalah Array apa pun.

Diperluas:

{
  (

    @^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
sumber
3

MATL, 7 byte

Ini adalah terjemahan dari pos Oktaf saya (dan mirip dengan beberapa kiriman lainnya di sini). Saya memposting posting MATL pertama saya kemarin (CNR crack), jadi saya kira ini tidak optimal, tapi itu yang terbaik yang saya dapatkan sejauh ini.

Sejujurnya, saya tidak sepenuhnya yakin tdiperlukan di sana, tapi itu satu-satunya cara saya bisa membuatnya bekerja. Ini digunakan sehingga saya bisa membandingkan input pengguna (diambil dengan G), dengan permutasi acak. Saya akan berpikir saya bisa membandingkan keduanya tanpa itu, tapi ...?

Bagaimanapun, ini dia:

`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

Cobalah online!

Stewie Griffin
sumber
Adakah perbaikan? Apakah saya benar-benar perlu di tsana atau dapatkah saya menyingkirkannya? Sangat menyenangkan mencoba bermain golf di MATL ... :)
Stewie Griffin
:-) Saya tidak melihat bagaimana cara menghilangkannya t(atau yang lainnya setara G) Anda harus meninggalkan sesuatu di tumpukan untuk iterasi berikutnya atau sebagai hasil akhir
Luis Mendo
3

Sebenarnya , 13 byte

;;WX╚│♀=ΣWX)X

Cobalah online!

Penjelasan:

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

Oktaf, 56 55 byte

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

Kita harus menggunakan input('')karena ini bukan fungsi. Juga, karena saya dapat memilih untuk memiliki input sebagai string, kita dapat menggunakan trik itu nnz(x)==numel(x).

Penjelasan:

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

Terima kasih kepada Luis karena memperhatikan bahwa input dapat berupa string, jadi saya dapat menggunakan nnzalih-alih numelmenghemat dua byte.

Stewie Griffin
sumber
Catatan untuk diri sendiri: Baca seluruh pertanyaan lain kali :) Terima kasih!
Stewie Griffin
1
Itu terjadi pada saya sepanjang waktu :-)
Luis Mendo
2

MATL, 13 byte

Ini adalah upaya bersama dari @LuisMendo dan saya. Berbeda dengan banyak jawaban lain di sini, yang satu ini bersifat deterministik dalam arti bahwa ia tidak mengambil sampel permutasi acak sampai mendapat derangement, tetapi ia menghasilkan semua derangement dan memilih satu secara acak.

Y@tG-!Af1ZrY)

Cobalah secara Online!

Penjelasan

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
cacat
sumber
2

Pyth - 10 9 byte

Ini terus mengocok input sementara salah satu karakter sama dengan karakter pada indeks mereka di input.

.WsqVHQ.S

Cobalah online di sini .

.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
sumber
Bisakah Anda menambahkan penjelasan. Saya ingin menulis jawaban yang keras. Saya tidak tahu banyak tentang itu.
Gurupad Mamadapur
@GurupadMamadapur yakin, akan senang juga.
Maltysen
1
@GurupadMamadapur menambahkan. Kami punya tutorial . Cukup ketinggalan zaman, tetapi akan mengajarkan Anda dasar-dasar. Jika Anda membutuhkan bantuan apa pun yang berhubungan dengan pyth, jangan ragu untuk me-ping saya di chat.
Maltysen
2

Mathematica, 57 byte

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

Fungsi yang tidak disebutkan namanya mengambil daftar whatevers sebagai input dan keluaran daftar. Setelah menghasilkan semua permutasi #input x, kami hanya menyimpan yang set #-xelemen-perbedaan tidak mengandung a 0; lalu kita membuat pilihan acak (seragam) dari set itu.

Greg Martin
sumber
1
bagus! Sedikit lebih lama #/.x_:>NestWhile[RandomSample[#,Length@#]&,#,Not@FreeQ[#-x,0]&]&jelas lebih cepat dalam praktik untuk string panjang
martin
Tunggu, Anda mengatakan kepada saya bahwa tidak ada gangguan bawaan pada Mathematica? :Hai
shooqie
Saya setengah berharap built-in sendiri :)
Greg Martin
0

PHP, 85 byte

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

Menyalin argumen string ke dua array, mengocok salah satunya hingga perbedaan di antara keduanya (juga membandingkan indeks elemen) sama dengan yang lainnya. Jalankan dengan -r.

Titus
sumber
0

R, 59 byte

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

Membaca daftar elemen ke STDIN, mengambil panjang daftar dan mulai rentang pengambilan sampel dari 1 hingga panjang, hingga menemukan yang tidak berbagi tempat dengan daftar yang dipesan. Kemudian cetak daftar itu.

JAD
sumber
0

Bertanya-tanya , 32 byte

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

Pemakaian:

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

Penjelasan

Lebih mudah dibaca:

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

Fungsi rekursif f. Apakah perbandingan elemen antara fdaftar input dan dan versi daftar input yang dikocok. Jika perbandingan menghasilkan nilai yang sama, maka fdisebut pada daftar shuffled. Jika tidak, kami cukup mengembalikan daftar yang dikocok.

Mama Fun Roll
sumber
0

Ruby, 67 byte

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

Oktaf, 54 53 byte

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

Hasilkan semua permutasi adan pilih secara acak baris yang tidak memiliki elemen umum a.

Catatan: Secara tidak sengaja sama dengan @flawr MATL answer!

rahnema1
sumber
0

Clojure, 94 90 79 byte

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

-4 byte dengan mengubah kondisional di dalam reduksi menjadi and, dan inlining done?.

-11 byte dengan mengonversi reduksi menjadi some.

WOOT! Kalahkan PHP.

Metode brute-force. Mengacak daftar saat tidak valid. Ini selesai cepat bodoh mengingat ini adalah metode brute force yang tidak melakukan apa pun untuk mencegah duplikat mencoba. Itu menemukan 1000 dearangments dari daftar elemen 1000 dalam waktu kurang dari satu detik.

Tidak Disatukan:

(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
sumber
0

Clojure, 56 byte

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

Perhatikan bahwa string tidak dapat dikocok, harus melewati seqatau vec.

Awalnya saya mencoba #(first(remove(fn[s]((set(map = % s))true))(iterate shuffle %)))tetapirecur pendekatannya memang lebih pendek dari iterate.

Ajaibnya adalah (set(map = % s))mengembalikan seperangkat false, set true atau set true dan false. Ini dapat digunakan sebagai fungsi, jika mengandung truemaka jawabannya adalah true, jika tidak palsu nil. =dengan senang hati mengambil dua argumen input, tidak perlu membungkusnya dengan sesuatu.

((set [false]) true)
nil

Mungkin ada cara yang lebih pendek untuk memeriksa apakah ada nilai yang benar?

NikoNyrh
sumber
0

APL, 11 byte.

Dengan string dalam argumen yang benar:

⍵[⍋(⍴⍵)?⍴⍵]

Penjelasan

ρ⍵ mendapatkan panjang (atau bentuk) dari argumen yang benar.

?mengembalikan array acak (⍴⍵)dari angka-angka ini.

mengembalikan urutan mereka untuk memastikan tidak ada duplikat.

⍵[..] mewakili bermacam-macam string secara acak menggunakan indeks ini.

Jacob Utley
sumber
Selamat datang di PPCG! Kami mengharuskan semua entri menjadi fungsi yang valid atau program lengkap, jadi jawaban Anda perlu mengambil input melalui argumen fungsi atau metode input.
ETHproduksi
Saya pikir itu harus sesuai dengan persyaratan sekarang. Itu mengambil argumen yang benar, atau .
Jacob Utley