Вычислить разряд комбинации?

Используйте хеш-таблицу для хранения результатов . Хорошая хеш-функция может выглядеть примерно так:

h (x) = (x1 * p ^ (k - 1) + x2 * p ^ (k - 2) + ... + xk * p ^ 0)% pp

Где x1 ... xk - числа в вашей комбинации (например, (0, 1, 2) имеет x1 = 0, x2 = 1, x3 = 2 ) и p и pp являются простыми числами.

Таким образом, вы должны сохранить Hash [h (0, 1, 2)] = 78 , а затем получить его таким же образом.

Примечание : хеш-таблица - это просто массив размером pp , а не dict.

На данный момент я пришел к компромиссу: у меня есть массив 13x13x13, который просто сопоставляется с индексом комбинации, занимая 13x13x13x2 байта = 4 килобайта (с использованием коротких целых чисел), плюс нормальный -размер (13 выберите 3) * 2 килобайта = 572 килобайта, всего 576 килобайт. Намного лучше, чем 4 мегабайта, а также быстрее, чем вычисление ранга!

Я сделал это отчасти из-за того, что, похоже, я не мог заставить ответ Морона работать. Кроме того, это более расширяемо - у меня есть случай, когда мне нужны комбинации с повторениями, и я еще не нашел способа вычислить их ранг.

То, что вам нужно, называется комбинадиками . Вот моя реализация этой концепции на Python:

def nthresh(k, idx):
  """Finds the largest value m such that C(m, k) <= idx."""
  mk = k
  while ncombs(mk, k) <= idx:
    mk += 1
  return mk - 1


def idx_to_set(k, idx):
  ret = []
  for i in range(k, 0, -1):
    element = nthresh(i, idx)
    ret.append(element)
    idx -= ncombs(element, i)
  return ret


def set_to_idx(input):
  ret = 0
  for k, ck in enumerate(sorted(input)):
    ret += ncombs(ck, k + 1)
  return ret

Вы можете попробовать использовать лексикографический указатель комбинации. Возможно, вам поможет эта страница: http://saliu.com/bbs/messages/348.html

Эта страница MSDN содержит более подробную информацию: Создание m-го лексикографического элемента математической комбинации .

Чтобы быть более конкретным:

При обработке как кортеже вы можете упорядочить комбинации лексикографически.

Итак, (0,1,2) <(0,1,3) <(0,1,4) и т. Д.

Допустим, у вас было число от 0 до n-1, и вы выбрали k из них.

Теперь, если первый элемент равен нулю, вы знаете, что это один из первых n-1, выберите k-1.

Если первый элемент равен 1, то это один из следующих n-2, выберите k-1.

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

Это тоже работает в обратном порядке, и на странице MSDN объясняется, как это сделать.

Я бы предложил специализированную хэш-таблицу. Хэш для комбинации должен быть эксклюзивным или исключением из хэшей для значений. Хэши для значений - это, по сути, случайные битовые шаблоны.

Вы можете закодировать таблицу, чтобы справиться с коллизиями, но будет довольно легко вывести минимально совершенную хэш-схему - такую, где никакие две комбинации из трех элементов не дают одинакового хэш-значения, и где размер хэша и размер таблицы минимальны.

Это в основном хэширование Зобриста - считайте, что "ход" - это добавление или удаление одного элемента комбинации.

EDIT

Причина использования хэш-таблицы в том, что производительность поиска O(n), где n - количество элементов в комбинации (при условии отсутствия коллизий). Вычисление лексикографических индексов в комбинациях значительно медленнее, IIRC.

Недостатком, очевидно, является предварительная работа по созданию таблицы.