Kami menempatkan bola ke nomor tetap sebuah tempat sampah. Tempat sampah ini mulai kosong.
Empty bin (a=4): 0 0 0 0
Dan satu demi satu kami menambahkan bola ke tempat sampah.
0 0 0 1 or
0 0 1 0 or
0 1 0 0 or
1 0 0 0
Kami membutuhkan cara cepat untuk mengulang semua kemungkinan keadaan yang diambil, tanpa duplikat dan tanpa kehilangan, dan kami tidak ingin menghitung semua kemungkinan sampah. Jadi alih-alih, kami menetapkan indeks konfigurasi masing-masing bin.
Kami menetapkan indeks dengan mengurutkan konfigurasi yang mungkin dengan cara tertentu:
- Urutkan naik dengan jumlah: jadi pertama
0 0 0 0
, maka konfigurasi yang mungkin dengan 1 bola ditambahkan, lalu 2, dll. Kemudian urutkan dalam setiap jumlah dalam urutan menaik, dari nampan pertama ke yang terakhir:
0 0 0 2 0 0 1 1 0 0 2 0 0 1 0 1 0 1 1 0 0 2 0 0 etc
Indeks kemudian ditugaskan naik melalui daftar ini:
0 0 0 0 -> 1 0 0 0 1 -> 2 0 0 1 0 -> 3 0 1 0 0 -> 4 1 0 0 0 -> 5 0 0 0 2 -> 6 0 0 1 1 -> 7 0 0 2 0 -> 8 0 1 0 1 -> 9 0 1 1 0 -> 10 0 2 0 0 -> 11
Aturan
Buat fungsi atau program yang mengambil daftar ukuran apa pun dengan bilangan bulat non-negatif dan cetak atau output indeksnya. Anda dapat mengasumsikan suatu setidaknya 2. Terpendek menang kode. Anda dapat menggunakan output 0-diindeks atau 1-diindeks, tetapi tentukan yang Anda gunakan. NB: semua contoh di sini diindeks 1.
Kode contoh
Tidak golf, di R:
nodetoindex <- function(node){
a <- length(node)
t <- sum(node)
if(t == 0) return(1)
index <- choose(t-1 + a, a)
while(sum(node) != 0){
x <- node[1]
sumrest <- sum(node)
if(x == 0){
node <- node[-1]
next
}
a <- length(node[-1])
index <- index + choose(sumrest + a, a) - choose(sumrest - x + a, a)
node <- node[-1]
}
return(index + 1)
}
Uji kasus
10 10 10 10 -> 130571
3 1 4 1 5 9 -> 424407
2 9 -> 69
0 0 0 -> 1
0 0 1 -> 2
0 0 0 0 0 0 -> 1
1 0 0 0 0 1 -> 23
Jawaban:
Jelly , 8 byte
Cobalah online!
Solusi brute-force. Kasing uji pertama terlalu banyak untuk TIO, tetapi saya telah memverifikasi secara lokal di laptop saya. Kasing uji kedua membutuhkan terlalu banyak RAM, bahkan untuk komputer desktop saya.
Bagaimana itu bekerja
sumber
Clojure, 152 byte
Tidak semudah yang saya kira. Versi yang kurang golf:
Loop atas status saat ini
v
, membuat peta hash dari elemenv
ke peringkat mereka, jika negara yang dicari ditemukan maka peringkatnya dikembalikan (+ jumlah negara yang terlihat sebelumnya). Jika tidak ditemukan maka muncul kembali dengan set baru kemungkinan negara.Oh sebenarnya kita tidak memerlukan fungsi pengurutan khusus karena semua negara dalam setiap loop memiliki jumlah yang identik. Ini tidak selambat yang saya harapkan
[3 1 4 1 5 9]
hanya butuh 2,6 detik.sumber
Mathematica, 50 byte
Port jawaban Dennis's Jelly .
Fungsi tanpa nama mengambil daftar bilangan bulat sebagai input, dan mengembalikan daftar kedalaman-2 dengan bilangan bulat tunggal sebagai output; misalnya, input untuk case uji terakhir adalah
{1,0,0,0,0,1}
dan outputnya{{23}}
.Versi yang sedikit tidak diubah adalah:
Seringkali kita dapat menyimpan byte individual dalam Mathematica dengan menggunakan notasi awalan (
function@n
bukanfunction[n]
) dan notasi infiks (a~function~b
bukanfunction[a,b]
). Ini hanya bekerja, bagaimanapun, ketika kode yang dihasilkan terjadi untuk menyatu dengan urutan prioritas intrinsik Mathematica untuk menerapkan fungsi. Saya agak kagum di sini bahwa, dengan enam set tanda kurung siku, itu benar-benar bekerja untuk menghapus semuanya dan menghemat enam byte dengan kode yang dikirimkan (tanpa tanda kurung ).sumber