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

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

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

#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.

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

И т. Д.

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

Answer 2

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

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

Редактировать 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

Answer 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.

Answer 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

Answer 5

Мне нужно было то же самое для моего проекта, и самое быстрое решение, которое я нашел, было (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

Answer 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.

Answer 7

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

Должно быть довольно просто вычислить индекс постепенно.

Answer 8

Я использовал ответ пользователя user515430 и преобразовал его в python3. Также это поддерживает непостоянные значения, поэтому вы можете передать [1,3,5,7,9] в качестве пула вместо диапазона (1,11)

from itertools import combinations
from scipy.special import comb
from pandas import Index

debugcombinations = False

class IndexedCombination:
    def __init__(self, _setsize, _poolvalues):
        self.setsize = _setsize
        self.poolvals = Index(_poolvalues)
        self.poolsize = len(self.poolvals)
        self.totalcombinations = 1
        fast_k = min(self.setsize, self.poolsize - self.setsize)
        for i in range(1, fast_k + 1):
            self.totalcombinations = self.totalcombinations * (self.poolsize - fast_k + i) // i

        #fill the nCr cache
        self.choose_cache = {}
        n = self.poolsize
        k = self.setsize
        for i in range(k + 1):
            for j in range(n + 1):
                if n - j >= k - i:
                    self.choose_cache[n - j,k - i] = comb(n - j,k - i, exact=True)
        if debugcombinations:
            print('testnth = ' + str(self.testnth()))

    def get_nth_combination(self,index):
        n = self.poolsize
        r = self.setsize
        c = self.totalcombinations
        #if index < 0 or index >= c:
        #    raise IndexError
        result = []
        while r:
            c, n, r = c*r//n, n-1, r-1
            while index >= c:
                index -= c
                c, n = c*(n-r)//n, n-1
            result.append(self.poolvals[-1 - n])
        return tuple(result)

    def get_n_from_combination(self,someset):
        n = self.poolsize
        k = self.setsize
        index = 0
        j = 0
        for i in range(k):
            setidx = self.poolvals.get_loc(someset[i])
            for j in range(j + 1, setidx + 1):
                index += self.choose_cache[n - j, k - i - 1]
            j += 1
        return index

    #just used to test whether nth_combination from the internet actually works
    def testnth(self):
        n = 0
        _setsize = self.setsize
        mainset = self.poolvals
        for someset in combinations(mainset, _setsize):
            nthset = self.get_nth_combination(n)
            n2 = self.get_n_from_combination(nthset)
            if debugcombinations:
                print(str(n) + ': ' + str(someset) + ' vs ' + str(n2) + ': ' + str(nthset))
            if n != n2:
                return False
            for x in range(_setsize):
                if someset[x] != nthset[x]:
                    return False
            n += 1
        return True

setcombination = IndexedCombination(5, list(range(1,10+1)))
print( str(setcombination.get_n_from_combination([2,5,7,8,10])))

возвращает 188

Answer 9

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

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-размеров. Это комбинация, поэтому общее количество возможных предметов будет (n k) . Это подсказка, что мы могли бы найти решение в Треугольник Паскаля . Через некоторое время, сравнивая написанные вручную примеры с соответствующими числами из треугольника Паскаля, мы найдем схему и, следовательно, алгоритм.

Answer 10

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

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

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

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

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

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

compute

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

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

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

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

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