Temukan array yang sesuai dengan jumlah penjumlahan

17

Pertimbangkan Apanjang array n. Array hanya berisi bilangan bulat positif. Sebagai contoh A = (1,1,2,2). Mari kita definisikan f(A)sebagai himpunan jumlah semua sub-susunan berdekatan yang tidak kosong dari A. Dalam hal ini f(A) = {1,2,3,4,5,6}. Langkah-langkah untuk menghasilkan f(A) adalah sebagai berikut:

Subarrays dari Aadalah (1), (1), (2), (2), (1,1), (1,2), (2,2), (1,1,2), (1,2,2), (1,1,2,2). Jumlah masing-masing adalah 1,1,2,2,2,3,4,4,5,6. Oleh karena itu, set yang Anda dapatkan dari daftar ini {1,2,3,4,5,6}.

Tugas

Diberikan satu set jumlah yang Sdiberikan dalam urutan yang diurutkan yang hanya berisi bilangan bulat positif dan panjang array n, tugas Anda adalah menghasilkan setidaknya satu array Xsedemikian rupa f(X) = S.

Misalnya, jika S = {1,2,3,5,6}dan n = 3kemudian output yang valid adalah X = (1,2,3).

Jika tidak ada array seperti itu, Xkode Anda harus menampilkan nilai konstan apa pun.

Contohnya

Input:, n=4, S = (1, 3, 4, 5, 6, 8, 9, 10, 13)kemungkinan keluaran:X = (3, 5, 1, 4)

Input:, n=6, S = (2, 3, 4, 5, 7, 8, 9, 10, 12, 14, 17, 22)kemungkinan keluaran:X = (5, 3, 2, 2, 5, 5)

Input:, n=6, S = (2, 4, 6, 8, 10, 12, 16)kemungkinan keluaran:X = (4, 2, 2, 2, 2, 4)

Input:, n=6, S = (1, 2, 3, 4, 6, 7, 8, 10, 14)kemungkinan keluaran:X = (4, 2, 1, 1, 2, 4)

Input: n=10, S = (1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 14, 15, 16, 17, 18, 19, 20, 23, 24, 25), mungkin keluaran: X = (1, 1, 3, 1, 2, 1, 2, 5, 4, 5).

Input: n=15, S = (1, 2, 3, 4, 6, 7, 8, 9, 10, 11, 13, 14, 15, 16, 17, 18, 20, 21, 22, 23, 24, 25, 26, 27, 28, 30, 31), mungkin keluaran: X = (1, 2, 1, 3, 3, 1, 3, 3, 1, 3, 3, 1, 2, 1, 3).

Format input dan output

Kode Anda dapat mengambil input dan memberikan output dalam format yang mudah dibaca yang menurut Anda nyaman. Namun, tolong tunjukkan hasil pengujian pada contoh-contoh dalam pertanyaan.

Durasi

Anda harus dapat menjalankan kode hingga selesai untuk semua contoh dalam pertanyaan. Pada prinsipnya harus benar nhingga 15tetapi Anda tidak perlu membuktikannya akan cukup cepat untuk semua input.

Anush
sumber
Komentar bukan untuk diskusi panjang; percakapan ini telah dipindahkan ke obrolan .
Dennis
Seharusnya memiliki test case dengan angka 2 digit.
Magic Octopus Mm

Jawaban:

6

Sekam , 20 byte

ḟȯ⁰¦ṁ∫ṫ!¡Sof~Λ€∫×:¹g

Cobalah online!

Mengembalikan satu solusi, atau daftar kosong jika tidak ada. Kasing uji terakhir ( n=15) selesai dalam 3,8 detik pada TIO.

Penjelasan

Program ini memiliki dua bagian. Pada bagian pertama ( ¡dan di sebelah kanannya), kita membangun daftar tak hingga yang kelemen ke-nya adalah daftar yang berisi semua kdaftar panjang yang jumlah irisannya S. Kami melakukan ini secara induktif, mulai dari irisan 1-elemen S, dan pada setiap langkah, menambahkan setiap elemen Ske setiap daftar, dan menjaga mereka yang memiliki jumlah awalan S. Di bagian kedua ( !dan di sebelah kiri), kita mengambil nelemen ke-10 dari daftar, yang berisi ndaftar panjang. Dari jumlah tersebut, kami memilih yang pertama yang jumlah irisannya sebenarnya mengandung setiap elemen S.

Dalam kode, pertama mari kita ganti odan ȯ(yang menyusun dua dan tiga fungsi menjadi satu) dengan tanda kurung untuk kejelasan.

¡S(f~Λ€∫)×:¹g  First part. Input is a list, say S=[1,2,3]
            g  Group equal adjacent elements: [[1],[2],[3]]
¡              Iterate function:
                Argument is a list of lists, say [[1,1],[1,2],[2,1]]
         ×      Mix (combine two lists in all possible ways)
          :     by prepending
           ¹    with the list S: [[1,1,1],[1,1,2],[2,1,1],[1,2,1],[2,1,2],[3,1,1],[2,2,1],[3,1,2],[3,2,1]]
   f            Filter by condition:
        ∫        Cumulative sums: [[1,2,3],[1,2,4],[2,3,4],[1,3,4],[2,3,5],[3,4,5],[2,4,5],[3,4,6],[3,5,6]]
     ~Λ          All of the numbers
 S     €         are elements of S: [[1,1,1]]
                 Only this list remains, since the other cumulative sums contain numbers not from S.
               Result of iteration: [[[1],[2],[3]],[[1,1],[1,2],[2,1]],[[1,1,1]],[],[],[]...

ḟ(⁰¦ṁ∫ṫ)!      Second part. Implicit input, say n=2.
        !      Take nth element of above list: [[1,1],[1,2],[2,1]]
ḟ              Find first element that satisfies this:
                Argument is a list, say [1,2]
      ṫ         Tails: [[1,2],[2]]
    ṁ           Map and concatenate
     ∫          cumulative sums: [1,3,2]
 ȯ ¦            Does it contain all elements of
  ⁰             S? Yes.
               Result is [1,2], print implicitly.

Ada beberapa bagian yang perlu penjelasan lebih lanjut. Dalam program ini, superskrip ⁰¹keduanya merujuk pada argumen pertama S. Namun, jika αada fungsi, maka α¹berarti "berlaku αuntuk S", sementara ⁰αberarti "tancapkan Ske argumen kedua α". Fungsi ¦memeriksa apakah argumen pertama berisi semua elemen yang kedua (menghitung multiplisitas), jadi Sharus argumen kedua.

Pada bagian pertama, fungsi yang ¡menggunakan dapat diartikan sebagai S(f~Λ€∫)(×:)¹. Combinator Sberperilaku seperti Sαβγ -> (αγ)(βγ), yang berarti bahwa kita dapat menyederhanakannya (f~Λ€∫¹)(×:¹). Bagian kedua ×:¹,, adalah "mix with Sby prepending", dan hasilnya diteruskan ke bagian pertama. Bagian pertama f~Λ€∫¹,, berfungsi seperti ini. Fungsi ini fmemfilter daftar berdasarkan suatu kondisi, yang dalam hal ini adalah ~Λ€∫¹. Ia menerima daftar daftar L, jadi kami punya ~Λ€∫¹L. Combinator ~berperilaku seperti ~αβγδε -> α(βδ)(γε): argumen pertama diteruskan ke β, yang kedua ke γ, dan hasilnya digabungkan dengan α. Ini artinya sudah kita miliki Λ(€¹)(∫L). Bagian terakhir ∫Lhanyalah jumlah kumulatif dari L,€¹adalah fungsi yang memeriksa keanggotaan S, dan Λmengambil kondisi (di sini €¹) dan daftar (di sini ∫L), dan memeriksa apakah semua elemen memuaskannya. Sederhananya, kami memfilter hasil pencampuran dengan apakah jumlah kumulatifnya semuanya S.

Zgarb
sumber
Saya menantikan penjelasannya!
Anush
1
@Anush saya menambahkan gangguan kode.
Zgarb
Saya sangat suka solusi ini. Agak cantik.
Anush
6

Ruby , 135 byte

->a,n{r=w=1;r+=1until w=(s=a[0,r]).product(*[s]*~-n).find{|x|x.sum==a.max&&a==[]|(1..n).flat_map{|r|x.each_cons(r).map(&:sum)}.sort};w}

Cobalah online!

Gunakan pencarian pertama yang luasnya. n = 10 bekerja pada TIO, n = 15 membutuhkan waktu lebih dari satu menit, tetapi bekerja pada mesin saya.

Ruby , 147 byte

->a,n{r=w=1;r+=1until w=([a[-1]-a[-2]]).product(*[s=a[0,r]]*~-n).find{|x|x.sum==a.max&&a==[]|(1..n).flat_map{|r|x.each_cons(r).map(&:sum)}.sort};w}

Cobalah online!

Versi yang dioptimalkan, bekerja pada TIO selama n = 15 (~ 20 dtk)

Sebenarnya, ini adalah awal dari pendekatan non-brute-force. Saya harap seseorang akan mengerjakannya dan menemukan solusi lengkap.

Ide pertama:

  • Jumlah array output adalah elemen terakhir (maks) dari array input.
  • Jumlah array output dikurangi elemen pertama (atau yang terakhir), adalah elemen terakhir kedua dari array input.
  • Jika array adalah solusi, maka array sebaliknya juga solusi, jadi kita dapat mengasumsikan elemen pertama adalah perbedaan antara 2 elemen terakhir dari array input.
  • Elemen kedua dapat menjadi perbedaan antara elemen terakhir kedua dan ketiga atau kedua dan keempat dari array input.

Yang membawa kami ke pengoptimalan berikutnya:

Ruby , 175 byte

->a,n{r=w=1;r+=1until w=([a[-1]-a[-2]]).product([a[-2]-a[-3],a[-2]-a[-4]],*[s=a[0,r]]*(n-2)).find{|x|x.sum==a.max&&a==[]|(1..n).flat_map{|r|x.each_cons(r).map(&:sum)}.sort};w}

Cobalah online!

~ 8,5 detik pada TIO. Tidak buruk...

... dan seterusnya (akan diterapkan)

GB
sumber
Ini terlihat sangat bagus!
Anush
Saya senang dengan algoritma non-brute force baru Anda. Jika Anda ingin lebih banyak contoh untuk diuji, saya dapat menambahkannya ke bagian baru dari pertanyaan.
Anush
2
@Anush Sebenarnya masih brute force (waktu eksponensial), tetapi dengan beberapa optimasi (faktor polinomial).
user202729
Bagi saya Anda lupa bahwa elemen pertama (elemen lebih kecil) selalu ada dalam solusi: jadi kami memiliki 1 dan yang terakhir (jumlah semua); dan Anda mengatakan yang terakhir terakhir tetapi ini bagi saya tidak jelas ... mungkin ada cara untuk menemukan semua yang lain dengan cara ini ...
RosLuP
5

Haskell, 117 111 byte

6 byte disimpan berkat @nimi!

f r i n s|n<1=[r|r==[]]|1<2=[y:z|y<-s,t<-[y:map(y+)i],all(`elem`s)t,z<-f[a|a<-r,all(a/=)t]t(n-1)s]
n&s=f s[]n s

Cobalah online!

frSins

Kapan nnol (diangkut ke n<1) daftar harus siap, jadi kami memeriksa apakah semua nilai telah terlihat. Jika tidak, kami mengembalikan daftar kosong untuk menunjukkan tidak ada solusi, kalau tidak kami mengembalikan daftar tunggal yang berisi daftar kosong, di mana elemen yang dipilih akan ditambahkan. Kasus ini juga bisa ditangani dengan persamaan tambahan

f [] _ 0 _=[[]]
f _ _ 0 _=[]

Jika ntidak nol, kami kembali

[y:z|y<-s,t<-[y:map(y+)i],all(`elem`s)t,z<-f[a|a<-r,all(a/=)t]t(n-1)s]
 ^1^ ^2^^ ^......3......^ ^.....4.....^ ^.............5.............^

Ini adalah daftar (1) daftar dari mana elemen pertama (2) berasal sdan sisanya (5) berasal dari panggilan rekursif, dalam kondisi (4) di mana semua jumlah baru berada s. Jumlah baru dihitung dalam (3) - catatan yang tdiambil dari daftar tunggal, peretasan golf jelek untuk apa yang akan Haskell idiomatik let t=y:map(y+)i. Panggilan rekursif (5) menjadi seperti baru rmengatur yang lama tanpa elemen-elemen yang muncul di antara jumlah baru t.

Fungsi utama &memanggil fungsi helper dengan mengatakan bahwa kita masih harus melihat semua nilai ( r=s) dan belum ada jumlah ( i=[]).

Untuk tujuh byte lebih, kita dapat membatasi perhitungan hanya memberikan hasil pertama (jika ada), yang jauh lebih cepat dan menangani semua kasus uji dalam waktu kurang dari 2 detik.

Cobalah online! (ini adalah variasi hanya hasil pertama dari versi lama)

Sievers Kristen
sumber
1
Ini luar biasa cepat. Jika Anda bisa menjelaskan algoritma yang bagus.
Anush
111 byte
nimi
Saya berpikir untuk mengajukan versi kode tercepat dari masalah ini. Apakah Anda pikir mungkin ada solusi waktu poli?
Anush
@nimi, terima kasih! Ah, bagus map, saya hanya mencoba <$>tetapi itu membutuhkan parens ekstra ... @Anush Saya tidak tahu solusi waktu polinomial
Christian Sievers
3

Bersih , 177 byte

import StdEnv,Data.List
$s n=find(\a=sort(nub[sum t\\i<-inits a,t<-tails i|t>[]])==s)(?{#u\\u<-s|u<=(last s)-n}(last s)n)
?e s n|n>1=[[h:t]\\h<-:e|h<=s-n,t<- ?e(s-h)(n-1)]=[[s]]

Cobalah online!

Memakan waktu sekitar 40 detik pada mesin saya untuk n=15test case, tetapi waktu habis pada TIO.

Bersih , 297 byte

import StdEnv,Data.List
$s n=find(\a=sort(nub[sum t\\i<-inits a,t<-tails i|t>[]])==s)(~[u\\u<-s|u<=(last s)-n](last s)n(reverse s))
~e s n a|n>4=let u=a!!0-a!!1 in[[u,h:t]\\h<-[a!!1-a!!2,a!!1-a!!3],t<- ?e(s-u-h)(n-2)]= ?e s n
?e s n|n>1=[[h:t]\\h<-e,t<- ?(takeWhile((>=)(s-n-h))e)(s-h)(n-1)]=[[s]]

Cobalah online!

Yang ini mencakup beberapa optimasi yang dibuat oleh GB dan juga beberapa dari saya. Saya pikir beberapa dari mereka dapat dibuat lebih umum, jadi saya akan menambahkan penjelasan setelah selesai.

Butuh sekitar 10 detik di mesin saya, 40 detik di TIO.

Suram
sumber
Bisakah Anda menguraikan optimasi yang Anda gunakan? Aku sangat tertarik.
Anush
1
@Anush saya akan mengedit jawaban dengan mereka dan @mentionAnda besok ketika mereka sudah habis, sayangnya tidak punya waktu hari ini.
Οurous
3

Python 3 , 177 byte

from itertools import*
s,n=eval(input())
for[*t]in combinations(s[:-2],n-2):
  a=[*map(int.__sub__,t+s[-2:],[0,*t,s[-2]])];
  {sum(a[p//n:p%n+1])for p in range(n*n)}^{0,*s}or-print(a)

Cobalah online!

(beberapa baris baru / spasi ditambahkan untuk menghindari pembaca harus menggulir kode)

Port langsung jawaban Jelly saya (dengan beberapa modifikasi, lihat bagian "catatan" di bawah)

Hasil penelusuran lokal:

[user202729@archlinux golf]$ printf '%s' "from itertools import*
s,n=eval(input())
for[*t]in combinations(s[:-2],n-2):a=[*map(int.__sub__,t+s[-2:],[0,*t,s[-2]])];{sum(a[p//n:p%n+1])for p in range(n*n)}^{0,*s}or-print(a)" > a.py
[user202729@archlinux golf]$ wc -c a.py
177 a.py
[user202729@archlinux golf]$ time python a.py<<<'([1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 14, 15, 16, 17, 18, 19, 20, 23, 24, 25], 10)' 2>/dev/null
[1, 4, 1, 1, 1, 1, 1, 7, 7, 1]

real    0m3.125s
user    0m3.119s
sys     0m0.004s
[user202729@archlinux golf]$ time python a.py<<<'([1, 2, 3, 4, 6, 7, 8, 9, 10, 11, 13, 14, 15, 16, 17, 18, 20, 21, 22, 23, 24, 25, 26, 27, 28, 30, 31], 15)' 2>/dev/null
[3, 1, 2, 1, 3, 3, 1, 3, 3, 1, 3, 3, 1, 2, 1]

real    11m36.093s
user    11m33.941s
sys     0m0.387s
[user202729@archlinux golf]$ 

Saya dengar itu itertoolsverbose, tetapi combinationsimplementasi terbaik saya bahkan lebih verbose:

c=lambda s,n,p:s and c(s[1:],n-1,p+s[:1])+c(s[1:],n,p)or[]if n else[p]

Catatan .

  • Menggunakan pembagian / modulo a[p//n:p%n+1]membutuhkan waktu sekitar 2x lebih lama, tetapi menghemat beberapa byte.
  • Ini sedikit berbeda dari jawaban Jelly - jawaban Jelly berulang ke belakang.
  • Berkat combinationsmengembalikan iterator, ini lebih ramah-memori.
pengguna202729
sumber
2

Jelly , 35 byte

Ẇ§QṢ⁼³
;³ṫ-¤0;I
ṖṖœcƓ_2¤¹Ṫ©ÇѬƲ¿ṛ®Ç

Cobalah online!

Jalankan secara lokal: (n = 15 membutuhkan lebih dari 1 GB RAM)

aaa@DESKTOP-F0NL48D MINGW64 ~/jellylanguage (master)
$ time python scripts/jelly fu z '[1,2,3,4,5,6,7,8,9,10,11,12,14,15,16,17,18,19,20,23,24,25]'<<<10
[8, 6, 2, 1, 1, 1, 1, 3, 1, 1]
real    0m1.177s
user    0m0.000s
sys     0m0.015s

aaa@DESKTOP-F0NL48D MINGW64 ~/jellylanguage (master)
$ time python scripts/jelly fu z '[1, 2, 3, 4, 6, 7, 8, 9, 10, 11, 13, 14, 15, 16, 17, 18, 20, 21, 22, 23, 24, 25, 2
6, 27, 28, 30, 31]'<<<15
[3, 1, 2, 1, 3, 3, 1, 3, 3, 1, 3, 3, 1, 2, 1]
real    12m24.488s
user    0m0.000s
sys     0m0.015s

(sebenarnya saya menjalankan versi UTF8-encoded, yang membutuhkan lebih dari 35 byte, tetapi hasilnya tetap sama)

Solusi ini menggunakan korsleting untuk mengurangi run-time.

(|S|2n2)×(n36+n2logn2)(262152)×(1536+152log152)5.79×109

Penjelasan

Kami mencatat bahwa jumlah semua awalan tidak kosong hadir dalam input, dan jumlahnya meningkat secara ketat. Kita juga dapat mengasumsikan bahwa elemen terbesar dan terbesar kedua adalah jumlah awalan.

n2|S|2(|S|2n2)n2n36


Belum diuji (tetapi harus memiliki kinerja yang identik)

Jelly , 32 byte

Ṫ©ÑẆ§QṢ⁻³
;³ṫ-¤ŻI
ṖṖœcƓ_2¤¹Ñ¿ṛ®Ç

Cobalah online!


Versi yang lebih tidak efisien (tanpa korsleting):

Jelly , 27 byte

Ẇ§QṢ⁼³
ṖṖœcƓ_2¤µ;³ṫ-¤0;I)ÑƇ

Cobalah online!

Untuk tes n = 15, dibutuhkan hingga 2GB RAM dan tidak berakhir setelah ~ 37 menit.


catatan : Ẇ§dapat diganti dengan ÄÐƤẎ. Mungkin lebih efisien.

pengguna202729
sumber
1

APL (NARS), karakter 758, byte 1516

r←H w;i;k;a;m;j
   r←⊂,w⋄→0×⍳1≥k←↑⍴w⋄a←⍳k⋄j←i←1⋄r←⍬⋄→C
A: m←i⊃w⋄→B×⍳(i≠1)∧j=m⋄r←r,m,¨∇w[a∼i]⋄j←m
B: i+←1
C: →A×⍳i≤k

G←{H⍵[⍋⍵]}

r←a d w;i;j;k;b;c
   k←↑⍴w ⋄b←⍬⋄r←0 ⋄j←¯1
A: i←1⋄j+←1⋄→V×⍳(i+j)>k
B: →A×⍳(i+j)>k⋄c←+/w[i..(i+j)]⋄→0×⍳∼c∊a⋄→C×⍳c∊b⋄b←b,c
C: i+←1⋄→B
V: →0×⍳∼a⊆b
   r←1

r←a F w;k;j;b;m;i;q;x;y;c;ii;kk;v;l;l1;i1;v1
   w←w[⍋w]⋄r←a⍴w[1]⋄l←↑⍴w⋄k←w[l]⋄m←8⌊a-2⋄b←¯1+(11 1‼m)⋄j←2⋄i←1⋄x←↑⍴b⋄i1←0⋄v1←⍬
I: i1+←1⋄l1←w[l]-w[l-i1]⋄v1←v1,w[1+l-i1]-w[l-i1]⋄→I×⍳(l1=i1)∧l>i1⋄→B
E: r←,¯1⋄→0
F: i←1⋄q←((1+(a-2)-m)⍴0),(m⍴1),0⋄r+←q
A:   i+←1⋄j+←1⋄→E×⍳j>4000
B:   →F×⍳i>x⋄q←((1+(a-2)-m)⍴0),b[i;],0⋄q+←r⋄v←q[1..(a-1)]⋄→A×⍳0>k-y←+/v
   q[a]←k-y⋄→A×⍳l1<q[a]⋄→A×⍳∼q⊆w⋄→A×⍳∼l1∊q⋄→A×⍳∼v1⊆⍦q⋄c←G q∼⍦v1⋄ii←1⋄kk←↑⍴c⋄→D
C:   →Z×⍳w d v1,ii⊃c⋄ii+←1
D:   →C×⍳ii≤kk
   →A
Z: r←v1,ii⊃c

Fungsi G dalam G x (dengan bantuan fungsi H) akan menemukan semua permutasi x. Fungsi d dalam xdy mencari apakah array y menghasilkan mengikuti array latihan x mengembalikan nilai Boolean. Fungsi F dalam x F y akan mengembalikan array r dengan panjang x, sedemikian sehingga ydr benar (= 1) Sedikit lama implementasi, tetapi inilah yang menghitung semua kasus dalam pengujian lebih sedikit waktu ... Kasus terakhir untuk n = 15 hanya berjalan 20 detik saja ... saya harus mengatakan ini tidak menemukan banyak solusi, kembalikan hanya satu solusi (akhirnya sepertinya begitu) dalam waktu yang lebih singkat (tidak dieksplorasi tes untuk input yang berbeda ...) 16 + 39 + 42 + 8 + 11 + 11 + 18 + 24 + 24 + 54 + 11 + 12 + 7 + 45 + 79 + 69 + 12 + 38 + 26 + 72 + 79 + 27 + 15 + 6 + 13 (758)

  6 F (2, 3, 4, 5, 7, 8, 9, 10, 12, 14, 17, 22)
5 3 2 2 5 5 
  6 F (2, 4, 6, 8, 10, 12, 16)
4 2 2 2 2 4 
  6 F (1, 2, 3, 4, 6, 7, 8, 10, 14)
4 2 1 1 2 4 
  10 F (1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 14, 15, 16, 17, 18, 19, 20, 23, 24, 25)
1 1 3 1 2 3 5 1 3 5 
  15 F (1, 2, 3, 4, 6, 7, 8, 9, 10, 11, 13, 14, 15, 16, 17, 18, 20, 21, 22, 23, 24, 25, 26, 27, 28, 30, 31)
1 2 1 3 3 1 3 3 1 3 3 1 2 1 3 
  ww←(1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 14, 15, 16, 17, 18, 19, 20, 23, 24, 25)
  ww≡dx 1 1 3 1 2 3 5 1 3 5 
1
RosLuP
sumber