Wie berechnet man den Index (lexikografische Reihenfolge), wenn die Kombination gegeben ist?

Question

Ich weiß, dass es einen Algorithmus gibt, der es ermöglicht, bei einer Zahlenkombination (keine Wiederholungen, keine Reihenfolge) den Index der lexikografischen Reihenfolge zu berechnen.
Es wäre sehr nützlich für meine Anwendung, um die Dinge zu beschleunigen...

Zum Beispiel:

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  

Ich möchte, dass der Algorithmus den Index der angegebenen Kombination zurückgibt.
es: index( 2, 5, 7, 8, 10 ) --> Index

EDIT: Eigentlich verwende ich eine Java-Anwendung, die alle Kombinationen C(53, 5) generiert und sie in eine TreeMap einfügt. Meine Idee ist es, ein Array zu erstellen, das alle Kombinationen (und zugehörige Daten) enthält, die ich mit diesem Algorithmus indizieren kann.
Alles dient dazu, die Kombinationssuche zu beschleunigen. Allerdings habe ich versucht, einige (nicht alle) Ihrer Lösungen und die Algorithmen, die Sie vorgeschlagen sind langsamer als ein get() von TreeMap.
Falls es hilft: Ich brauche eine Kombination von 5 aus 53, beginnend von 0 bis 52.

Nochmals vielen Dank an alle :-)

Answer 1

Beispiellösung:

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;
    }
}

Die Idee hinter den Kulissen ist, eine k-Teilmenge mit einer Operation zu verbinden, bei der k-Elemente aus der n-großen Menge gezogen werden. Es handelt sich um eine Kombination, so dass die Gesamtzahl der möglichen Elemente wie folgt lautet (n k) . Es ist ein Hinweis darauf, dass wir die Lösung in den folgenden Bereichen suchen könnten Pascalsches Dreieck . Nach einer Weile des Vergleichs von manuell geschriebenen Beispielen mit den entsprechenden Zahlen aus dem Pascalschen Dreieck werden wir das Muster und damit den Algorithmus finden.

Answer 2

Ich habe die Antwort von user515430 verwendet und in Python3 konvertiert. Auch dies unterstützt nicht-kontinuierliche Werte, so dass Sie in [1,3,5,7,9] als Ihr Pool anstelle von range(1,11) übergeben könnte

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])))

kehrt zurück 188