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

Hier ist ein Schnipsel, der die Arbeit erledigen wird.

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

Es wird angenommen, dass Sie eine Funktion haben

int c(int n, int k);

die die Anzahl der Kombinationen der Auswahl von k Elementen aus n Elementen zurückgibt. Die Schleife berechnet die Anzahl der Kombinationen, die der angegebenen Kombination vorausgehen. Durch Hinzufügen von eins am Ende erhalten wir den aktuellen Index.

Für die gegebene Kombination gibt es c(9, 4) = 126 Kombinationen, die 1 enthalten und ihr somit in lexikografischer Reihenfolge vorausgehen.

Zu den Kombinationen, die 2 als kleinste Zahl enthalten, gehören

c(7, 3) = 35 Kombinationen mit 3 als zweitkleinster Zahl

c(6, 3) = 20 Kombinationen mit 4 als zweitkleinster Zahl

Sie alle stehen vor der angegebenen Kombination.

Von den Kombinationen, die 2 und 5 als die beiden kleinsten Zahlen enthalten, gibt es

c(4, 2) = 6 Kombinationen mit 6 als drittkleinster Zahl.

Sie alle stehen vor der angegebenen Kombination.

Etc.

Wenn Sie eine Druckanweisung in die innere Schleife einfügen, erhalten Sie die Zahlen 126, 35, 20, 6, 1. Ich hoffe, das erklärt den Code.

Answer 2

Konvertieren Sie Ihre Zahlenauswahl in eine faktorielle Basiszahl . Diese Zahl ist dann der gewünschte Index. Technisch gesehen wird damit der lexikografische Index aller Permutationen berechnet, aber wenn Sie nur Kombinationen angeben, werden die Indizes immer noch gut geordnet sein, nur mit einigen großen Lücken für alle Permutationen, die zwischen den einzelnen Kombinationen liegen.

Edit: Pseudocode entfernt, er war falsch, aber die obige Methode sollte funktionieren. Zu müde, um mit korrekten Pseudocode im Moment zu kommen.

Edit 2: Hier ist ein Beispiel. Nehmen wir an, wir würden eine Kombination von 5 Elementen aus einer Menge von 10 Elementen auswählen, wie in Ihrem Beispiel oben. Wenn die Kombination wäre 2 3 4 6 8 erhält man die zugehörige faktorielle Basiszahl wie folgt:

Nehmen Sie die nicht ausgewählten Elemente und zählen Sie, an wie vielen Sie vorbeikommen müssen, um zu dem auszuwählenden Element zu gelangen.

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

Der Index in faktorieller Basis ist also 1112300000

In Dezimalbasis ist es

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

Answer 3

Dies ist Algorithmus 2.7 kSubsetLexRank auf Seite 44 von Kombinatorische Algorithmen von Kreher und Stinson.

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

Das Feld t enthält Ihre Werte, zum Beispiel [5 7 8 9 10]. Die Funktion choose(n, k) berechnet die Zahl "n choose k". Der Ergebniswert r ist der Index, in diesem Beispiel 251. Weitere Eingaben sind n und k, im Beispiel wären das 10 und 5.

Answer 4

Null-Basis,

# 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

Ich brauchte auch das gleiche für ein Projekt von mir und die schnellste Lösung, die ich fand, war (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

Meine Eingabe "comb" enthielt Elemente in aufsteigender Reihenfolge Sie können den Code zum Beispiel mit testen:

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

Es ist nicht schwer zu beweisen, dass wenn comb=(a1,a2,a3...,ak) (in aufsteigender Reihenfolge) dann:

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