Sandwich Array

8

(Diadaptasi dari Soal C pada kualifikasi pertama dari ACM Programming Contest 2012/2013 )

Anda memiliki beberapa array, bernama A 1 , A 2 , ..., A n , masing-masing diurutkan dalam urutan menaik. Setiap item dalam array akan menjadi bilangan bulat 32-bit.

Sebuah Sandwich adalah satu set indeks j 1 , j 2 , ..., j n sehingga A 1 [j 1 ] ≤ A 2 [j 2 ] ≤ .... ≤ A n [j n ].
A i [0] adalah elemen pertama dari A i .

Diberikan beberapa array, hasilkan setiap sandwich yang mungkin Anda dapat miliki dari array tersebut, dipisahkan oleh baris baru.

Jika ada fungsi bawaan yang melakukan ini dalam bahasa Anda, jangan gunakan itu.

Input dapat diberikan dengan cara apa pun, output harus dipisahkan dengan spasi putih, tetapi dapat diberikan dalam urutan apa pun.

Kasus cobaan:
[[1, 5, 7, 10], [2, 6, 6, 8, 12], [4, 5, 9]]

Keluaran:

0 0 0
0 0 1
0 0 2
0 1 2
0 2 2
0 3 2
1 1 2
1 2 2
1 3 2
2 3 2

Kasus cobaan:
[[10, 20, 30], [1, 2, 3]]

Keluaran:

Kode terpendek menang.

beary605
sumber
1
Nilai apa yang bisa dimiliki oleh array? Hanya bilangan bulat positif?
Ilmari Karonen
@IlmariKaronen: Mereka akan mengandung bilangan bulat negatif juga.
beary605
@PeterTaylor: Untuk kesederhanaan, mereka akan menjadi bilangan bulat 32-bit.
beary605
@ Davidvidarraher: Ini kasus uji berikutnya. Saya harus membuatnya lebih jelas.
beary605
Terima kasih. Sekarang saya melihat bahwa solusi saya saat ini hanya berfungsi untuk array 3 elemen. Saya harus bekerja sedikit lebih untuk menggeneralisasikannya.
DavidC

Jawaban:

2

APL (33)

↑1-⍨B/⍨{(⍳⍴A)∘≡⍋⍵⌷¨A}¨B←,⍳⊃∘⍴¨A←⎕

Input dibaca dari keyboad, tetapi harus diberikan sebagai daftar APL, yaitu

(1 5 7 10) (2 6 6 8 12) (4 5 9)

Penjelasan:

  • B←,⍳⊃∘⍴¨A←⎕: A adalah input yang dievaluasi, B adalah semua set indeks yang memungkinkan dalam daftar yang diberikan pada A.
  • {(⍳⍴A)∘≡⍋⍵⌷¨A}¨B: untuk setiap set indeks, dapatkan nilai dari daftar ( ⍵⌷¨A) dan lihat apakah mereka diurutkan ( (⍳⍴A)∘=⍋)
  • B/⍨: pilih dari B semua set indeks di mana ekspresi sebelumnya benar (yaitu semua sandwich)
  • 1-⍨: kurangi satu dari semua indeks, karena pertanyaan ini mengasumsikan array berbasis-0 dan array-APL adalah berbasis-1 secara default.
  • : mengatur daftar set indeks sebagai matriks (sehingga setiap set adalah pada barisnya sendiri)
marinus
sumber
3

Mathematica 120 130

Edit

Versi ini bekerja dengan array ukuran yang bervariasi.


l = List;
g = Grid@Cases[Outer[l, Sequence @@ MapIndexed[l, #, {2}], 1]~Flatten~(Length[#] - 1), 
x_ /; LessEqual @@ x[[All, 1]] == True :> x[[All, 2, 2]] - 1] &

Pemakaian

g@{{10, 20, 30}, {1, 22, 3}}
g@{{1, 5, 7, 10}, {2, 6, 6, 8, 12}, {4, 5, 9}}
g@{{10, 20, 30}, {1, 2, 3}}
g@{{1, -2, 3}, {-12, -7, 8, 9, 6}, {3, 99, 9}, {100, 10, -23}, {90, 10}}

hasil


Penjelasan

Menggunakan contoh pertama dari atas,

a = {{10, 20, 30}, {1, 22, 3}}

MapIndexedmenetapkan indeks untuk semua elemen. NB: Mathematica mulai menghitung dengan 1. (Kami akan mempertimbangkannya nanti.)

MapIndexed[l, a, {2}]

{{{10, {1, 1}}, {20, {1, 2}}, {30, {1, 3}}}, {{1, {2, 1}}, {22, {2, 2}}, {3, {2, 3}}}}


Outermenghasilkan semua daftar, masing-masing kandidat sebagai array sandwich, dan indeks elemen mereka; %berisi hasil dari output sebelumnya. Angka-angka, 10dan 22yang saya sorot setelah mereka output, merujuk pada array sandwich {10,22}yang belum diidentifikasi.

Outer[l, Sequence @@ %, 1]~Flatten~(Length[a] - 1)

{{{10, {1, 1}}, {1, {2, 1}}}, {{ 10 , {1, 1}}, { 22 , {2, 2}}}, {{10, { 1, 1}}, {3, {2, 3}}}, {{20, {1, 2}}, {1, {2, 1}}}, {{20, {1, 2}},, {22, {2, 2}}}, {{20, {1, 2}}, {3, {2, 3}}}, {{30, {1, 3}}, {1, {2, 1}}}, {{30, {1, 3}}, {22, {2, 2}}}, {{30, {1, 3}}, {3, {2, 3}}}}}


Casesmenguji setiap elemen di atas untuk menentukan apakah suatu hubungan LessEqual(kurang dari atau sama) berlaku. Hasil yang ditunjukkan di bawah ini adalah contoh di mana array sandwich terdeteksi. Sekali lagi, saya menyoroti {10,22}dalam output.

Cases[%, x_ /; LessEqual @@ x[[All, 1]] == True]

{{{ 10 , {1, 1}}, { 22 , {2, 2}}}, {{20, {1, 2}}, {22, {2, 2}}}}}


%%mengacu pada hasil kedua dari belakang. :>, [RuleDelayed] mengembalikan bagian-bagian dari instance yang menarik, yaitu, indeks sandwich array.  -1mengoreksi fakta bahwa Mathematica memulai array dengan 1 bukannya 0. 

Cases[%%, 

x_ /; LessEqual @@ x [[Semua, 1]] == Benar:> x [[Semua, 2, 2]] - 1]

{{0, 1}, {1, 1}}


Gridmenampilkan hasilnya dalam kotak. Baris pertama 0 1berarti elemen 0 dari sublist pertama (yaitu 10 ) dan elemen 1 dari sublist kedua (yaitu 22 ) merupakan array sandwich pertama yang ditemukan.

Grid@%

0 1

1 1

DavidC
sumber
Saya tidak suka jawaban ini karena Anda secara artifisial menyederhanakan jawaban Anda dengan memperbaiki jumlah array.
FUZxxl
Jika maksud Anda itu hanya berfungsi untuk array dari 3 "baris", saya berbagi ketidaksukaan Anda. Masalahnya berkaitan dengan mengaktifkan LessEqualuntuk bekerja dengan array dengan ukuran yang tidak ditentukan. Mungkin ada contoh lain di mana asumsi yang sama menghambat generalisasi. Ketika saya mendapat kesempatan, saya akan menggeneralisasi pendekatan.
DavidC
@ FuZxxl saya bisa menggeneralisasi pendekatan. Lihatlah.
DavidC
3

GolfScript, 51 karakter

~:A{,}%{*}*,{A{,.@.@/\@%}%\;}%{:k,,{.A=\k==}%.$=},`

Contoh input (pada stdin):

[[1 5 7 10] [2 6 6 8 12] [4 5 9]]

Contoh output (ke stdout):

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

(Perhatikan bahwa input harus diberikan tanpa koma, jika tidak, program kemungkinan besar akan macet.)


Saya kira saya harus menambahkan beberapa penjelasan tentang cara kerja kode ini:

  • ~:Ahanya mengevaluasi input sebagai kode GolfScript dan menetapkan hasilnya (array array) A. Itu juga meninggalkan salinan Adi stack untuk langkah selanjutnya.

  • {,}%mengganti setiap sub-array dengan panjangnya, dan {*}*mengalikan panjangnya bersama-sama, memberikan jumlah total kandidat sandwich yang mungkin. Angka ini kemudian dikonversi oleh ,ke array yang banyak bilangan bulat berturut-turut mulai dari 0.

  • {A{,.@.@/\@%}%\;}%mengkonversi setiap nomor menjadi kandidat sandwich yang sesuai (yaitu array indeks yang valid ke dalam setiap sub-array di A). Misalnya, diberi input di atas, 0akan memetakan ke [0 0 0], 1ke [1 0 0], 2ke [2 0 0], 3ke [3 0 0], 4ke [0 1 0]dan seterusnya. (Mencari tahu persis bagaimana kode mencapai yang tersisa sebagai latihan untuk pembaca yang tertarik.)

  • {:k,,{.A=\k==}%.$=},menyaring kandidat sandwich dengan memetakan masing-masing ke elemen yang sesuai dari sub-array A(sehingga misalnya [0 0 0]akan menghasilkan [1 2 4], [1 0 0]akan menghasilkan [5 2 4], dan seterusnya, untuk input di atas), menyortir array yang dihasilkan dan membandingkannya dengan salinan yang tidak disortir . Jika mereka sama, array sudah diurutkan, dan dengan demikian kandidatnya memang sandwich.

  • Akhirnya, `hanya mengubah array sandwich yang disaring menjadi string untuk output.

Ilmari Karonen
sumber
Mereka harus dipisahkan oleh spasi putih, jadi spasi atau tab juga berfungsi.
beary605
OK, saya sudah mengubah format output.
Ilmari Karonen
1

R - 89 karakter

i=do.call(expand.grid,lapply(x,seq_along))
i[apply(diff(t(mapply(`[`,x,i)))>=0,2,all),]-1

dimana

x = list(c(1, 5, 7, 10), c(2, 6, 6, 8, 12), c(4, 5, 9))

atau

x = list(c(10, 20, 30), c(1, 2, 3))
flodel
sumber
1

Python, 149 141 140

import itertools as I;x=input();r=range;print[p for p in I.product(*map(r,map(len,x)))if all(x[i][p[i]]<=x[i+1][p[i+1]]for i in r(len(x)-1))]

Python memiliki pustaka itertools yang berguna yang dapat menghasilkan permutasi. Ini hanya mengulangi semua permutasi yang mungkin dari indeks yang valid dan memeriksa apakah mereka memenuhi kriteria.

Saya pikir saya bisa membuat ini lebih pendek, masih bekerja di sana.

Sunting: Sekarang semua satu baris untuk kenyamanan membaca Anda!

scleaver
sumber
r=rangeakan menyimpan satu karakter.
beary605
Terima kasih atas tipnya. Tidak pernah terpikir oleh saya bahwa saya bisa alias fungsi perpustakaan.
scleaver
1

Python 120

f=lambda p,k=0:['%i '%j+m for j,v in enumerate(p[0])if v>=k for m in f(p[1:],v)]if p else['']
print'\n'.join(f(input()))

... masih berpikir, "menghitung" adalah kata yang sangat panjang.

Daniel
sumber
1

GolfScript (44 karakter)

~{.,,]zip}%{{`{+}+1$\/}%\;}*{2%.$=},{(;2%}%`

Input dan output format yang sama dengan entri Ilmari.

Demo

Rincian kasar:

Petakan setiap baris input ke dalam array berpasangan [value index]

{.,,]zip}%

Lipat produk Cartesian di atas baris

{{`{+}+1$\/}%\;}*

Saring ke entri yang 0, 2, 4, dll. Tidak berkurang.

{2%.$=},

Peta masing-masing ke entri 1, 3, 5, dll.

{(;2%}%
Peter Taylor
sumber
0

Q, 43

{f(&)m~'(asc')m:x@'/:f:(cross/)(!:')(#:')x}
tmartin
sumber