计算子集排序的范围和破坏

Question

对于某个自然数 n，我们拥有集合 {1, 2, ..., n} 的所有子集。我们定义这些子集的顺序如下：

• 空集的等级为 0。
• 以下是所有最小元素为 1 的集合。这些集合首先按基数排序，基数相同的集合再按字典顺序排序。
• 以下是所有最小元素为 2 的集合。这些集合首先按基数排序，基数相同的集合再按字典顺序排序。
• ...
• 以下是所有最小元素为n-1的集合。这些首先按基数排序，然后相同基数的集合按字典顺序排序。
• 以下是所有最小元素为n的集合。因此，最后一个位置是集合 {n}。

示例：n=4 子集排序：∅, {1}, {1, 2}, {1, 3}, {1, 4}, {1, 2, 3}, {1, 2, 4 }, {1, 3, 4}, {1, 2, 3, 4}, {2}, {2, 3}, {2, 4}, {2, 3, 4}, {3}, {3 , 4}, {4}

任务：

1. 编写一个 rang 方法，根据上述排序返回给定子集的排名。您可以使用函数 kSubsetLexRang(subset, k, n)，它返回按字典顺序包含 n 个元素的集合的 k 子集的排名。

2. 编写一个 derang 方法，给定整数 r 和 n，返回集合 {1, 2, ..., n} 的子集，其根据上述排序的排名为 r。您可以使用函数 kSubsetLexDerang(r, k, n)，它返回按字典顺序包含 n 个元素的集合的 k 子集的排列。

我找不到n元组的k子集的字典顺序和这个顺序之间的任何联系。任何想法？与 derang 类似，我不知道如何构造相应的集合。

import math

def kSubsetLexRang(T, k, n):
    r = 0
    for i in range(1, k + 1):
        if i == 1:
            a = 1
        else:
            a = T[i - 2] + 1
        for j in range(a, T[i - 1]):
            r += math.comb(n - j, k - i)
    return r

和

def kSubsetLexDerang(r,k,n):
    x=1
    T=[0]*k
    for i in range(1,k+1):
        while math.comb(n-x,k-i)<=r:
            r-=math.comb(n-x,k-i)
            x+=1
        T[i-1]=x
        x+=1
    return T

Answer 1

这里是 derang（更容易测试）：

def derang(r, n):

    # Special case: no element
    if r == 0:
        return []
    r -= 1

    # Determine the smallest element
    smallest = 1
    while r >= 2**(n-1):
        r -= 2**(n-1)
        n -= 1
        smallest += 1

    # Determine k
    k = 0
    while r >= math.comb(n-1, k):
        r -= math.comb(n-1, k)
        k += 1

    # Build the set
    return [smallest] + [smallest + x for x in kSubsetLexDerang(r, k, n)]

测试：

n = 4
for r in range(2**n):
    print(derang(r, n))

输出：在线尝试！

[]
[1]
[1, 2]
[1, 3]
[1, 4]
[1, 2, 3]
[1, 2, 4]
[1, 2, 5]
[1, 2, 3, 4]
[2]
[2, 3]
[2, 4]
[2, 3, 4]
[3]
[3, 4]
[4]