Generuj przypadkowe wykolejenie

30

Opis wyzwania

„Wykroczenie” sekwencji jest permutacją, w której żaden element nie pojawia się w pierwotnej pozycji. Na przykład ECABDjest odstępstwem ABCDE, ale CBEDAnie jest:

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

Biorąc pod uwagę sekwencję, wygeneruj jej przypadkowe odstępstwo.

Notatki

  • Możesz wziąć ciąg znaków jako dane wejściowe lub tablicę / listę elementów (liczby całkowite, znaki, obiekty ...)

  • Zamiast zwracać nowy obiekt, możesz zmodyfikować istniejący, zamieniając jego elementy

  • Każde odstępstwo powinno mieć jednakowe prawdopodobieństwo wygenerowania

  • Możesz założyć, że w sekwencji jest więcej niż jeden element i żaden nie pojawia się więcej niż jeden raz

shooqie
źródło
4
Związane z?
Addison Crump,
3
@VoteToClose: haha, totalnie odpadł
shooqie,
Nie wiem za dużo o tym wszystkim, ale czy jest to w jakikolwiek sposób związane z twierdzeniem o punkcie stałym ... zgodnie z którym rzeczy zawsze kończą się na swoim miejscu, czy coś w tym rodzaju ...? Założę się, że się mylę, ale proszę, popraw mnie :)
Farhan Anam,
Czy jest jakaś gwarancja, że ​​elementy będą unikalne, czy mogą zawierać duplikaty?
Carcigenicate
1
@Carcigenicate: znajduje się tam w opisie; możesz założyć, że nie ma duplikatów
shooqie

Odpowiedzi:

12

CJam , 14 bajtów

q:X{mr_X.=:|}g

Wypróbuj online!

Powoduje tasowanie danych wejściowych, aż stanie się zaburzeniem.

Wyjaśnienie

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
źródło
1
Chciałbym, żeby OP sprecyzował, że rozwiązania będą musiały zagwarantować, że zawsze kończą.
John Dvorak,
4
@JanDvorak Cóż, prawdopodobieństwo, że to się nie skończy, wynosi 0. Ale masz rację, że wymaganie deterministycznego czasu działania uczyniłoby to wyzwanie bardziej interesującym.
Martin Ender,
Czy prawdopodobieństwo faktycznie wynosi 0? Losowanie nie będzie idealne, jak to właściwie działa? Myślę, że jest to prawdopodobnie dobre przybliżenie tego, o co poprosił PO, ale wątpię, aby prawdopodobieństwa każdego odstępstwa były takie same (prawdopodobnie zależy to od wartości początkowej PRNG, która prawdopodobnie jest używana przez operację tasowania).
Nikt
3
@Nie wątpię, że można uzyskać idealnie jednolite wyniki z PRNG przy użyciu dowolnego algorytmu. Jednak przy założeniu, że samo tasowanie jest jednolite (co w pewnym sensie Java zapewnia „Wszystkie permutacje występują w przybliżeniu z jednakowym prawdopodobieństwem.”), Rozwiązanie oparte na odrzuceniu również da jednolite odstępstwa, ponieważ każde odstępstwo jest jedną permutacją i każde permutacja ma takie samo prawdopodobieństwo.
Martin Ender,
1
@ Nikt Math frajerem tutaj. Warunek, który kończy się sukcesem lub porażką, nazywa się statystycznie próbą Bernoulliego. Oznacza to, że prawdopodobieństwo koniecznych prób K do pierwszego sukcesu wynosi (1 - p) ^ (k - 1) * p, gdzie p jest prawdopodobieństwem udanego wykroczenia. Łatwo zauważyć, że gdy k rośnie, prawdopodobieństwo potrzeby próby k staje się znikomo małe. Dlatego mówimy, że algorytm zatrzymuje się z prawdopodobieństwem 1 („prawie na pewno”), ale nie jest niemożliwe, aby nigdy się nie zatrzymywał.
maservant
9

Galaretka , 6 bajtów

Ẋ=³S$¿

Wypróbuj online!

Wyjaśnienie

Ẋ    ¿    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 uratował bajt.

Lynn
źródło
5
Masz czapkę Winter Bash z wyprzedzeniem? :-)
Luis Mendo
2
Czas narysować ładne nowe zdjęcie, Ẋ=³S$¿oszczędza bajt.
Jonathan Allan,
2
Huh, nigdy o tym nie wiedziałem $. Dzięki!
Lynn
Ma 6 znaków, ale więcej niż 6 bajtów. Ẋ = ³S $ ¿długości bajtów wynoszą: 312112. Czyli łącznie 10 bajtów.
mxfh
6

Python, 85 bajtów

Modyfikuje przekazaną do niej listę (dozwoloną przez meta i w pytaniu).

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

Wypróbuj online tutaj!

FlipTack
źródło
1
Jeśli podasz Python 2, myślę, że można zastąpić def D(l):z l=input(), a następnie zapisać przestrzenie wcięć w następujących liniach (tak masz program zamiast funkcji). Nie głosowałem jednak!
matmandan
@mathmandan dobry pomysł, ale musiałbym go ponownie wydrukować, jeśli jest to pełny program, który kosztuje więcej bajtów.
FlipTack,
1
Ok, jeśli tak mówisz. Wydaje mi się, że specyfikacja mówiła, że ​​nie musisz drukować ani zwracać wyniku - że wystarczy pobrać listę [z danych wejściowych użytkownika] i przetasować. Ale rozsądne jest odczytanie „istniejącego” jako „istniejącego przed uruchomieniem dowolnego kodu” - w takim przypadku zgadzam się z Tobą. (Być może istnieje ustalony konsensus w tej sprawie.) :)
matmandan
5

ES6 (JavaScript), 71, 69 bajtów

Dane wejściowe i wyjściowe są tablicami i powinny działać z dowolnymi typami elementów (ciągi, liczby itp.), O ile można je porównać z „==”.

Grał w golfa

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

Test

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

Interaktywny fragment kodu

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>

zepelin
źródło
5

Perl 6 , 33 bajtów

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

Lambda, która pobiera listę liczb całkowitych lub znaków jako dane wejściowe i zwraca nową listę.

Jeśli musi obsługiwać listy dowolnych wartości, nemusiałby zostać zastąpiony !eqv(+2 bajty).

( Wypróbuj online. )

Wyjaśnienie:

  • { }: Definiuje lambda.
  • .pick(*): Generuje losowe losowanie listy danych wejściowych.
  • .pick(*) xx *: Tworzy leniwą, nieskończoną sekwencję takich przetasowań.
  • (* Zne $_).all: Lambda, która zamyka dwie listy (argument *i zewnętrzny argument lambda $_) za pomocą neoperatora (ujemna równość łańcucha), dając listę boolanów, a następnie tworzy allpołączenie, aby zwinąć je do jednego stanu boolowskiego.
  • first PREDICATE, SEQUENCE: Pobiera pierwszy element z naszej nieskończonej sekwencji permutacji, która spełnia test „wykolejenia”.
smls
źródło
4

Brachylog , 19 18 15 13 bajtów

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

Wypróbuj online!

Wyjaśnienie

@~.                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
Fatalizować
źródło
3

Perl 6 , 45 bajtów

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

Spróbuj

Dane wejściowe to tablica czegokolwiek.

Rozszerzony:

{
  (

    @^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
źródło
3

MATL, 7 bajtów

To jest tłumaczenie mojego postu Octave (i podobne do niektórych innych zgłoszeń tutaj). Wczoraj opublikowałem swój pierwszy post MATL (pęknięcie CNR), więc myślę, że nie jest to optymalne, ale najlepsze, jakie do tej pory mam.

Szczerze mówiąc, nie jestem do końca pewien, czy tjest tam potrzebny, ale jest to jedyny sposób, w jaki mogę go uruchomić. Służy do porównywania danych wejściowych użytkownika (pobranych z G) z losową permutacją. Myślałbym, że mógłbym porównać te dwa bez tego, ale ...?

W każdym razie oto:

`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

Wypróbuj online!

Stewie Griffin
źródło
Jakieś ulepszenia? Czy naprawdę ttam potrzebuję , czy mogę się go pozbyć? Fajnie było grać w golfa w MATL ... :)
Stewie Griffin,
:-) Nie wiem, jak się tego pozbyć t(lub równoważnie innego G) Musisz zostawić coś na stosie do następnej iteracji lub jako wynik końcowy
Luis Mendo
3

Właściwie 13 bajtów

;;WX╚│♀=ΣWX)X

Wypróbuj online!

Wyjaśnienie:

;;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
źródło
2

Oktawa, 56 55 bajtów

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

Musimy użyć, input('')ponieważ nie jest to funkcja. Ponadto, ponieważ mogę wybrać, aby dane wejściowe były ciągiem, możemy użyć tej sztuczki nnz(x)==numel(x).

Wyjaśnienie:

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

Dzięki Luisowi za zauważenie, że wejście może być ciągiem, więc mogłem użyć nnzzamiast numelzapisywania dwóch bajtów.

Stewie Griffin
źródło
Uwaga do siebie: następnym razem przeczytaj całe pytanie :) Dzięki!
Stewie Griffin,
1
To mi się ciągle zdarza :-)
Luis Mendo
2

MATL, 13 bajtów

To wspólny wysiłek @LuisMendo i mnie. W przeciwieństwie do wielu innych odpowiedzi tutaj, ta jest deterministyczna w tym sensie, że nie próbkuje losowych permutacji, dopóki nie otrzyma wykroczenia, ale generuje wszystkie wykroczenia i wybiera jedną losowo.

Y@tG-!Af1ZrY)

Wypróbuj online!

Wyjaśnienie

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
wada
źródło
2

Pyth - 10 9 bajtów

Powoduje to tasowanie danych wejściowych, podczas gdy dowolny ze znaków jest równy znakom ze swojego indeksu na wejściu.

.WsqVHQ.S

Wypróbuj online tutaj .

.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
źródło
Czy możesz dodać wyjaśnienie. Chciałem napisać pytającą odpowiedź. Niewiele o tym wiem.
Gurupad Mamadapur,
@GurupadMamadapur na pewno też byłby szczęśliwy.
Maltysen
1
@GurupadMamadapur dodane. Mamy tutorial . Jest dość przestarzały, ale nauczy Cię podstaw. Jeśli potrzebujesz pomocy w jakiejkolwiek kwestii związanej z pyth, możesz pingować mnie na czacie.
Maltysen
2

Mathematica, 57 bajtów

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

Nienazwana funkcja przyjmuje listę wielorybników jako dane wejściowe i wyjściowe. Po wygenerowaniu wszystkich permutacji #danych wejściowych xzachowujemy tylko te, dla których zbiór #-xróżnic elementarnych nie zawiera 0; następnie dokonujemy (równomiernie) losowego wyboru z tego zestawu.

Greg Martin
źródło
1
miły! Nieco dłużej #/.x_:>NestWhile[RandomSample[#,Length@#]&,#,Not@FreeQ[#-x,0]&]&oczywiście szybszy w praktyce dla długich strun
martin
Zaraz, mówisz mi, że nie ma wbudowanych wykroczeń w Mathematica? : o
shooqie,
W połowie spodziewałem się wbudowanego w siebie :)
Greg Martin
0

PHP, 85 bajtów

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

Kopiuje argument ciągu do dwóch tablic, tasuje jeden z nich, aż różnica między nimi (także porównanie indeksów elementów) będzie równa drugiej. Uruchom z -r.

Tytus
źródło
0

R, 59 bajtów

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

Odczytuje listę elementów do STDIN, pobiera długość listy i rozpoczyna zakres próbkowania od 1 do długości, dopóki nie znajdzie takiego, który nie dzieli miejsc z uporządkowaną listą. Następnie drukuje tę listę.

JAD
źródło
0

Cud , 32 bajty

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

Stosowanie:

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

Wyjaśnienie

Bardziej czytelny:

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

Funkcja rekurencyjna f. Dokonuje elementarnego porównania między flistą danych wejściowych a tasowaną wersją listy danych wejściowych. Jeśli porównanie daje jakiekolwiek równe wartości, to fjest wywoływane na liście losowej. W przeciwnym razie po prostu zwracamy listę losową.

Mama Fun Roll
źródło
0

Rubinowy, 67 bajtów

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

Oktawa, 54 53 bajty

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

Wygeneruj wszystkie permutacje ai wybierz losowo wiersz, który nie ma wspólnego elementu a.

Uwaga: Jest to przypadkowo to samo, co odpowiedź @Lawr MATL!

rahnema1
źródło
0

Clojure, 94 90 79 bajtów

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

-4 bajty poprzez zmianę warunku wewnątrz redukcji na andi wstawianie done?.

-11 bajtów poprzez konwersję redukcji na some.

WOOT! Pokonaj PHP.

Metoda siłowa. Tasuje listę, gdy jest niepoprawna. To kończy się głupio szybko, biorąc pod uwagę, że jest to metoda brutalnej siły, która nie robi nic, aby zapobiec podwójnym próbom. Okazało się 1000 dearangments z 1000 elementów długiej listy w mniej niż sekundę.

Nie golfowany:

(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
źródło
0

Clojure, 56 bajtów

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

Zauważ, że łańcucha nie można przetasować, należy go przepuścić przez seqlub vec.

Początkowo próbowałem, #(first(remove(fn[s]((set(map = % s))true))(iterate shuffle %)))ale recurpodejście jest rzeczywiście krótsze niż iterate.

Magia polega na tym, że (set(map = % s))zwraca albo zbiór fałszów, zbiór prawdy, albo zbiór prawdy i fałszu. Może to być użyte jako funkcja, jeśli zawiera, truewówczas odpowiedź brzmi true, w przeciwnym razie fałsz nil. =z przyjemnością przyjmuje dwa argumenty wejściowe, bez potrzeby owijania go czymś.

((set [false]) true)
nil

Może istnieje jeszcze krótszy sposób sprawdzenia, czy którakolwiek z wartości jest prawdziwa?

NikoNyrh
źródło
0

APL, 11 bajtów.

Z ciągiem we właściwym argumencie:

⍵[⍋(⍴⍵)?⍴⍵]

Wyjaśnienie

ρ⍵ pobiera długość (lub kształt) odpowiedniego argumentu.

?zwraca losową tablicę (⍴⍵)tych liczb.

zwraca ich kolejność, aby zapewnić brak duplikatów.

⍵[..] reprezentuje losowy asortyment ciągu przy użyciu tego indeksu.

Jacob Utley
źródło
Witamy w PPCG! Wymagamy, aby wszystkie wpisy były poprawnymi funkcjami lub pełnymi programami, więc twoja odpowiedź musi przyjmować dane wejściowe za pomocą argumentu funkcji lub metody wprowadzania.
ETHproductions
Myślę, że teraz powinno pasować do wymagań. Przyjmuje odpowiedni argument lub .
Jacob Utley,