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

Ответ 1

Вот концептуальный ответ и код, основанный на том, как работает порядок lex. (Так что, я думаю, мой ответ подобен тому, как "придурок", за исключением того, что я думаю, что у него слишком мало деталей, а его ссылок слишком много.) Я написал для вас функцию 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

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

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

Ответ 2

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

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

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

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

So (0,1,2) < (0,1,3) (0,1,4) и т.д.

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

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

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

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

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

Ответ 3

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

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

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

ИЗМЕНИТЬ

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

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

Ответ 4

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

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.

Ответ 5

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

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

Ответ 6

То, что вы хотите, называется 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

Ответ 7

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

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

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

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

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

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

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

Чтобы прочитать об этом классе и загрузить код, см. Tablizing the Binomial Coeffieicent.

Нельзя преобразовать этот класс в С++.