algorithm - 如何使用 Factoradic 系统获取或取消排名 K-th 排列与重复项目

Question

昨天我花了一整天的时间试图解决一个问题，该问题需要我获得第 k 个排列或取消排序排列。 我发现最好的方法是因式数，经过数小时的谷歌搜索和阅读数十个 pdfs\powerpoints，我终于成功地用铅笔和纸以及代码使它完美地工作。

现在的问题是，当有重复项时。

我尝试了所有方法，但无法让它按应有的方式工作。因子总是为排列生成更大的排名，不能让它只“识别”非重复排列。

有谁知道如何使用 actoradic 系统对具有重复项的排列进行排序？ (例如:abaac)？ 如果有人知道，请给我一个小例子和直观的解释，这肯定会在未来造福很多其他人。

非常感谢:)

PS:这是我自己编写的尝试的 C++ 代码。我知道它根本没有优化，但只是为了向您展示我到目前为止得到的结果: 如果没有重复的项目，此代码将正确运行，但对于重复的项目将是错误的(next_permutation 当然不可用，当我想要第 1 十亿次排列时)。

#include <iostream>
#include <cstdio>
#include <string>
#include <algorithm>

using namespace std;

int f(int n) {
    if(n<2) return 1;
    return n*f(n-1);
}

int pos(string& s,char& c) {
    for(int i=0;i<s.size();++i) {
        if(s[i]==c) return i;
    }
    return -1;
}

int main() {
    const char* perm    =    "bedac";
    string original=perm;
    sort(original.begin(),original.end());
    string s=original;
    string t=perm;
    int res=0;
    for(;s!=t && next_permutation(s.begin(),s.end());++res);
    cout<<"real:"<<res<<endl;
    s=original;
    string n;
    while(!s.empty()) {
        int p=pos(s,t[0]);
        n+=p;
        t.erase(0,1);
        s.erase(p,1);
    }
    for(res=0;!n.empty();(res+=n[0]*f(n.size()-1)),n.erase(0,1));
    cout<<"factoradix:"<<res<<endl;
    return 0;
}

Answer 1

在所有元素都是唯一的排列中，我们可以以递归方式生成每个元素。稍微重写你的实现(用伪代码)

def map(k,left):
   ele = k/(len(left)!)
   return [ele] + map( k % (len(left)!), left - left[ele])

这里我们先验知道子集合中有多少个元素，即(k-1)!。

在具有重复元素的排列中，剩余元素的数量是 (k-1)!/((# of 1s)!(# of 2s)! ... (# of ks)!) 这会根据我们在每个级别上选择的元素而变化。我们需要应用相同的想法，但不是能够即时计算索引，而是需要确定如果我们在递归的每个级别选择元素 X 时有多少子排列。我们从排列数中减去它并递归。

# group_v is the value of an element 
# group_members is the number of times it is repeated
# facts_with is group_members[x] factorial
def permap(k,group_v,group_members,facts_with):

    n = sum(group_members);  # how many elements left
    if n == 0:
        return []

    total = math.factorial(n-1);
    total_denom = prod(facts_with);


    start_range = 0; end_range = 0; 
    for group_i in range(len(group_v)):
        if group_members[group_i] == 0:
            continue
        v = (group_members[group_i]*total)/(total_denom) # n-1!/((a-1)!...z!)                                          

        end_range += v
        if end_range > k:
            facts_with[group_i]/=group_members[group_i];
            group_members[group_i]-=1;
            return [group_v[group_i]] + permap(k-start_range,group_v,group_members,facts_with)
        else:
            start_range=end_range

    raise Exception()

Python 中的完整 list

#imports                          



import itertools;
import math;
import operator
def prod(lst):
    return reduce(operator.mul,lst);

#mainfunc                                                                                                          
def permap(k,group_v,group_members,facts_with):

    n = sum(group_members);
    if n == 0:
        return []

    total = math.factorial(n-1);
    total_denom = prod(facts_with);

    start_range = 0; end_range = 0;
    for group_i in range(len(group_v)):
        if group_members[group_i] == 0:
            continue
        v = (group_members[group_i]*total)/(total_denom) # n-1!/(a!...z!)                                          

        end_range += v
        if end_range > k:
            facts_with[group_i]/=group_members[group_i];
            group_members[group_i]-=1;
            return [group_v[group_i]] + permap(k-start_range,group_v,group_members,facts_with)
        else:
            start_range=end_range

    raise Exception()

items = [1,2,2,1]
n_groups = len(list(itertools.groupby(items)))
facts_with = [0]*(n_groups)
group_v = [0]*(n_groups)
group_members = [0]*(n_groups)

group_i = 0
print [list(g) for k,g in itertools.groupby(items)];
for group in itertools.groupby(items):
    group_v[group_i], group_members[group_i] = group;
    group_members[group_i] = len(list(group_members[group_i]))
    facts_with[group_i] = math.factorial(group_members[group_i]);
    group_i+=1

for x in range(6):
    print permap(x,list(group_v),list(group_members),list(facts_with));