Czy tablicę można odtasować?

15

tło

Bardzo wykwalifikowani operatorzy kart potrafią zastosować technikę, w której tną talię idealnie na pół, a następnie idealnie przeplatają karty. Jeśli zaczną od posortowanej talii i wykonają tę technikę bezbłędnie 52 razy z rzędu, talia zostanie przywrócona do posortowanej kolejności. Twoim wyzwaniem jest zabranie talii kart do tablicy liczb całkowitych i ustalenie, czy można ją sortować za pomocą tylko losowania Faro.

Definicja

Matematycznie tasowanie Faro to permutacja 2 n elementów (dla dowolnej dodatniej liczby całkowitej n ), która przenosi element w pozycji i (indeksowane 1) do pozycji 2 i (mod 2 n +1). Chcielibyśmy również móc obsługiwać listy nieparzystej długości, więc w takim przypadku wystarczy dodać jeden element na końcu listy (Joker, jeśli masz jeden pod ręką), a Faro przetasuje nową listę jak wyżej, ale zignoruj dodany element fikcyjny podczas sprawdzania kolejności listy.

Cel

Napisz program lub funkcję, która pobierze listę liczb całkowitych i zwróci lub wyświetli prawdę, jeśli pewna liczba losowań Faro spowodowałaby posortowanie tej listy w kolejności nieskalującej (nawet jeśli ta liczba jest równa zero - małe listy powinny dać prawdę). W przeciwnym razie zwróć lub wygeneruj fałsz.

Przykłady

[1,1,2,3,5,8,13,21]  => True
[5,1,8,1,13,2,21,3] => True
[9,36,5,34,2,10,1] => True
[1,0] => True
[0] => True
[] => True
[3,2,1] => True
[3,1,2] => False
[9,8,7,6,5,4,3,2,1,0] => True
[9,8,7,6,5,4,3,2,0,1] => False
[3,1,4,1,5,9,2,6,9] => False
[-1,-1,-1,-2] => True

Punktacja

To jest golf golfowy, więc wygrywa najkrótsze źródło w bajtach.

code-golf array-manipulation permutations kwintopia
źródło
Aby uniknąć pomyłek z innymi osobami zajmującymi się kartami, należy zauważyć, że istnieją dwa rodzaje losowania Faro. In-Shuffle oraz out-losowe . Opisana tutaj metoda jest tasowaniem. Co ciekawe, potrzeba tylko 8 przetasowań, aby przywrócić talię do pierwotnego porządku. Więcej informacji
BrainSteel,
Czy to nie tylko „przetasowanie N + 1 razy i sprawdzenie, czy któraś z list po drodze jest posortowana”?
lirtosiast
Właściwie n razy jest wystarczające, ponieważ zrobienie tego 2n razy gwarantuje znalezienie wszystkich możliwych permutacji, ale dostaniesz co najmniej jedną z rosnącej lub malejącej kolejności w pierwszym n.
kwintopia,
1
Związane z. Związane z.
Martin Ender,
1
Czy pierwszy element nie pozostaje zawsze na pierwszym miejscu?
Eumel,

Odpowiedzi:

3

Pyth - 26 25 24 bajtów

Używa skumulowanego zmniejszenia, aby wielokrotnie zastosować losowanie Faro i zachować wszystkie wyniki. Następnie mapuje go i sprawdza, czy podczas sortowania są niezmienne, a następnie używa sumy do sprawdzenia, czy wszystkie są prawdziwe. Zwraca wartość dodatnią lub zero.

smSI-db.usC_c2NQsC.tc2Qb

Pakiet testowy .

Maltysen
źródło
3

MATL , 41 bajtów

itn2\?YNh]tnt1+:"x[]2e!PY)ttZN~)tS=At.]wx

Dane wyjściowe to 1lub 0.

Wyjaśnienie

i              % get input array
tn2\           % is size odd?
?              % if that's the case
  YNh          % concat NaN at the end
]              % end if
tn             % get size of input array
t1+:           % vector 1:n+1, where n is input size, so loop will be entered even with []
"              % for loop
  x[]2e!PY)    % delete result from previous iteration and do the shuffling
  ttZN~)       % remove NaN, if there's any
  tS=A         % check if array is sorted
  t.           % copy the result. If true, break loop
]              % end for
wx             % remove unwanted intermediate result

Przykład

>> matl itn2\?YNh]tnt1+:"x[]2e!PY)ttZN~)tS=At.]wx
> [1,1,2,3,5,8,13,21]
1
Luis Mendo
źródło