Algorytm „sortowania”

33

Istnieje „algorytm sortowania”, zwany czasem sortowaniem Stalina, w którym w celu posortowania listy wystarczy usunąć elementy z listy, aż zostanie ona posortowana w porządku rosnącym. Na przykład lista

[1, 2, 4, 5, 3, 6, 6]

Kiedy „posortowane” za pomocą Stalina staje się sortowanie

[1, 2, 4, 5, 6, 6]

Trójka została usunięta, ponieważ była niesprawna.

Oczywiście istnieje wiele sposobów usuwania elementów w celu posortowania listy. Na przykład każda lista zawierająca mniej niż dwa elementy musi zostać posortowana, więc wystarczy usunąć ślepo wystarczającą liczbę elementów, abyśmy zawsze mogli sortować listę. Ponieważ tak jest, zależy nam tylko na jak najdłuższym wyniku ze stali Stalina.

Twoim zadaniem będzie pobranie listy dodatnich liczb całkowitych i wyprowadzenie długości najdłuższej posortowanej (rosnącej) listy, którą można uzyskać, usuwając elementy z oryginalnej listy. To jest długość najdłuższej posortowanej (być może nieciągłej) podlisty.

Posortowane listy mogą mieć ten sam element więcej niż raz z rzędu. Nie musisz obsługiwać pustej listy, chyba że sam program jest pusty.

Punktacja

Twoja odpowiedź będzie oceniana według długości najdłuższego możliwego rodzaju Stalina. Programy będą interpretowane raczej jako ciąg bajtów niż znaków, a ich kolejność będzie naturalna, która powstaje w wyniku interpretacji bajtów jako liczb. Niższe wyniki są lepsze.

To nie jest

Oto fajne narzędzie, które pomoże Ci zdobyć odpowiedzi.

Przypadki testowe

[1, 2, 4, 5, 3, 6, 6] -> 6
[19, 2] -> 1
[3, 3, 4, 3] -> 3
[10] -> 1
[1, 2, 4, 9] -> 4
[1, 90, 2, 3, 4, 5] -> 5
[1, 90, 91, 2, 3, 4, 5] -> 5
Kreator pszenicy
źródło
3
W skrócie: wypisz długość najdłuższej (nie ściśle) rosnącej sekwencji .
user202729,
1
Podoba mi się reguła „Nie musisz obsługiwać pustej listy, chyba że sam program jest pusty”.
Paŭlo Ebermann
To wyzwanie przypomina mi wiele wyzwań związanych z droportem: codegolf.stackexchange.com/questions/61808/…
Stefnotch
1
Zrobiłem sprawdzanie na ptpb.pw/SVSt.html . Wciąż niezbyt funkcjonalny, ale działa. (DO ZROBIENIA: * wykres słupkowy * podział na najmniej malejące sekwencje * obsługa innych stron kodowych)
user202729
@ user202729 Cool! Dodałem go do postu. W razie potrzeby możesz edytować nowsze wersje.
Wheat Wizard

Odpowiedzi:

8

Python 2 , długość 14 12 10 9

M=max;X=exit;i=input();L=[0]*M(i)
for	a	in	i:L[a-1]=M(L[:a])+1
X(M(L))

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

Wypróbuj online!

Jak to działa

LL[a1]a

L

a[L[0],,L[a1]]aaaL[a1]

L

Dennis
źródło
Czy możesz wyjaśnić, dlaczego to działa? Trudno mi to zrozumieć :(
Dead Possum
Dodałem wyjaśnienie.
Dennis
5

Haskell , wynik 8 7, 48 bajtów

(l:k)%d|d>l=k%d|3>2=max(1+k%l)(k%d)
c%b=0
a=(%0)

Wypróbuj online!

Najdłuższa posortowana lista jest

%%%%%%)
Kreator pszenicy
źródło
4

Galaretka , długość  4  2

ṢƑƇZLƲ}ŒP

Wypróbuj online!

Bajty na stronie kodowej Jelly

183 146 144 90 76 169 125 19 80

Jak to działa

ṢƑƇZLƲ}ŒP  Main link. Argument: A (array)

       ŒP  Powerset; yield P, the array of all sub-arrays of A.
     Ʋ     Vier; combine the preceding four links into a monadic chain...
      }    and apply the chain to the right argument (P).
  Ƈ            Comb; only keep arrays for which the link to the left returns 1.
ṢƑ             Sort fixed; yield 1 if sorting doesn't alter the array.
   Z           Zip; read the filtered powerset by columns.
    L          Take the length.
Dennis
źródło
3

Pyth, wynik 3 2 ( 7 bajtów)

leSI#y

Zaoszczędź punkt dzięki Andersowi Kaseorgowi.
Wypróbuj tutaj

Wyjaśnienie

leSI#y
     yQ    Take the power set of the (implicit) input (preserving order).
  SI#      Get the ones that are sorted.
 e         Take the last (longest).
l          Get the length.

źródło
leSI#ypunkty 2.
Anders Kaseorg
2

Stax , 4 maksymalna długość sortowania według Stalina

S{:^fF%|M

Uruchom i debuguj

Działa to w ten sposób.

S       powerset of input
{:^f    filter by non-descending sequences
F%|M    take the maximum length remaining
rekurencyjny
źródło
2

R , wynik 15 11, 72 62 bajtów

function(L,M=max,A=1:M(L)*0){for(Y in L)A[Y]=M(A[1:Y])+1;M(A)}

Wypróbuj online!

Odpowiedź Pytona Dennisa na port R.

Giuseppe
źródło
Po prostu zmiana nazw zmiennych nie pomoże, ponieważ jak pokazuje twój ostatni link, żadna z nich nie jest użyta w (znalezionym) podciągu, który daje wynik 15.
Ørjan Johansen
@ ØrjanJohansen ah, oczywiście, jestem raczej głupi. Podejrzewam, że konieczne jest inne podejście.
Giuseppe
2

Brachylog , długość 2 (4 bajty)

⊇≤₁l

Wypróbuj online!

Odpowiedź, która rekompensuje to, że jest tak zwięzła, ponieważ nie jest o wiele krótsza.

( 08 03 80 6Cna stronie kodowej Brachylog)

        Output
   l    the length of
 ≤₁     a non-decreasing
⊇       sublist of
        the input.
        (maximizing the size of the sublist)
Niepowiązany ciąg
źródło
Wpadłem ►LSnmOṖna Husk ale jego wynik (o długości co najmniej) jest zbyt zły niepokoić komentarz ...
niezwiązane String