Cel

Posortuj listę elementów, upewniając się, że każdy element jest wymieniony po określonych zależnościach.

Wejście

Tablica tablic liczb całkowitych, gdzie każda liczba całkowita określa indeks innego elementu na podstawie 0 lub 1, po którym ten element musi nastąpić. Dane wejściowe mogą być tablicą lub ciągiem znaków lub czymkolwiek innym, możliwym do odczytania przez człowieka.

Na przykład wejście oparte na 0:

[
  [ 2 ],    // item 0 comes after item 2
  [ 0, 3 ], // item 1 comes after item 0 and 3
  [ ],      // item 2 comes anywhere
  [ 2 ]     // item 3 comes after item 2
]

Załóżmy, że nie ma zależności cyklicznych, zawsze istnieje co najmniej jedno prawidłowe zamówienie.

Wynik

Liczby w kolejności zależności. Dwuznaczny porządek nie musi być deterministyczny. Wynik może być tablicą, tekstem lub czymkolwiek innym, czytelnym dla człowieka.

Dane wyjściowe powinny zawierać tylko jedno zamówienie, nawet jeśli istnieje wiele prawidłowych zamówień.

Możliwe wyniki dla powyższego wejścia obejmują:

[ 2, 3, 0, 1 ]
[ 2, 0, 3, 1 ]

Punktacja

Funkcja lub program, który wypełni to w najmniejszej liczbie bajtów, wygrywa chwałę akceptacji. Termin upływa za 6 dni.

Galaretka, 8 bajtów

ịÐL³ŒḊ€Ụ

Opiera się to na (niezaimplementowanym) podejściu do głębokości z odpowiedzi Python @ xnor .

Wypróbuj online!

Jak to działa

ịÐL³ŒḊ€Ụ  Main link. Input: A (list of dependencies)

 ÐL       Apply the atom to the left until a loop is reached, updating the left
          argument with the last result, and the right argument with the previous
          left argument.
ị         For each number in the left argument, replace it with the item at that
          index in the right argument.
   ³      Call the loop with left arg. A (implicit) and right arg. A (³).
    ŒḊ€   Compute the depth of each resulting, nested list.
       Ụ  Sort the indices of the list according to their values.

Pyth, 21 bajtów

hf.A.e!f>xYTxkTbQ.plQ

                    Q  input
                   l   length of input array
                 .p    all permutations of [0, 1, ..., lQ-2, lQ-1]
hf                     find the first permutation for which...
    .e          Q        map over the input array with indices...
       f       b           find all elements in each input subarray where...
        >xYT                 index of dependency is greater than...
            xkT              index of item
      !                    check whether resulting array is falsy (empty)
  .A                     is the not-found check true for [.A]ll elements?

Test:

llama@llama:~$ echo '[[2],[0,3],[],[2]]' | pyth -c 'hf.A.e!f>xYTxkTbQ.plQ' 
[2, 0, 3, 1]

Python 2, 73 bajty

l=input()
f=lambda n:1+sum(map(f,l[n]))
print sorted(range(len(l)),key=f)

Sortuje wierzchołki według ich liczby potomnej, która jest fobliczana rekurencyjnie. Jeśli wierzchołek wskazuje na inny wierzchołek, jego potomkowie obejmują wierzchołek spiczasty i wszystkich potomków tego wierzchołka, więc ma on znacznie więcej potomków. Tak więc jest on umieszczany później niż wskazany wierzchołek w porządku, zgodnie z potrzebami.

Liczba potomków wierzchołka jest równa sobie, a liczba potomków każdego z jej dzieci. Zauważ, że potomek może być liczony wiele razy, jeśli prowadzi do niego wiele ścieżek.

Przydałby się również do użycia głębokości, a nie liczby potomków

f=lambda n:1+max(map(f,l[n]))

z wyjątkiem tego, maxże trzeba podać 0na pustej liście.

Pyth, 19 bajtów

hf!s-V@LQT+k._T.plQ

Wypróbuj online: demonstracja

Wyjaśnienie:

hf!s-V@LQT+k._T.plQ   implicit: Q = input list
               .plQ   all permutations of [0, 1, ..., len(Q)-1]
 f                    filter for permutations T, which satisfy:
      @LQT               apply the permutation T to Q
                         (this are the dependencies)
            ._T          prefixes of T
          +k             insert a dummy object at the beginning
                         (these are the already used elements)
    -V                   vectorized subtraction of these lists
   s                     take all dependencies that survived
  !                      and check if none of them survived
h                    print the first filtered permutation

Bash, 35 bajtów

perl -pe's/^$/ /;s/\s/ $. /g'|tsort

Przykładowy przebieg

We / Wy jest indeksowane 1. Każda tablica przechodzi w osobną linię, z białymi znakami jako separatorem elementów.

$ echo $'4\n1\n\n3\n1 3 2' # [[4], [1], [], [3], [1, 3, 2]]
4
1

3
1 3 2
$ bash tsort <<< $'4\n1\n\n3\n1 3 2'
3
4
1
2
5

Jak to działa

tsort- o czym dowiedziałem się w odpowiedzi na @ DigitalTrauma - odczytuje pary tokenów oddzielonych białymi spacjami, które wskazują częściowe uporządkowanie, i drukuje całkowite uporządkowanie (w postaci posortowanej listy wszystkich unikatowych tokenów), które rozszerza wspomniane częściowe uporządkowanie.

Po wszystkich liczbach w określonej linii następuje spacja lub znak linii. s/\s/ $. /gCzęść komendy Perl zastępuje te białe znaki z przestrzeni, numer linii i innej przestrzeni, a tym samym upewniając się, że każda n na linii k poprzedza k .

Wreszcie, jeśli linia jest pusta (tzn. Składa się tylko z linii), s/^$/ /wstawia do niej spację. W ten sposób drugie podstawienie zamienia pustą linię k w k k, upewniając się, że każda liczba całkowita występuje co najmniej raz w ciągu, do którego jest przesyłany potok tsort.

Bash + coreutils, 20 80

nl -v0 -ba|sed -r ':;s/(\S+\s+)(\S+) /\1\2\n\1 /;t;s/^\s*\S+\s*$/& &/'|tsort|tac

Wprowadź jako linie oddzielone spacją, np .:

2
0 3

2

• nl dodaje do wszystkich wierszy indeksy zerowe
• sed dzieli listy zależności na proste pary zależności i uzależnia niepełne zależności od siebie.
• tsort wykonuje wymagany rodzaj topologiczny
• tac ustawia wyjściową odwrotną kolejność

Ideone. Ideone z walizką testową @Dennis

Python 2, 143 118 116 bajtów

Nieco bardziej losowe podejście.

from random import*
l=input()
R=range(len(l))
a=R[:]
while any(set(l[a[i]])-set(a[:i])for i in R):shuffle(a)
print a

Edycje:

• naprawiłem to i faktycznie zaoszczędziłem też trochę bajtów.
• Zapisano 2 bajty (dzięki @Dennis)