Tujuan

Mengurutkan daftar item memastikan bahwa setiap item terdaftar setelah dependensi yang ditentukan.

Memasukkan

Array array bilangan bulat, di mana setiap bilangan bulat menentukan indeks berbasis 0 atau 1 dari item lain yang harus dicari setelah item ini. Input dapat berupa array atau string atau apa pun yang dapat dibaca manusia.

Misalnya, input berbasis 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
]

Asumsikan tidak ada dependensi melingkar, selalu ada setidaknya satu pesanan yang valid.

Keluaran

Angka-angka dalam urutan ketergantungan. Perintah ambigu tidak harus bersifat deterministik. Outputnya bisa berupa array atau teks atau apa pun yang bisa dibaca manusia.

Hanya satu pesanan yang harus diberikan dalam output, bahkan di mana ada beberapa pesanan yang valid.

Output yang mungkin untuk input di atas termasuk:

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

Mencetak gol

Fungsi atau program yang menyelesaikan ini dalam jumlah byte paling sedikit memenangkan kemuliaan penerimaan. Batas waktu dalam 6 hari.

Jelly, 8 byte

ịÐL³ŒḊ€Ụ

Ini didasarkan pada pendekatan kedalaman (tidak diterapkan) dari jawaban Python @ xnor .

Cobalah online!

Bagaimana itu bekerja

ịÐ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 byte

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?

Uji:

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

Python 2, 73 byte

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

Urutkan simpul dengan hitungan turunannya, yang fmenghitung secara rekursif. Jika titik menunjuk ke titik lain, turunannya termasuk titik runcing dan semua turunan titik itu, sehingga memiliki lebih banyak keturunan. Jadi, itu ditempatkan lebih lambat dari simpul runcing dalam pemesanan, seperti yang diinginkan.

Hitungan turunan dari verteks adalah satu untuk dirinya sendiri, ditambah jumlah turunan dari masing-masing anak-anaknya. Perhatikan bahwa turunan dapat dihitung beberapa kali jika ada beberapa jalur menuju ke sana.

Itu juga akan bekerja menggunakan kedalaman daripada menghitung keturunan

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

kecuali maxharus memberi 0pada daftar kosong.

Pyth, 19 byte

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

Cobalah online: Peragaan

Penjelasan:

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 byte

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

Contoh dijalankan

I / O adalah 1-diindeks. Setiap array berjalan pada baris terpisah, dengan whitespace sebagai pemisah item.

$ 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

Bagaimana itu bekerja

tsort- yang saya pelajari dalam jawaban @ DigitalTrauma - membaca pasangan token, dipisahkan oleh spasi putih, yang menunjukkan pemesanan parsial, dan mencetak pemesanan total (dalam bentuk daftar diurutkan dari semua token unik) yang memperpanjang pemesanan sebagian yang disebutkan sebelumnya.

Semua angka pada garis tertentu diikuti oleh spasi atau umpan baris. Bagian s/\s/ $. /gdari perintah Perl menggantikan karakter spasi putih tersebut dengan spasi, nomor baris, dan spasi lain, sehingga memastikan bahwa setiap n pada baris k mendahului k .

Akhirnya, jika baris kosong (yaitu, hanya terdiri dari umpan baris), s/^$/ /tambahkan spasi untuknya. Dengan cara ini, substitusi kedua mengubah baris kosong k menjadi k k, memastikan bahwa setiap bilangan bulat muncul setidaknya sekali dalam string yang disalurkan ke 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

Input sebagai garis yang dipisahkan oleh spasi, mis:

2
0 3

2

• nl menambahkan indeks berbasis nol ke semua baris
• sed membagi daftar depedensi menjadi pasangan ketergantungan yang sederhana, dan membuat ketergantungan yang tidak lengkap bergantung pada diri mereka sendiri.
• tsort apakah jenis topologi yang diperlukan
• tac menempatkan urutan terbalik output

Ideone. Ideone dengan testcase @Dennis

Python 2, 143 118 116 byte

Pendekatan yang sedikit lebih acak .

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

Suntingan:

• memperbaikinya, dan sebenarnya menyimpan beberapa byte juga.
• Disimpan 2 byte (terima kasih @Dennis)