Wir setzen Bälle in eine feste Anzahl ein Behälter. Diese Fächer beginnen leer.

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

Und eins nach dem anderen fügen wir Bälle zu den Behältern hinzu.

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

Wir brauchen einen schnellen Weg, um alle möglichen Zustände, die die Bins annehmen, ohne Duplikate und ohne fehlende zu durchlaufen, und wir wollen nicht alle möglichen Bins aufzählen. Also ordnen wir stattdessen jeder Bin-Konfiguration einen Index zu.

Wir ordnen den Index zu, indem wir die möglichen Konfigurationen auf eine bestimmte Weise sortieren:

1. Aufsteigend nach Summe sortieren: also zuerst 0 0 0 0die möglichen Konfigurationen mit 1 Ball addieren, dann 2, etc.

2. Sortieren Sie dann innerhalb jeder Summe in aufsteigender Reihenfolge vom ersten bis zum letzten Behälter:

   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. Der Index wird dann aufsteigend über diese Liste zugeordnet:

   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 
   

Regeln

Erstellen Sie eine Funktion oder ein Programm, das eine Liste beliebiger Größe mit nicht negativen Ganzzahlen erstellt, und geben Sie den Index aus oder geben Sie ihn aus. Sie können davon ausgehen , eine mindestens 2 Kürzeste Code gewinnt zu sein. Sie können 0-indizierte oder 1-indizierte Ausgaben verwenden, aber angeben, welche Sie verwenden. NB: Alle Beispiele hier sind 1-indiziert.

Beispielcode

Nicht golfen, in 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)
} 

Testfälle

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

Gelee , 8 Bytes

S0rṗLSÞi

Probieren Sie es online!

Brute-Force-Lösung. Der erste Testfall ist zu viel für TIO, aber ich habe ihn lokal auf meinem Laptop überprüft. Der zweite Testfall erfordert zu viel RAM, auch für meinen Desktop-Computer.

Wie es funktioniert

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 Bytes

#(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)))))

Nicht so einfach wie ich dachte. Weniger Golf Version:

(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)))))))

Schleifen über aktuelle Zustände v und erstellt eine Hash-Map aus Elementen mit vbis zu ihrem Rang. Wenn der gesuchte Zustand gefunden wird, wird sein Rang zurückgegeben (+ die Anzahl der zuvor gesehenen Zustände). Wenn nicht gefunden, wird mit einer neuen Menge möglicher Zustände fortgefahren.

Eigentlich brauchen wir diese benutzerdefinierte Sortierfunktion nicht, da alle Zustände in jeder Schleife die gleiche Summe haben. Dies ist nicht so langsam, wie ich erwartet hatte, da es [3 1 4 1 5 9]nur 2,6 Sekunden gedauert hat.

Mathematica, 50 Bytes

Ein Port von Dennis 'Jelly-Antwort .

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

Unbenannte Funktion, die eine Liste von Ganzzahlen als Eingabe verwendet und eine Liste der Tiefe 2 mit einer einzelnen Ganzzahl als Ausgabe zurückgibt; Beispielsweise ist die Eingabe für den letzten Testfall {1,0,0,0,0,1}und die Ausgabe ist{{23}} .

Eine leicht ungolfederte Version ist:

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

Oft können wir in Mathematica einzelne Bytes speichern, indem wir Präfixnotation ( function@nanstelle von function[n]) und Infixnotation ( a~function~banstelle von function[a,b]) verwenden. Dies funktioniert jedoch nur, wenn der resultierende Code gut mit der Vorrangreihenfolge von Mathematica für das Anwenden von Funktionen übereinstimmt. Ich war ein bisschen erstaunt, dass es bei sechs Sätzen von eckigen Klammern tatsächlich funktionierte, alle zu entfernen und sechs Bytes mit dem (angenehm klammerlosen) Code zu sparen.