Diskrete Permutation Teilmenge Rang und Unrank in Delphi

Question

Grüße Delphian Stapler.

Ich habe durch die Website, alle "Permutation Rang & Unrank" verwandten Diskussionen durchsucht und konnte nicht die eine finden, die meine Bedürfnisse erfüllt.

In Delphi:

mit einer Anordnung von:

Members: array [0..3] of Byte = (0,1,2,3); 

Will man die durch alle verschiedene Permutationen von drei Elementen zusammengesetzt zu durchlaufen, kann man schätzen, dass der Ergebnisliste wird nach 24 Zeilen zusammengesetzt sein , lexikographisch geordnet als:

0 012 
1 013 
2 021 
3 023 
4 031 
5 032 
6 102 
7 103 
8 120 
9 123 
10 130 
11 132 
12 201 
13 203 
14 210 
15 213 
16 230 
17 231 
18 301 
19 302 
20 310 
21 312 
22 320 
23 321 

man die Größe der Liste durch die Verwendung einer „n wählen k“ Formel berechnen kann, wobei „n“ für die Anzahl der Mitglieder steht und „k“ für die Anzahl der Möglichkeiten:

p(n,k) = n!/(n-k)! 
p(4,3) = 4!/(4-3)! = (4 x 3 x 2 x 1)/(1 x 1) = 24 

Was ich versuche, ist, herauszufinden, wie man (ohne durch die gesamte Liste der Suche):

Durch den lexicographic Rang liefern, sagen wir, "13" kann man "entrank" und die Teilmenge "203" erhalten.

Durch die Bereitstellung der Teilmenge "203" kann man den lexikographischen Rang "13" erhalten.

Jede Hilfe wird sehr geschätzt.

Vielen Dank für Ihre Zeit.

Answer 1

Dieses kombinatorische Objekt hat einen speziellen Namen für "Anordnung" in der russischen und französischen Kombinatorik A(n, k). Es ist leicht zu sehen, dass jede Ziffer den ersten Platz der Arrangement-Liste A(n-1, k-1) mal belegt. So können wir herausfinden, welche Ziffer für einen gegebenen Rang zuerst gilt und umgekehrt - mit der ersten Ziffer können wir ein Rangintervall finden. Fahren Sie dann für die nächsten Ziffern fort und entfernen Sie die verwendeten Ziffern aus der Liste.

function ArrangementByRank(n, k, rank: Integer): string; 

    function NumArrNK(n, k: Integer): Int64; 
    var 
     i: Integer; 
    begin 
     Result := 1; 
     for i := 0 to k - 1 do 
     Result := Result * (n - i); 
    end; 

    var 
    Dig: array of Byte; 
    i, j, id, ank: Integer; 
    begin 
    Result := ''; 
    SetLength(Dig, n); 
    for i := 0 to n - 1 do 
     Dig[i] := i; //initial digit list 

    for i := 1 to k do begin 
     ank := NumArrNK(n - i, k - i); //might be optimized 
     id := rank div ank; 
     rank := rank mod ank; //prepare for the next round 
     Result := Result + IntToStr(Dig[id]); 
     for j := id to n - i - 1 do 
     Dig[j] := Dig[j + 1]; //squeeze digit list 
    end; 
    end; 

Aufruf mit Argumenten 5, 3, 151,2,0 Anordnung zurückgibt. Für Reverse Task Rang könnte als

(Index of 1 in initial list) * A(4,2) + (Index of 2 in squeezed list) * A(3,1) = 
1 * A(4,2) + 1 * A(3,1) = 
12 + 3 = 
15