如何使用 Factoradic 系统获取或取消具有重复项的 K 排列

Question

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

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

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

有谁知道如何使用行动系统对重复项目的排列进行取消排名？ （例如：abaac）？ 如果有人知道，请我喜欢一个小例子和直观的解释，这肯定会让将来的许多其他人受益。

非常感谢:)

PS：这是我自己编写的尝试的 C++ 代码。我知道它根本没有优化，但只是为了向您展示到目前为止我得到的结果： 如果没有重复的项目，此代码将正确工作，但如果重复的项目，则会出现错误（当然，当我想要第 10 亿个排列时，next_permutation 不可用）。

#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 中的完整列表

#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));