Как рассчитать индекс (лексикографический порядок) при заданной комбинации

Question

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

Например:

combination(10, 5)  
1 - 1 2 3 4 5  
2 - 1 2 3 4 6  
3 - 1 2 3 4 7  
....  
251 - 5 7 8 9 10  
252 - 6 7 8 9 10  

Мне нужно, чтобы алгоритм возвращал индекс данной комбинации.
es: index( 2, 5, 7, 8, 10 ) -> индекс

РЕДАКТИРОВАТЬ: на самом деле я использую Java-приложение, которое генерирует все комбинации C (53, 5) и вставляет их в TreeMap. Моя идея состоит в том, чтобы создать массив, содержащий все комбинации (и связанные данные), которые я могу индексировать с помощью этого алгоритма.
Все для ускорения поиска комбинации. Однако я попробовал некоторые (не все) ваши решения и предложенные вами алгоритмы медленнее, чем get () из TreeMap.
Если это поможет: мои потребности в комбинации 5 из 53, начиная с 0 до 52.

Еще раз спасибо всем: -)

Answer 1

Предполагая, что максимальный setSize не слишком велик, вы можете просто сгенерировать таблицу поиска, где входы кодируются следующим образом:

  int index(a,b,c,...)
  {
      int key = 0;
      key |= 1<<a;
      key |= 1<<b;
      key |= 1<<c;
      //repeat for all arguments
      return Lookup[key];
  } 

Чтобы сгенерировать таблицу поиска, посмотрите на this "Банковский ордер "алгоритм .Создайте все комбинации, а также сохраните базовый индекс для каждого элемента nItems. (для примера на p6 это будет [0,1,5,11,15]). Обратите внимание, что, сохраняя ответы в порядке, противоположном примеру (LSB установлены первыми), вы будетенужна только одна таблица, размер которой соответствует максимально возможному набору.

Заполните таблицу поиска, пройдя по комбинациям, выполнив Lookup[combination[i]]=i-baseIdx[nItems]

Answer 2

РЕДАКТИРОВАТЬ: не важно. Это совершенно неправильно.

---

Пусть ваша комбинация будет (a ₁ , a ₂ , ..., a _k-1 , a _k ) где a ₁ 2 <... <a <sub>k . Пусть выбирают (a, b) = a! / (B! * (A-b)!), Если a> = b и 0 в противном случае. Тогда индекс, который вы ищете, равен

выберите (a _k -1, k) + выберите (a _k-1 -1, k-1) + выберите (a _k-2 -1, k-2) + ... + выберите (a ₂ -1, 2) + выберите (a ₁ -1, 1) + 1

Первый член подсчитывает количество комбинаций k-элементов, так что самый большой элемент меньше _k . Второе слагаемое подсчитывает количество комбинаций (k-1) -элементов, так что самый большой элемент меньше, чем _k-1 . И так далее.

Обратите внимание, что размер юниверса элементов, из которых нужно выбрать (в вашем примере 10), не играет роли в вычислении индекса. Вы понимаете почему?