Можно ли получить индекс комбинации, не генерируя ее?

Question

Я имею в виду функцию, которая принимает массив элементов и комбинацию в качестве параметров и возвращает число, представляющее индекс комбинации без генерации каждой комбинации.

У меня нет предпочтений, она может быть влюбой язык программирования.

Пример кода getCombinationIndex("114") и должен возвращать индекс комбинации 114.

[1,1,1]: 1
[2,1,1]: 2
[3,1,1]: 3
[4,1,1]: 4
[.....]
[1,1,4]: ?

Answer 1

Эта проблема может рассматриваться как базовое преобразование.Для начала вам понадобится две информации, и тогда это будет только базовое преобразование.

1. Основание
   В вашем случае это наибольшее количество всех предметов.
   [4,1,1] -> 4
2. Желаемая комбинация
   

Это работает только при условии, что все предметы могут иметь одинаковый максимум.

---

Алгоритм

1. Обратный порядок элементов
2. Уменьшение каждого элемента на 1
3. Преобразование числа в основание 10
4. Увеличение на 1

---

Пример

1. Начало: 114
2. Реверс: 411
3. Уменьшение: 300
4. Преобразование:
   База 4: 300
   База 10: 3 * 4 ^ 2 + 0 * 4 ^ 1 + 0 * 4 ^ 0 = 24
5. Инкремент: 25

Answer 2

Допустим, вы рассматриваете комбинации k символов из алфавита A = {a_0, a_1, ..., a_n} (то есть с n символами и a_i < a_j лексикографически, если i < j).В вашем примере у вас есть алфавит из 4 символов A = {1, 2, 3, 4} и комбинаций k = 3 символов.

Затем комбинация c = [a_i1, a_i2, ..., a_ik] может быть уникально закодирована как I(c) = i1 + n*i2 + (n^2)*i3 + ... + (n^(k-1))*ik.Индекс, который вы ищете: F(c) = I(c) + 1.

---

Давайте посмотрим, как это работает для вашего примера:

F([1,1,1]) = I([1,1,1]) + 1 = 0 + 4*0 + (4^2)*0 + 1 = 1
F([2,1,1]) = I([2,1,1]) + 1 = 1 + 4*0 + (4^2)*0 + 1 = 2
F([3,1,1]) = I([2,1,1]) + 1 = 2 + 4*0 + (4^2)*0 + 1 = 3
F([4,1,1]) = I([2,1,1]) + 1 = 3 + 4*0 + (4^2)*0 + 1 = 4
...
F([2,1,3]) = I([2,2,3]) + 1 = 1 + 4*1 + (4^2)*2 + 1 = 38
...
F([1,1,4]) = I([1,1,4]) + 1 = 0 + 4*0 + (4^2)*3 + 1 = 49
...
F([4,4,4]) = I([4,4,4]) + 1 = 3 + 4*3 + (4^2)*3 + 1 = 64