Partisi vektor membagi vektor ke atas serangkaian vektor sehingga penjumlahannya adalah yang asli. Berikut adalah beberapa partisi:

[3, 1, 2] = [3, 1, 2]
[3, 1, 2] = [0, 0, 1] + [0, 0, 1] + [0, 1, 0] + [1, 0, 0] + [2, 0, 0]
[3, 1, 2] = [1, 1, 2] + [2, 0, 0]

Di sini penambahan vektor dilakukan berdasarkan elemen. Partisi yang valid tidak mengandung vektor dengan bilangan bulat negatif, atau vektor semua-nol.

Sekarang tantangannya adalah untuk menulis program atau fungsi yang menghasilkan semua partisi vektor yang mungkin diberikan vektor target. Ini mungkin terdengar relatif mudah ...

... tapi ada twist. Jika vektor input berukuran L, dan partisi terbesar yang dihasilkannya memiliki elemen M, Anda tidak boleh menggunakan lebih dari memori O (L * M).

Anda dapat mengasumsikan bahwa integer menggunakan memori O (1). Ini berarti bahwa Anda harus menampilkan partisi saat Anda menghasilkannya. Selain itu, Anda hanya harus mengeluarkan setiap partisi tepat sekali. Sebagai contoh, ini adalah partisi yang sama:

[3, 1, 2] = [3, 0, 2] + [0, 1, 0]
[3, 1, 2] = [0, 1, 0] + [3, 0, 2]

Jika Anda ingin menampilkan kedua jawaban Anda tidak valid.

Semua partisi untuk [3, 2]:

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

Untuk menguji jawaban Anda, jalankan di [3, 2, 5, 2]. Itu harus menghasilkan 17939 partisi, yang semuanya berjumlah [3, 2, 5, 2], dan itu semua unik (Anda dapat menguji keunikan dengan terlebih dahulu menyortir setiap partisi secara leksikografis).

Kode terpendek dalam byte menang.

Python 2, 289 byte

Algoritma brute force sederhana. Perlakukan seluruh daftar sebagai angka dalam basis max(input)+1( b), dan periksa setiap "nomor" dalam rentang [0, b**(L*M))untuk melihat apakah itu:

1. Jumlah ke jumlah yang benar
2. Berurutan sesuai abjad (memastikan keunikan)

Jika daftar cocok dengan kriteria ini, program mengeluarkannya dengan semua vektor nol nol dilucuti.

Penggunaan memori

Struktur data terbesar yang saya gunakan dalam program ini adalah daftar bersarang ganda, panjang daftar yang Mberisi panjang kutu Luntuk memberikan O(L*M)memori.

Untuk struktur data saya yang lain, saya memiliki 3 int global O(3), 1 panjang daftar L( O(L)), 1 panjang array M( O(M)), dan salinan array terbesar saat menghasilkan ( O(L*M)).

Secara total, ini memberi saya penggunaan memori O(2*L*M + L + M + 3)yang disederhanakan O(L*M), memenuhi kriteria.

Kompleksitas waktu

Menjadi algoritma brute force, algoritma ini sangat lambat. Agar loop sementara berhenti, int terakhir dalam array harus b-1. Loop perlu dijalankan beberapa b**(L*M)kali sebelum itu terjadi.

Selain itu, setiap kali daftar berjalan, perlu memeriksa kedua kondisi, dan mencetak daftar dalam kasus terburuk, menggunakan L*M+L+Miterasi. Ini disederhanakan untuk memberikan keseluruhan O(L*M * b**(L*M)). Saya mencoba untuk menguji program saya [3, 2, 5, 2], tetapi menyerah setelah 45 menit.

Program golf

v=input()
L=len(v)
M=sum(v)
b=max(v)
R=range
t=[L*[0]for i in R(M)]
def A(l,i):
 if i<L*M-1and~-b<l[i/L][i%L]:A(l,i+1)
 l[i/L][i%L]=-~l[i/L][i%L]%-~b
while t[-1][-1]<b:
 if v==[sum(q[i]for q in t)for i in R(L)]and all(`t[i]`>=`t[i+1]`for i in R(M-1)):print[x for x in t if[0]*L!=x]
 A(t,0)

Saya mungkin bisa bermain golf ini sedikit lebih, terutama bagian increment. Kode tidak diundang datang.