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

Wenn man eine Menge von positiven ganzen Zahlen 0<=x_1 < x_2< ... < x_k , dann könnte man etwas verwenden, das man die gequetschte Ordnung nennt:

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

Das Schöne an der zerquetschten Reihenfolge ist, dass sie unabhängig vom größten Wert in der übergeordneten Menge funktioniert.

Die gequetschte Reihenfolge ist nicht die Reihenfolge, nach der Sie suchen, aber sie ist verwandt.

Die gequetschte Ordnung wird verwendet, um die lexikographische Ordnung in der Menge der k-Teilmengen von {1,...,n) zu erhalten, indem man

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

berechnen Sie

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

Berechnen Sie dann den Index der gequetschten Ordnung von (n-x_k,...,n-k_1)

Ziehen Sie dann den Index der gequetschten Ordnung von Choose(n,k) ab, um Ihr Ergebnis zu erhalten, das der lexikografische Index ist.

Wenn Sie relativ kleine Werte für n und k haben, können Sie alle Werte Choose(a,b) mit a im Cache speichern.

Siehe Anderson, Kombinatorik auf endlichen Mengen, S. 112-119

Answer 2

Es gibt noch eine andere Möglichkeit, dies alles zu tun. Man könnte alle möglichen Kombinationen erzeugen und sie in eine Binärdatei schreiben, in der jeder Kamm durch seinen Index, beginnend bei Null, dargestellt wird. Wenn Sie dann einen Index finden müssen und die Kombination gegeben ist, wenden Sie eine binäre Suche auf die Datei an. Hier ist die Funktion. Sie ist in VB.NET 2010 für mein Lotto-Programm geschrieben, es funktioniert mit dem israelischen Lotteriesystem, daher gibt es eine Bonuszahl (7.); ignorieren Sie sie einfach.

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. Es dauert 5 bis 10 Minuten, um 16 Millionen Kämme auf einem Core 2 Duo zu erzeugen. Das Auffinden des Index mit der binären Suche in der Datei dauert 397 Millisekunden auf einem SATA-Laufwerk.

Answer 3

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

Answer 4

EDIT: Vergessen Sie es. Das ist völlig falsch.

---

Ihre Kombination soll sein (a ₁ , a ₂ , ..., a _k-1 , a _k ), wobei a ₁ < a ₂ < ... < a _k . Wählen Sie(a,b) = a!/(b!*(a-b)!), wenn a >= b ist, und sonst 0. Dann ist der gesuchte Index

wählen(a _k -1, k) + choose(a _k-1 -1, k-1) + choose(a _k-2 -1, k-2) + ... + wählen Sie (a ₂ -1, 2) + wählen Sie (a ₁ -1, 1) + 1

Der erste Term zählt die Anzahl der k-Element-Kombinationen, bei denen das größte Element kleiner ist als a _k . Der zweite Term zählt die Anzahl der (k-1)-Elementkombinationen, bei denen das größte Element kleiner ist als a _k-1 . Und so weiter.

Beachten Sie, dass die Größe der Grundgesamtheit der auszuwählenden Elemente (10 in Ihrem Beispiel) bei der Berechnung des Indexes keine Rolle spielt. Können Sie sehen, warum?

Answer 5

Unter der Voraussetzung, dass die maximale setSize nicht zu groß ist, können Sie einfach eine Nachschlagetabelle erstellen, in der die Eingaben auf diese Weise kodiert sind:

  int index(a,b,c,...)
  {
      int key = 0;
      key |= 1<<a;
      key |= 1<<b;
      key |= 1<<c;
      //repeat for all arguments
      return Lookup[key];
  } 

Um die Nachschlagetabelle zu erstellen, sehen Sie sich dieser Algorithmus der "Banker's Order" . Erzeugen Sie alle Kombinationen und speichern Sie auch den Basisindex für jedes nElement. (Für das Beispiel auf S. 6 wäre dies [0,1,5,11,15]). Beachten Sie, dass Sie, wenn Sie die Antworten in der umgekehrten Reihenfolge wie im Beispiel (LSBs zuerst) speichern, nur eine Tabelle benötigen, die für die größtmögliche Menge ausgelegt ist.

Füllen Sie die Nachschlagetabelle auf, indem Sie die Kombinationen durchgehen, indem Sie Lookup[combination[i]]=i-baseIdx[nItems]