Stawiamy kulki na ustaloną liczbę ciągu pojemników. Te pojemniki zaczynają się puste.

Empty bin (a=4): 0 0 0 0 

I jeden po drugim dodajemy kule do pojemników.

0 0 0 1  or
0 0 1 0  or
0 1 0 0  or
1 0 0 0

Potrzebujemy szybkiego sposobu na obejście wszystkich możliwych stanów, które przyjmują pojemniki, bez duplikatów i żadnych braków, i nie chcemy wyliczać wszystkich możliwych pojemników. Zamiast tego przypisujemy każdej konfiguracji bin indeks.

Indeks przypisujemy, sortując możliwe konfiguracje w określony sposób:

1. Sortuj rosnąco według sumy: najpierw najpierw 0 0 0 0możliwe konfiguracje z 1 kulą, potem 2 itd.

2. Następnie posortuj w obrębie każdej sumy w porządku rosnącym, od pierwszego pojemnika do ostatniego:

   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
   

3. Indeks jest następnie przypisywany rosnąco za pomocą tej listy:

   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 
   

Zasady

Utwórz funkcję lub program, który pobiera listę dowolnego rozmiaru z nieujemnymi liczbami całkowitymi i wypisz lub wypisz jej indeks. Można założyć, być co najmniej 2. Najkrótsze wygrywa kod. Możesz użyć danych wyjściowych z indeksowaniem 0 lub 1 z indeksowaniem, ale określ, którego używasz. Uwaga: wszystkie przykłady są tutaj indeksowane 1.

Przykładowy kod

Nie grał w golfa, w 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)
} 

Przypadki testowe

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

Galaretka , 8 bajtów

S0rṗLSÞi

Wypróbuj online!

Rozwiązanie siłowe. Pierwszy przypadek testowy to za dużo dla TIO, ale zweryfikowałem to lokalnie na moim laptopie. Drugi przypadek testowy wymaga zbyt dużej pamięci RAM, nawet na moim komputerze stacjonarnym.

Jak to działa

S0rṗLSÞi  Main link. Argument: A (array)

S         Compute the sum s of A.
 0r       Create the range [0, ..., s].
    L     Yield the length l of A.
   ṗ      Cartesian power; yield the array of all l-tuples over [0, ..., s], in
          lexicographical order.
     SÞ   Sort the l-tuples by their sums. The sorting mechanism is stable, so
          l-tuples with the same sum are still ordered lexicographically.
       i  Find the index of A in the generated array of tuples.

Clojure, 152 bajty

#(loop[v[(vec(repeat(count %)0))]i 1](if-let[r((zipmap v(range))%)](+ r i)(recur(sort(set(for[v v i(range(count v))](update v i inc))))(+ i(count v)))))

Nie tak łatwe, jak myślałem. Wersja mniej golfowa:

(def f (fn[t](loop[v[(vec(repeat(count t)0))]i 1]
               (if-let[r((zipmap v(range))t)](+ r i)
                 (recur (sort-by (fn[v][(apply + v)v]) (set(for[v v i(range(count v))](update v i inc))))
                        (+ i(count v)))))))

Pętle nad aktualnymi stanami v, tworzy mapę skrótów z elementów vdo ich rangi, jeśli znaleziony stan zostanie znaleziony, wówczas zwrócony zostanie jego stopień (+ liczba wcześniej widzonych stanów). Jeśli nie zostanie znaleziony, powtarza się z nowym zestawem możliwych stanów.

Och, właściwie nie potrzebujemy tej niestandardowej funkcji sortowania, ponieważ wszystkie stany w każdej pętli mają identyczną sumę. To nie jest tak wolne, jak się spodziewałem, [3 1 4 1 5 9]zajęło tylko 2,6 sekundy.

Mathematica, 50 bajtów

Port galaretki Dennisa .

0~Range~Tr@#~Tuples~Length@#~SortBy~Tr~Position~#&

Nienazwana funkcja przyjmuje listę liczb całkowitych jako dane wejściowe i zwraca listę głębokości 2 z jedną liczbą całkowitą jako dane wyjściowe; na przykład dane wejściowe dla ostatniego przypadku testowego to, {1,0,0,0,0,1}a dane wyjściowe to {{23}}.

Nieco golfowa wersja to:

Position[SortBy[Tuples[Range[0,Tr[#]],Length[#]],Tr],#]&

Często możemy zapisywać poszczególne bajty w Mathematica za pomocą notacji prefiksowej ( function@nzamiast function[n]) i notacji infixowej ( a~function~bzamiast function[a,b]). Działa to jednak tylko wtedy, gdy powstały kod dobrze współgra z wewnętrznym porządkiem pierwszeństwa Mathematica dla stosowania funkcji. Byłem trochę zaskoczony, że przy sześciu zestawach nawiasów kwadratowych faktycznie udało się usunąć wszystkie z nich i zaoszczędzić sześć bajtów za pomocą (przyjemnie pozbawionego nawiasów) kodu.