Wczoraj zadałem to pytanie na temat przetasowań riffle. Wydaje się, że wczorajsze pytanie było nieco zbyt trudne, więc jest to powiązane, ale o wiele łatwiejsze zadanie.

Dzisiaj jesteś proszony o ustalenie, czy permutacja jest tak naprawdę przetasowaniem riffle. Nasza definicja losowego przetasowania jest dostosowana do naszego ostatniego pytania:

Pierwszą częścią losowania jest podział. W partycji podziel talię kart na dwie części. Te dwa podrozdziały muszą być ciągłe, wzajemnie się wykluczające i wyczerpujące. W prawdziwym świecie chcesz, aby twoja partycja była jak najbliższa, jak to możliwe, jednak w tym wyzwaniu nie jest to rozważane, wszystkie partycje, w tym te, które są zdegenerowane (jedna partycja jest pusta), są jednakowo ważne.

Po ich podzieleniu karty są łączone w taki sposób, że karty zachowują względną kolejność w obrębie podziału, którego są członkami . Na przykład, jeśli karta A znajduje się przed kartą B w talii, a karty A i B znajdują się w tej samej partycji, karta A musi znajdować się przed kartą B w wyniku końcowym, nawet jeśli liczba kart między nimi wzrosła. Jeśli A i B znajdują się w różnych partycjach, mogą być w dowolnej kolejności, niezależnie od kolejności początkowej, w wyniku końcowym.

Każde losowanie karabinów można następnie traktować jako permutację oryginalnej talii kart. Na przykład permutacja

1,2,3 -> 1,3,2

jest losowym tasowaniem. Jeśli tak podzielisz talię

1, 2 | 3

widzimy, że każda karta w 1,3,2tej samej kolejności względem każdej innej karty na partycji. 2jest nadal po 1.

Z drugiej strony poniższa permutacja nie jest przetasowaniem riffla.

1,2,3 -> 3,2,1

Widzimy to, ponieważ dla wszystkich dwóch (nietrywialnych) partycji

1, 2 | 3
1 | 2, 3 

istnieje para kart, które nie zachowują względnej kolejności. W pierwszej partycji 1i 2zmień ich kolejność, podczas gdy w drugiej partycji 2i 3zmień ich kolejność.

Zadanie

Biorąc pod uwagę permutację dowolną rozsądną metodą, ustal, czy reprezentuje ona prawidłowe losowanie karabinu. Powinieneś wypisać dwie różne stałe wartości: jedną dla „Tak, to jest losowe odtwarzanie riffla”, a drugą dla „Nie, to nie jest losowe odtwarzanie losowe”.

To jest golf golfowy, więc odpowiedzi będą liczone w bajtach, przy czym mniej bajtów będzie lepszych.

Przypadki testowe

1,3,2 -> True
3,2,1 -> False
3,1,2,4 -> True
2,3,4,1 -> True
4,3,2,1 -> False
1,2,3,4,5 -> True
1,2,5,4,3 -> False
5,1,4,2,3 -> False
3,1,4,2,5 -> True
2,3,6,1,4,5 -> False

JavaScript (ES6), 47 bajtów

Pobiera dane wejściowe jako tablicę liczb całkowitych. Zwraca wartość logiczną.

([x,...a],y)=>a.every(z=>z+~x?y?z==++y:y=z:++x)

Przypadki testowe

let f =

([x,...a],y)=>a.every(z=>z+~x?y?z==++y:y=z:++x)

;[
  [1,3,2      ],  // -> True
  [3,2,1      ],  // -> False
  [3,1,2,4    ],  // -> True
  [2,3,4,1    ],  // -> True
  [4,3,2,1    ],  // -> False
  [1,2,3,4,5  ],  // -> True
  [1,2,5,4,3  ],  // -> False
  [3,1,4,2,5  ],  // -> True
  [2,3,6,1,4,5]   // -> False
]
.forEach(a => console.log(JSON.stringify(a) + ' -> ' + f(a)))

W jaki sposób?

Tablica wejściowa A jest poprawnym tasowaniem riffla, jeśli składa się z co najwyżej dwóch odrębnych sekwencji z przeplotem kolejnych liczb całkowitych.

Zasady wyzwanie określić, że mamy otrzymać permutacji z [1 ... n] . Nie musimy więc dodatkowo sprawdzać, czy posortowane połączenie tych sekwencji faktycznie prowadzi do takiego zakresu.

Używamy licznika x zainicjowanego na A [0] i licznika y początkowo niezdefiniowanego.

Dla każdego wpisu z w A , zaczynając od drugiego:

• Sprawdzamy, czy z jest równe x + 1 lub y + 1 . Jeśli tak, zwiększamy odpowiedni licznik.
• W przeciwnym razie: jeśli y jest nadal niezdefiniowane, inicjalizujemy go do z .
• W przeciwnym razie sprawimy, że test się nie powiedzie.

Haskell , 41 bajtów

n%h=n+0^(n-h)^2
f l=elem(foldl(%)0$l++l)l

Wypróbuj online!

Sprawdza, czy lista skonkatenowana z samym sobą zawiera liczby 0..n-1w kolejności jako podsekwencja.

Haskell , 43 bajty

spobiera listę liczb całkowitych jak w przykładach OP i zwraca a Bool.

s p=or[f(<x)p++f(>=x)p<[1..]|x<-p]
f=filter

Wypróbuj online!

Jak to działa

• Lista rozumienie próbuje każdy element xz pkolei i sprawdza, czy może to być pierwszy element z drugim rozbiorze shuffle. Następnie orzwraca, Truejeśli którykolwiek z czeków był True.
• Zrozumienie robi to dzieląc (z filter) pna elementy mniejsze i większe niż (lub równe) x, łącząc i sprawdzając, czy powstała lista [1..length p], tj. Elementy w kolejności.
• Sprawdzanie, czy wynikowa lista jest [1..length p]wykonywana, poprzez sprawdzenie, czy wynik jest ściśle mniejszy niż lista nieskończona [1..] == [1,2,3,etc.], co daje taki sam wynik dla dowolnej permutacji.

Galaretka , 13 6 bajtów

ỤIṢḊRẠ

Wypróbuj online!

Wersja alternatywna, wyzwanie postdate, 5 bajtów

Ụ>ƝSỊ

Wypróbuj online!

Jak to działa

ỤIṢḊRẠ  Main link. Argument: A (permutation of [1, ..., n])

Ụ       Grade up; sort the indices of A by their respective values.
        For shuffles, the result is the concatenation of up to two increasing
        sequences of indices.
 I      Compute the forward differences.
        In a shuffle, only one difference may be negative.
  Ṣ     Sort the differences.
   Ḋ    Dequeue; remove the first (smallest) difference.
    R   Range; map each k to [1, ..., k].
        This yields an empty array for non-positive values of k.
     Ạ  All; check if all resulting ranges are non-empty.

Python 2 , 39 bajtów

l=input()
n=0
for x in l*2:n+=n==x
l[n]

Wypróbuj online!

Pobiera indeksowaną listę 0 i generuje kod wyjścia.

Brachylog , 9 bajtów

o~cĊ⟨⊆⊇⟩?

Wypróbuj online!

Predykat kończy się powodzeniem, jeśli dane wejściowe reprezentują odtwarzanie losowe riffle, a jeśli nie, oznacza to, że między innymi, jeśli predykat zostanie uruchomiony jako cały program, wydrukowany zostanie sukces true.i błąd zostanie wydrukowany false.. Dane wejściowe są traktowane jako lista wszelkiego rodzaju elementów i interpretuje je jako reprezentację permutacji posortowanej przez siebie.

   Ċ         Some length-two list
 ~c          which concatenated
o            is the input sorted
    ⟨        satisfies the condition that its first element
     ⊆       is an ordered not-necessarily-contiguous sublist
        ?    of the input
      ⊇      which is an ordered superlist of
       ⟩     the list's second element.

Czuję, że coś w duchu ⊆ᵐpowinno działać zamiast czterobajtowej konstrukcji „kanapkowej” ⟨⊆⊇⟩.

Python 2 , 75 60 47 bajtów

dzięki Dennisowi za -13 bajtów

x={0}
for v in input():x=x-{v-1}|{v}
len(x)<3>q

Wypróbuj online!

Wyjście odbywa się za pomocą kodu wyjścia.

Rubinowy , 35 bajtów

->l{l.any?{|a|l&[*1..a]|l==l.sort}}

Wypróbuj online!

W jaki sposób?

• l & [*1..a] | lstosuje przecięcie, a następnie połączenie: najpierw uzyskaj elementy, lktóre są, <=aa następnie dodaj pozostałe elementy lbez zmiany kolejności. Jeśli a jest liczbą, której szukamy, to ta operacja jest taka sama jak sortowanie l.

Czysty , 56 55 bajtów

import StdEnv
?l=any(\e=sortBy(\a b=a<e&&b>=e)l<[1..])l

Wypróbuj online!

Pyth, 5 bajtów

}SQy+

Zestaw testowy

}SQy+

    +QQ  concatenated two copies of the (implicit) input
   y     all subsequences of it
}        contain an element equaling
 SQ      the input list sorted 

Sprawdza, czy lista podwójnych danych wejściowych zawiera posortowaną wersję siebie jako podsekwencji.

Dzięki Erikowi Outgolfer na 1 bajt, który lepiej wykorzystuje niejawne dane wejściowe +QQzamiast zamiast *2Q.

Pyth , 9 bajtów

!t-.+xLQS

Zestaw testowy.

Zaoszczędzono 3 bajty dzięki isaacg .

Pyth , 14 bajtów

}SQm.nS.Tcd2./

Wypróbuj tutaj! lub Zweryfikuj wszystkie przypadki testowe.

Wyjścia Truei Falseodpowiednio losowe odtwarzanie losowe i losowe.

W jaki sposób?

} SQm.nS.Tcd2./ ~ Pełny program. Odczytuje dane wejściowe ze STDIN i wysyła do STDOUT.

            ./ ~ Zwraca wszystkie podziały wejścia na rozłączne podciągi (partycja).
   m ~ Mapuj powyżej za pomocą zmiennej d.
         cd2 ~ Posiekaj d na listy dwuelementowe.
       .T ~ Uzasadniona transpozycja, ignorowanie nieobecności.
      S ~ Sortuj (leksykograficznie).
    .n ~ Głęboko spłaszczyć.
} ~ Sprawdź, czy powyższe zawiera ...
 SQ ~ Posortowane dane wejściowe.

Łuska , 7 bajtów

±§#OoṖD

Zestaw testowy!

Perl, 28 bajtów

Obejmuje +1dlaa

Wejście na STDIN, 1 oparte

perl -aE '$.+=$_==$.for@F,@F;say$.>@F' <<< "3 1 2 4"

Wykorzystuje algorytm xnor

C (gcc) , 61 bajtów

a,b,B;f(int*A){for(a=b=B=1;*A;A++)a-*A?B*=*A>b,b=*A:++a;b=B;}

Wypróbuj online!