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

Question

Я хочу предварительно вычислить некоторые значения для каждой комбинации в наборе комбинаций. Например, при выборе 3 чисел от 0 до 12 я вычислю некоторое значение для каждого из них:

>>> for n in choose(range(13), 3):
    print n, foo(n)

(0, 1, 2) 78
(0, 1, 3) 4
(0, 1, 4) 64
(0, 1, 5) 33
(0, 1, 6) 20
(0, 1, 7) 64
(0, 1, 8) 13
(0, 1, 9) 24
(0, 1, 10) 85
(0, 1, 11) 13
etc...

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

>>> a = [78, 4, 64, 33]
>>> a[magic((0,1,2))]
78

Что бы magic было?

Изначально я думал просто сохранить ее в виде 3-мерной матрицы размером 13 x 13 x 13, так что я могу легко индексировать ее таким образом. В то время как это 13 хорошо для выбора 3, это будет иметь слишком много накладных расходов для чего-то вроде 13 выбора 7.

Я не хочу использовать dict, потому что в конечном итоге этот код будет на C, и массив все равно будет намного эффективнее.

ОБНОВЛЕНИЕ: у меня тоже есть похожая проблема, но я использую комбинации с повторениями, поэтому любые ответы о том, как получить их, будут высоко оценены =).

ОБНОВЛЕНИЕ: Чтобы было ясно, я пытаюсь сэкономить место. Каждая из этих комбинаций фактически превращается во что-то, занимающее много места, скажем, 2 килобайта. Если бы я использовал массив 13x13x13, это было бы 4 мегабайта, из которых мне нужно только 572 килобайта с использованием (13 выбирают 3) точек.

Answer 1

Вот концептуальный ответ и код, основанный на том, как работает lex ordering.(Так что я думаю, что мой ответ похож на ответ «придурка», за исключением того, что я думаю, что у него слишком мало деталей, а в его ссылках слишком много.) Я написал для вас функцию unchoose(n,S), которая работает, предполагая, что S - упорядоченный списокподмножество range(n).Идея: либо S содержит 0, либо его нет.Если это так, удалите 0 и вычислите индекс для оставшегося подмножества.Если это не так, то он идет после подмножеств binomial(n-1,k-1), которые содержат 0.

def binomial(n,k):
    if n < 0 or k < 0 or k > n: return 0
    b = 1
    for i in xrange(k): b = b*(n-i)/(i+1)
    return b

def unchoose(n,S):
    k = len(S)
    if k == 0 or k == n: return 0
    j = S[0]
    if k == 1: return j
    S = [x-1 for x in S]
    if not j: return unchoose(n-1,S[1:])
    return binomial(n-1,k-1)+unchoose(n-1,S)

def choose(X,k):
    n = len(X)
    if k < 0 or k > n: return []
    if not k: return [[]]
    if k == n: return [X]
    return [X[:1] + S for S in choose(X[1:],k-1)] + choose(X[1:],k)

(n,k) = (13,3)
for S in choose(range(n),k): print unchoose(n,S),S

Теперь также верно, что вы можете кэшировать или хэшировать значения обеих функций, биномиальных и невыбранных.И что хорошо в этом, так это то, что вы можете сделать компромисс между предварительным вычислением всего и предварительным вычислением ничего.Например, вы можете предварительно вычислять только для len(S) <= 3.

. Вы также можете оптимизировать unchoose так, чтобы он добавлял биномиальные коэффициенты с циклом, если S[0] > 0, вместо уменьшения и использования хвостовой рекурсии.

Answer 2

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

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

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

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

То есть (0,1,2) <(0,1,3) <(0,1,4) и т. Д. </p>

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

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

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

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

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

Answer 3

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

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

Это в основном Хеширование Zobrist - думать о "движении" как о добавлении или удалении одного элементакомбинации.

РЕДАКТИРОВАТЬ

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

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

Answer 4

Я написал класс для работы с общими функциями для работы с биномиальным коэффициентом, к которому относится ваша проблема. Он выполняет следующие задачи:

1. Выводит все K-индексы в хорошем формате для любого N, выбирающего K, в файл. K-индексы могут быть заменены более описательными строками или буквами. Этот метод делает решение проблемы такого типа довольно тривиальным.

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

3. Преобразует индекс в отсортированной таблице биномиальных коэффициентов в соответствующие K-индексы.

4. Использует Mark Dominus метод для вычисления биномиального коэффициента, который с гораздо меньшей вероятностью переполняется и работает с большими числами.

5. Класс написан на .NET C # и предоставляет способ управления объектами, связанными с проблемой (если таковые имеются), используя общий список. Конструктор этого класса принимает значение bool, называемое InitTable, которое при значении true создаст общий список для хранения управляемых объектов. Если это значение равно false, таблица не будет создана. Таблицу не нужно создавать для выполнения 4 вышеуказанных методов. Методы доступа предоставляются для доступа к таблице.

6. Существует связанный тестовый класс, который показывает, как использовать класс и его методы. Он был тщательно протестирован с 2 случаями, и никаких известных ошибок нет.

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

Нетрудно преобразовать этот класс в C ++.

Answer 5

То, что вы хотите, называется combinadics . Вот моя реализация этой концепции в 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

Answer 6

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

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

Answer 7

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

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.