Delphi 中的不同排列子集秩和非秩

Question

你好Delphi堆垛机。

我搜索了整个站点，所有 "permutation rank & unrank" 相关讨论，但找不到满足我需要的那个。

在Delphi中：

有一个数组：

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

如果要遍历由 3 个元素组成的所有不同排列，可以估计结果列表将由 24 行组成，按字典顺序排列为：

可以使用"n choose 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”，可以"unrank"并获得子集“203”。

通过提供子集“203”，可以获得词典排名“13”。

任何帮助将不胜感激。

感谢您的宝贵时间。

Answer 1

此组合对象在俄语和法语组合学 A(n, k) 中具有特殊名称，表示 "arrangement"。不难看出，每个数字都占据排列表首位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 returns 安排 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

Delphi 中的不同排列子集秩和非秩

Distinct permutation subset rank and unrank in Delphi

delphi

permutation

subset

distinct

rank