Мы кладем шарики в фиксированном числе через бункера. Эти контейнеры начинаются пустыми.

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

И один за другим мы добавляем шары в контейнеры.

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

Нам нужен быстрый способ перебрать все возможные состояния бинов, без дубликатов и без пропусков, и мы не хотим перечислять все возможные бины. Таким образом, вместо этого мы присваиваем каждой конфигурации bin индекс.

Мы назначаем индекс, сортируя возможные конфигурации определенным образом:

1. Сортировка по возрастанию по сумме: сначала 0 0 0 0, затем возможные конфигурации с добавлением 1 шара, затем 2 и т. Д.

2. Затем выполните сортировку по каждой сумме в порядке возрастания, от первого до последнего:

   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. Индекс затем назначается по возрастанию через этот список:

   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 
   

правила

Создайте функцию или программу, которая принимает список любого размера с неотрицательными целыми числами и печатает или выводит его индекс. Можно предположить, что a равно как минимум 2. Победит самый короткий код. Вы можете использовать 0-индексированный вывод или 1-индексированный, но укажите, какой вы используете. NB: все примеры здесь 1-индексированы.

Пример кода

Не в гольф, в 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)
} 

Контрольные примеры

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

Желе , 8 байт

S0rṗLSÞi

Попробуйте онлайн!

Решение для грубой силы. Первый тестовый пример слишком сложен для TIO, но я проверил его локально на своем ноутбуке. Второй тест требует слишком много оперативной памяти, даже для моего настольного компьютера.

Как это устроено

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 байта

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

Не так просто, как я думал. Менее гольф-версия:

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

Зацикливает текущие состояния v, создает хэш-карту из элементов vих ранга, если искомое состояние найдено, то возвращается его ранг (+ количество ранее просмотренных состояний). Если не найдено, то рекурсы с новым набором возможных состояний.

О, на самом деле нам не нужна эта пользовательская функция сортировки, поскольку все состояния в каждом цикле имеют одинаковую сумму. Это не так медленно, как я ожидал, поскольку [3 1 4 1 5 9]заняло всего 2,6 секунды.

Mathematica, 50 байтов

Порт Дениса Желе ответ .

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

Безымянная функция, принимающая список целых чисел в качестве входных данных и возвращающая список глубины 2 с одним целым числом в качестве выходных данных; например, вход для последнего контрольного примера равен, {1,0,0,0,0,1}а выход - {{23}}.

Немного неутешительная версия:

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

Часто мы можем сохранять отдельные байты в Mathematica, используя префиксную нотацию ( function@nвместо function[n]) и инфиксную нотацию ( a~function~bвместо function[a,b]). Это работает, однако, только когда полученный код хорошо сочетается с внутренним порядком приоритета Mathematica для применения функций. Я был немного удивлен, что с шестью наборами квадратных скобок фактически удалось удалить все из них и сохранить шесть байтов с (приятно без скобок) представленным кодом.