Tuples dengan secara berurutan menelusuri entri dalam daftar daftar

9

Tantangan:

Diberikan daftar daftar kosong dari bilangan bulat, kembalikan daftar tupel dari formulir berikut: Daftar pertama tupel dimulai dengan setiap elemen dari daftar pertama diikuti oleh elemen pertama dari setiap daftar berikutnya, sehingga tuple ke-i seharusnya [ith element of first list, first element of second list, ... , first element of last list]. Sebagai contoh:

[[1, 2, 3], [4, 5, 6], [7, 8, 9]] => [[1, 4, 7], [2, 4, 7], [3, 4, 7], ...

Kemudian lakukan tupel formulir [last element of first list, ith element of second list, first element of third list, ..., first element of last list], jadi dalam contoh kita ini akan menjadi:

[[1, 2, 3], [4, 5, 6], [7, 8, 9]] =>  ..., [3, 4, 7], [3, 5, 7], [3, 6, 7], ...

Lanjutkan dengan setiap daftar yang tersisa, sampai Anda mendapatkan [last element of first list, ..., last element of second to last list, ith element of last list]:

[[1, 2, 3], [4, 5, 6], [7, 8, 9]] => ..., [3, 6, 7], [3, 6, 8], [3, 6, 9]]

Output penuh adalah sebagai berikut:

[[1, 2, 3], [4, 5, 6], [7, 8, 9]] => 
        [[1, 4, 7], [2, 4, 7], [3, 4, 7], [3, 5, 7], [3, 6, 7], [3, 6, 8], [3, 6, 9]]

Beberapa boilerplate untuk ukuran yang baik:

  • Jika Anda ingin input menjadi daftar string, atau daftar bilangan bulat positif, tidak apa-apa. Pertanyaannya adalah tentang memanipulasi daftar, bukan tentang apa yang ada dalam daftar.
  • Input dan output dapat dalam format apa pun yang dapat diterima .
  • Program atau fungsi lengkap diizinkan.
  • Celah standar tidak diizinkan secara default.
  • Pertanyaan ini adalah kode golf, jadi byte-count terendah akan menang.

Contoh:

[] => [[]] (or an error, thanks to ngn for correcting the output in this case)

[[1]] => [[1]]

[[1, 2], [3, 4], [5]] => [[1, 3, 5], [2, 3, 5], [2, 4, 5]]

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

[[1, 2, 3], [4, 5]] => [[1, 4], [2, 4], [3, 4], [3, 5]]

[[1, 2, 3], []] => unspecified behavior (can be an error)

[[3, 13, 6], [9, 2, 4], [5, 10, 8], [12, 1, 11], [7, 14]] => 
     [[3, 9, 5, 12, 7], [13, 9, 5, 12, 7], [6, 9, 5, 12, 7], [6, 2, 5, 12, 7], 
      [6, 4, 5, 12, 7], [6, 4, 10, 12, 7], [6, 4, 8, 12, 7], [6, 4, 8, 1, 7], 
      [6, 4, 8, 11, 7], [6, 4, 8, 11, 14]]  

[[16, 8, 4, 14, 6, 7, 10, 15], [11, 1, 12, 2, 19, 18, 9, 3], [13, 5, 17]] =>
    [[16, 11, 13], [8, 11, 13], [4, 11, 13], [14, 11, 13], [6, 11, 13], 
     [7, 11, 13], [10, 11, 13], [15, 11, 13], [15, 1, 13], [15, 12, 13], [15, 2, 13], 
     [15, 19, 13], [15, 18, 13], [15, 9, 13], [15, 3, 13], [15, 3, 5], [15, 3, 17]]

Jika ada yang memiliki judul yang lebih baik, beri tahu saya.

jilbab
sumber
1
Saya memiliki perasaan yang [] => []seharusnya [] => [[]]tetapi tidak dapat menemukan kata-kata untuk menjelaskan mengapa.
ngn
1
@ ngn Anda benar, seharusnya [[]]karena ada satu tuple kosong dengan satu entri dari masing-masing (nol) daftar. Mungkin terlalu menjengkelkan untuk memerlukan program untuk menampilkan ini dengan benar, jadi saya akan mengatakan bahwa itu tidak perlu.
Hood
1
Ya [], sebenarnya, adalah daftar kosong dari daftar yang tidak kosong, tetapi hasilnya ambigu antara []dan [[]]jika itu merupakan input yang diizinkan. ("Daftar pertama tupel dimulai dengan setiap elemen dari daftar pertama ..." - tidak ada daftar pertama, jadi kita selesai -> [])
Jonathan Allan
1
@ Jonathanathan Allan Saya sekarang yakin bahwa output yang "benar" []seharusnya [[]]. Misalnya, jumlah tupel keluaran adalah sum(inner list lengths) - length of outer list + 1yang dalam kasus kosong berikan 1, yang merupakan panjang [[]]tetapi bukan panjang []. Ini sedikit masalah yang pedantic ...
Hood
1
Bisakah kita menganggap semua entri berbeda? Atau, lebih kuat, permutasi pada 1..n seperti dalam contoh Anda?
xnor

Jawaban:

5

JavaScript (ES6), 59 byte

Mengharapkan daftar daftar bilangan bulat positif .

f=a=>[a.map(a=>a[0]),...a.some(a=>a[1]&&a.shift())?f(a):[]]

Cobalah online!

Bagaimana?

Pada setiap iterasi:

  • Kami menampilkan daftar baru yang terdiri dari elemen pertama dari setiap daftar.
  • Kami menghapus elemen pertama dari daftar pertama yang mengandung setidaknya 2 elemen, dan ulangi prosesnya. Atau kami menghentikan rekursi jika tidak ada daftar seperti itu.
Arnauld
sumber
1
Itu a.sometrik mengagumkan!
ETHproductions
1
@ ETHproductions Sekarang mencari tantangan di mana menggunakan awe.sometidak akan membuang-buang byte ... :)
Arnauld
2

Python 2 , 62 byte

lambda M:[zip(*M)[l.pop(0)*0]for l in M+[[1,1]]for _ in l[1:]]

Cobalah online!

Menggunakan ide pop Chas Brown terinspirasi oleh pengajuan JS Arnauld .


Python 2 , 68 byte

M=input()
for l in[[0,0]]+M:
 for x in l[1:]:l[0]=x;print zip(*M)[0]

Cobalah online!

Memotong elemen pertama dari daftar untuk menyimpan nilai yang diinginkan. Ini [[0,0]]+adalah hack jelek untuk mencetak nilai awal pertama.

Tidak
sumber
2

Jelly , 15 byte

ẈṚṪ×€PƊƤFQṚCịŒp

Cobalah online! (catatan kaki menampilkan daftar yang dikembalikan sebenarnya daripada representasi Jelly)

Bagaimana?

Mengindeks ke dalam produk Cartesian dari daftar pada poin yang diperlukan ...

ẈṚṪ×€PƊƤFQṚCịŒp - Link: list of lists  e.g. [[6,8,4,9],[7,1,5],[3,2]]
Ẉ               - length of each            [4,3,2]
 Ṛ              - reverse                   [2,3,4]
       Ƥ        - for each prefix:             [2]      [2,3]      [2,3,4]
      Ɗ         -   last 3 links as a monad:
  Ṫ             -     tail (pop rightmost)     2        3          4
     P          -     product (of remaining)   1        2          6
    €           -     for €ach (range tail)    [1,2]    [1,2,3]    [1,2,3,4]   
   ×            -       multiply               [1,2]    [2,4,6]    [6,12,18,24]
        F       - flatten                   [1,2,2,4,6,6,12,18,24]
         Q      - de-duplicate              [1,2,4,6,12,18,24]
          Ṛ     - reverse                   [24,18,12,6,4,2,1]
           C    - complement (1-x)          [-23,-17,-11,-5,-3,-1,0]
             Œp - Cartesian product (of the input)
                -         -> [[6,7,3],[6,7,2],[6,1,3],[6,1,2],[6,5,3],[6,5,2],[8,7,3],[8,7,2],[8,1,3],[8,1,2],[8,5,3],[8,5,2],[4,7,3],[4,7,2],[4,1,3],[4,1,2],[4,5,3],[4,5,2],[9,7,3],[9,7,2],[9,1,3],[9,1,2],[9,5,3],[9,5,2]]
            ị   - index into (1-based & modular)
                -   indexes:      -23,                                            -17,                                            -11,                                             -5,             -3,             -1,     0
                -    values: [[6,7,3],                                        [8,7,3],                                        [4,7,3],                                        [9,7,3],        [9,1,3],        [9,5,3],[9,5,2]]
                -         -> [[6,7,3],[8,7,3],[4,7,3],[9,7,3],[9,1,3],[9,5,3],[9,5,2]]

ẈṚ’ṣ1T$¦ƬUṚị"€(14 byte) gagal untuk input dengan panjang (non-trailing) satu daftar; tapi mungkin ṣ1T$bisa diganti dengan yang lain?

Jonathan Allan
sumber
2

K (ngn / k) , 40 21 19 18 byte

{x@'/:?|\+|!|#:'x}

Cobalah online!

menggunakan ide dari jawaban @ H.PWiz

{ } berfungsi dengan argumen x

#:' panjang masing-masing

| balik

! semua indeks tupel untuk array dengan dimensi tersebut sebagai kolom dalam matriks (daftar daftar)

| balik

+ mengubah urutan

|\ menjalankan maxima

? unik

x@'/: gunakan setiap tuple di sebelah kanan sebagai indeks dalam daftar yang sesuai dari x

ngn
sumber
1

Arang , 33 byte

IE⊕ΣEθ⊖LιEθ§λ⌈⟦⁰⌊⟦⊖Lλ⁻ι∧μΣE…θμ⊖Lν

Cobalah online! Tautan adalah untuk mengucapkan versi kode. Penjelasan:

Keluarkan bilangan bulat ke string sebelum secara implisit mencetak menggunakan format output default untuk daftar, yang merupakan setiap item pada barisnya masing-masing, dan daftar bersarang memiliki spasi ganda.

E⊕ΣEθ⊖Lι

Ambil jumlah panjang daftar dan kurangi panjang daftar daftar. Kemudian putar dari 0 ke nilai ini termasuk.

Eθ§λ

Peta dari daftar daftar dan indeks ke dalam setiap daftar.

⌈⟦⁰⌊⟦⊖Lλ

Jepit indeks ke 0 dan indeks terakhir dalam daftar. (Kurung penutup tersirat.)

⁻ι∧μΣE…θμ⊖Lν

Setelah daftar pertama, kurangi panjang yang dikurangi dari semua daftar sebelumnya dari indeks terluar. (Ini tidak berfungsi untuk daftar pertama karena panjang daftar kosong dan jumlahnya bukan angka.)

Neil
sumber
1

Python 2 , 72 byte

f=lambda a:zip(*a)[:1]+(any(len(u)>1and u.pop(0)for u in a)and f(a)or[])

Cobalah online!

Ini adalah port Python dari algoritma Javascript yang luar biasa dari Arnauld .

Chas Brown
sumber
1

APL (Dyalog Classic) , 32 30 27 byte

1↓¨∪⊃{(⍵,¨⊃⍺),⍺,¨⍨⊢/⍵}/⌽0,⎕

Cobalah online!

program yang lengkap, input dari keyboard ( )

untuk []output input [[]](padanan APL mereka adalah 0⍴⊂⍬dan ,⊂⍬)

mengasumsikan keunikan angka dalam input

ngn
sumber
1
Bukan berarti itu membuat perbedaan pada output, tapi saya pikir input untuk tes kedua harus,⊂,1
H.PWiz
@ H.Piz, itu benar, tetap, tepuk tangan
ngn
1

JavaScript (ES6), 58 54 byte

h=(x,s)=>[x.map(y=>s|y?y[0]:s=y.shift()),...s?h(x):[]]

Setelah 14+ upaya menurunkan kode saya (menghapus semua contoh while loop,, pushdan concat), saya tiba pada iterasi yang secara algoritmik mirip dengan jawaban @ Arnauld , tidak mengejutkan mengingat betapa ringkasnya itu!

Menerima daftar daftar bilangan bulat positif. Cobalah online!

58 byte

Untuk 1 byte lebih, mengganti s = y.shift()dengan y.shift(s = 1)harus menangani semua bilangan bulat (mungkin, karena saya belum mengujinya secara pribadi).

h=(x,s)=>[x.map(y=>!s/y[1]?s=y.shift():y[0]),...s?h(x):[]]

58 byte

Versi bonus, dengan sedikit penataan ulang:

h=x=>[x.map(y=>s&&y[1]?y.shift(s=0):y[0],s=[]),...s||h(x)]

Penjelasan

Versi awal dari kode mencoba untuk memodifikasi klon dari (array) elemen pertama dari setiap array, tetapi langkah ekstra menginisialisasi array itu mahal ... sampai saya menyadari bahwa pemetaan elemen pertama dari setiap array kira-kira operasi "hanya" yang diperlukan jika saya mengubah array asli.

Menggunakan bendera boolean untuk memeriksa apakah array telah digeser (yaitu disingkat). Gantikan pemeriksaan bersyarat lebih jauh dengan mengamati bahwa JS memaksa array dengan nilai angka sebagai satu-satunya elemen ke dalam angka itu, sementara memaksa array dengan beberapa nilai sebagai NaN.

var
h = (x, s) => 
    [
        x.map(y =>                 // map to first element of each array
            s|y                    // if s == 1 (i.e. an array has been shortened)
                                   // or the current array y has length == 1
                ? y[0]
                : s = y.shift()    // remove first element of y and set s to truthy
        ),
        ...s ? h(x) : []           // only concatenate a recurrence of the function if an array has had a value removed
    ]
redundansi
sumber
1

APL (Dyalog) , 15 byte ( SBCS )

Terima kasih ngn untuk menunjukkan byte yang tidak perlu

{∪⌈\,⍉⍳≢¨⍵}⊃¨¨⊂

Cobalah online!

{∪⌈\,⍉⍳≢¨⍵}menghasilkan daftar untuk diindeks ke dalam input. misalnya(1 2 3) (4 5 6) (7 8 9) -> (0 0 0) (1 0 0) (2 0 0) (2 1 0) (2 2 0) (2 2 1) (2 2 2)

≢¨⍵: panjang setiap daftar di input

,⍉⍳membuat semua kombinasi angka hingga inputnya. misalnya2 3 -> (0 0) (1 0) (0 1) (1 1) (0 2) (1 2)

⌈\: memindai dengan maksimal. misalnya contoh di atas sekarang akan menjadi(0 0) (1 0) (1 1) (1 1) (1 2) (1 2)

: hapus duplikat

⊃¨¨⊂ melakukan pengindeksan, memperhatikan kedalaman dari kedua argumen

H.Piz
sumber
Jawaban bagus! Anda mengalahkan saya hampir setengah byte saya. sepertinya tidak perlu .
ngn
@ ngn Bagus, saya tidak ingat apa yang menyebabkan saya berpikir itu. Terima kasih!
H.PWiz
0

Python 2 , 91 byte

f=lambda a,p=():a and[p+(q,)+zip(*a)[0][1:]for q in a[0][p>():]]+f(a[1:],p+(a[0][-1],))or[]

Cobalah online!

Chas Brown
sumber