Delphi中不同的排列子集排名和排名

Question

问候Delphian堆垛机.

我搜索了网站,所有"排列等级和排名"相关的讨论,找不到符合我需求的那个.

在德尔福:

有一个数组:

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

如果想要迭代由3个元素组成的所有不同排列,可以估计结果列表将由24行组成,按字典顺序排列为:

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

可以使用"n选择k"公式计算列表的大小,其中"n"表示成员数,"k"表示选择数:

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

我想弄清楚的是如何,(没有搜索整个列表):

通过提供词典排名,假设为"13",可以"解开"并获得子集"203".

通过提供子集"203",可以获得字典等级"13".

任何帮助都感激不尽.

感谢您的时间.

Answer 1

这个组合对象在俄语和法语组合中具有表示"排列"的特殊名称A(n, k).很容易看出每个数字占据排列列表A(n-1, k-1)时间的第一位.所以我们可以找到给定等级的数字首先出现,反之亦然 - 有第一个数字,我们可以找到等级的间隔.然后继续下一个数字,从列表中删除使用过的数字.

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;

使用参数调用5, 3, 15返回安排1,2,0.对于反向任务排名可能被发现为

 (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