Convert a sample to an index

Question

We are putting balls into a fixed number a bins. These bins begin empty.

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

And one by one we add balls to the bins.

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

We need a quick way to loop over all the possible states the bins take, without duplicates and without missing any and we don't want to enumerate all the possible bins. So instead we assign each bin-configuration an index.

We assign the index by sorting the possible configurations in a specific way:

1. Sort ascending by sum: so first 0 0 0 0, then the possible configurations with 1 ball added, then 2, etc.

2. Then sort within each sum in ascending order, from the first bin to the last:

   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. The index is then assigned ascending through this list:

   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 
   

Rules

Create a function or program that takes a list of any size with non-negative integers and print or output its index. You can assume a to be at least 2. Shortest code wins. You may use 0-indexed output or 1-indexed, but specify which you use. NB: all examples here are 1-indexed.

Example code

Not golfed, 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)
} 

Test cases

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

Answer 1

Jelly, 8 bytes

S0rṗLSÞi

Try it online!

Brute-force solution. The first test case is too much for TIO, but I've verified it locally on my laptop. The second test case requires too much RAM, even for my desktop computer.

How it works

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.

Answer 2

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

Not as easy as I thought. Less golfed 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)))))))

Loops over current states v, creates a hash-map from elements of v to their rank, if the searched state is found then its rank is returned (+ the number of previously seen states). If not found then recurses with a new set of possible states.

Oh actually we don't need that custom sorting function as all states within each loop has identical sum. This isn't as slow as I expected as [3 1 4 1 5 9] took only 2.6 seconds.

Answer 3

Mathematica, 50 bytes

A port of Dennis's Jelly answer.

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

Unnamed function taking a list of integers as input, and returning a depth-2 list with a single integer as output; for example, the input for the last test case is {1,0,0,0,0,1} and the output is {{23}}.

A slightly ungolfed version is:

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

Often we can save individual bytes in Mathematica by using prefix notation (function@n instead of function[n]) and infix notation (a~function~b instead of function[a,b]). This only works, however, when the resulting code happens to mesh well with Mathematica's intrinsic precedence order for applying functions. I was kind of amazed here that, with six sets of square brackets, it actually worked to remove all of them and save six bytes with the (pleasantly bracketless) submitted code.