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

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

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.

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!

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>

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”.

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

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
}

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!

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

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.

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

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

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.

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.

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ę.

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ą.

Rubinowy, 67 bajtów

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

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!

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))))

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?

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.