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

Ответ 1

Вот фрагмент, который будет выполнять работу.

#include <iostream>

int main()
{
    const int n = 10;
    const int k = 5;

    int combination[k] = {2, 5, 7, 8, 10};

    int index = 0;
    int j = 0;
    for (int i = 0; i != k; ++i)
    {
        for (++j; j != combination[i]; ++j)
        {
            index += c(n - j, k - i - 1);
        }
    }

    std::cout << index + 1 << std::endl;

    return 0;
}

Предполагается, что у вас есть функция

int c(int n, int k);

который вернет количество комбинаций выбора k элементов из n элементов. Цикл вычисляет количество комбинаций, предшествующих данной комбинации. Добавляя один в конец, мы получаем фактический индекс.

Для данной комбинации есть c (9, 4) = 126 комбинаций, содержащих 1 и, следовательно, предшествующих ему в лексикографическом порядке.

Из комбинаций, содержащих 2 как наименьшее число, есть

c (7, 3) = 35 комбинаций, имеющих 3 как второе наименьшее число

c (6, 3) = 20 комбинаций, имеющих 4 в качестве второго наименьшего числа

Все они предшествуют данной комбинации.

Из комбинаций, содержащих 2 и 5 в качестве двух наименьших чисел, есть

c (4, 2) = 6 комбинаций, имеющих 6 в качестве третьего наименьшего числа.

Все они предшествуют данной комбинации.

Etc.

Если вы поместите оператор печати во внутренний цикл, вы получите цифры 126, 35, 20, 6, 1. Надеюсь, что это объясняет код.

Ответ 2

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

Изменить: pseudocode удален, это было неправильно, но метод выше должен работать. Слишком устал, чтобы придумать правильный псевдокод на данный момент.

Изменить 2: Вот пример. Скажем, мы выбрали комбинацию из 5 элементов из набора из 10 элементов, как в вашем примере выше. Если комбинация была 2 3 4 6 8, вы получили бы соответствующий факториальный базовый номер следующим образом:

Возьмите невыбранные элементы и подсчитайте, сколько вы должны пройти, чтобы перейти к тем, который вы выбираете.

1 2 3 4 5 6 7 8 9 10
2 -> 1
1 3 4 5 6 7 8 9 10
3 -> 1
1 4 5 6 7 8 9 10
4 -> 1
1 5 6 7 8 9 10
6 -> 2
1 5 7 8 9 10
8 -> 3

Таким образом, индекс в факториальной базе 1112300000

В десятичной базе это

1*9! + 1*8! + 1*7! + 2*6! + 3*5! = 410040

Ответ 3

Это алгоритм 2.7 kSubsetLexRank на стр. 44 комбинаторных алгоритмов Кришера и Стинсона.

r = 0
t[0] = 0
for i from 1 to k
    if t[i - 1] + 1 <= t[i] - 1
        for j from t[i - 1] to t[i] - 1
            r = r + choose(n - j, k - i)
return r

В массиве t хранятся ваши значения, например [5 7 8 9 10]. Функция select (n, k) вычисляет число "n выбирает k". Значение результата r будет индексом 251 для примера. Другими входами являются n и k, для примера они будут 10 и 5.

Ответ 4

нулевой базы,

# v: array of length k consisting of numbers between 0 and n-1 (ascending)
def index_of_combination(n,k,v):
    idx = 0
    for p in range(k-1):
        if p == 0: arrg = range(1,v[p]+1)
        else: arrg = range(v[p-1]+2, v[p]+1)
        for a in arrg:
            idx += combi[n-a, k-1-p]
    idx += v[k-1] - v[k-2] - 1
    return idx

Ответ 5

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

Теперь значение каждой цифры в факториал-базовом номере - это количество элементов, которые меньше, чем они еще не использовались. Итак, для комбинации (10, 5):

(1 2 3 4 5) == 0*9!/5! + 0*8!/5! + 0*7!/5! + 0*6!/5! + 0*5!/5!
            == 0*3024 + 0*336 + 0*42 + 0*6 + 0*1
            == 0

(10 9 8 7 6) == 9*3024 + 8*336 + 7*42 + 6*6 + 5*1
             == 30239

Достаточно легко вычислить индекс пошагово.

Ответ 6

Есть еще один способ сделать все это. Вы можете создать все возможные комбинации и записать их в двоичный файл, где каждый гребень представлен индексом, начинающимся с нуля. Затем, когда вам нужно найти индекс и указать комбинацию, вы применяете двоичный поиск в файле. Здесь функция. Он написан на VB.NET 2010 для моей лотерейной программы, он работает с израильской лотерейной системой, поэтому есть бонусный (7-й) номер; просто игнорируйте его.

Public Function Comb2Index( _
ByVal gAr() As Byte) As UInt32
 Dim mxPntr As UInt32 = WHL.AMT.WHL_SYS_00     '(16.273.488)
 Dim mdPntr As UInt32 = mxPntr \ 2
 Dim eqCntr As Byte
 Dim rdAr() As Byte

    modBinary.OpenFile(WHL.WHL_SYS_00, _
    FileMode.Open, FileAccess.Read)

    Do
    modBinary.ReadBlock(mdPntr, rdAr)
RP: If eqCntr = 7 Then GoTo EX

        If gAr(eqCntr) = rdAr(eqCntr) Then
           eqCntr += 1
           GoTo RP

        ElseIf gAr(eqCntr) < rdAr(eqCntr) Then
            If eqCntr > 0 Then eqCntr = 0
               mxPntr = mdPntr
               mdPntr \= 2

        ElseIf gAr(eqCntr) > rdAr(eqCntr) Then
            If eqCntr > 0 Then eqCntr = 0
            mdPntr += (mxPntr - mdPntr) \ 2
        End If

    Loop Until eqCntr = 7

EX: modBinary.CloseFile()
    Return mdPntr

End Function

P.S. Для создания 16 миллионов гребней на Core 2 Duo требуется 5-10 минут. Для поиска индекса с использованием двоичного поиска в файле требуется 397 миллисекунд на диске SATA.

Ответ 7

Мне тоже было нужно то же самое для моего проекта, и самое быстрое решение, которое я нашел, было (Python):

import math

def nCr(n,r):
    f = math.factorial
    return f(n) / f(r) / f(n-r)

def index(comb,n,k):
    r=nCr(n,k)
    for i in range(k):
        if n-comb[i]<k-i:continue
        r=r-nCr(n-comb[i],k-i)
    return r

Мой ввод "гребенка" содержит элементы в порядке возрастания. Вы можете протестировать код, например:

import itertools
k=3
t=[1,2,3,4,5]
for x in itertools.combinations(t, k):
    print x,index(x,len(t),k)

Нетрудно доказать, что если comb = (a1, a2, a3..., ak) (в порядке возрастания), то:

index = [nCk- (n-a1 + 1) Ck] + [(n-a1) C (k-1) - (n-a2 + 1) C (k-1)] +... =   nCk - (n-a1) Ck - (n-a2) C (k-1) -.... - (n-ak) C1

Ответ 8

ИЗМЕНИТЬ: Ничего. Это совершенно неправильно.

Пусть ваша комбинация будет (a ₁, a ₂,..., a _k-1, a _k), где a ₁ a ₂... < а <суб > ксуб > . Выберем (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-элементов, так что наибольший элемент меньше, чем a _k. Второй член подсчитывает количество (k-1) -элементных комбинаций, так что наибольший элемент меньше, чем _k-1. И так далее.

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

Ответ 9

Предполагая, что максимальный 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];
  } 

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

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

Ответ 10

Если у вас есть набор положительных целых чисел 0 <= x_1 < x_2 <... < x_k, тогда вы можете использовать что-то, называемое сжатым порядком:

I = sum(j=1..k) Choose(x_j,j)

Красота сжатого порядка заключается в том, что он работает независимо от наибольшего значения в родительском наборе.

Сжатый порядок - это не тот порядок, который вы ищете, но он связан.

Чтобы использовать сжатый порядок для получения лексикографического порядка в множестве k-подмножеств {1,..., n), выбирая

1 <= x1 < ... < x_k <=n

вычислить

 0 <= n-x_k < n-x_(k-1) ... < n-x_1

Затем вычислите сжатый индекс порядка (n-x_k,..., n-k_1)

Затем вычтите сжатый индекс заказа из Select (n, k), чтобы получить результат, который является лексикографическим индексом.

Если у вас относительно небольшие значения n и k, вы можете кэшировать все значения. Выберите (a, b) с помощью

См. Андерсон, Комбинаторика на конечных наборах, стр. 112-119

Ответ 11

Пример решения:

class Program
{
    static void Main(string[] args)
    {
        // The input
        var n = 5;
        var t = new[] { 2, 4, 5 };

        // Helping transformations
        ComputeDistances(t);
        CorrectDistances(t);

        // The algorithm
        var r = CalculateRank(t, n);

        Console.WriteLine("n = 5");
        Console.WriteLine("t = {2, 4, 5}");
        Console.WriteLine("r = {0}", r);

        Console.ReadKey();
    }

    static void ComputeDistances(int[] t)
    {
        var k = t.Length;
        while (--k >= 0)
            t[k] -= (k + 1);
    }

    static void CorrectDistances(int[] t)
    {
        var k = t.Length;
        while (--k > 0)
            t[k] -= t[k - 1];
    }

    static int CalculateRank(int[] t, int n)
    {
        int k = t.Length - 1, r = 0;

        for (var i = 0; i < t.Length; i++)
        {
            if (t[i] == 0)
            {
                n--;
                k--;
                continue;
            }

            for (var j = 0; j < t[i]; j++)
            {
                n--;
                r += CalculateBinomialCoefficient(n, k);
            }

            n--;
            k--;
        }

        return r;
    }

    static int CalculateBinomialCoefficient(int n, int k)
    {
        int i, l = 1, m, x, y;

        if (n - k < k)
        {
            x = k;
            y = n - k;
        }
        else
        {
            x = n - k;
            y = k;
        }

        for (i = x + 1; i <= n; i++)
            l *= i;

        m = CalculateFactorial(y);

        return l/m;
    }

    static int CalculateFactorial(int n)
    {
        int i, w = 1;

        for (i = 1; i <= n; i++)
            w *= i;

        return w;
    }
}

Идея за кулисами - связать k-подмножество с операцией рисования k-элементов из набора n-size. Это комбинация, поэтому общее количество возможных элементов будет (n k). Это ключ к поиску решения в Pascal Triangle. Через некоторое время сравнивая вручную написанные примеры с соответствующими номерами из треугольника Паскаля, мы найдем шаблон и, следовательно, алгоритм.