How to use Factoradic system to get or unrank the K-th permutations WITH repeated items

Yesterday I spent the entire day trying to solve a problem that wants me to get the k-th permutation or unrank a permutation. I found the best way was factoradic numbers, after hours of Googling and reading dozens of pdfs\powerpoints I finally managed to make it work perfectly both with pencil and paper and by code.

Problem now is, when there are repeated items.

I tried everything, but couldn't get the thing to work the way it should.The factoradic always generates much bigger rank for a permutation, can't just let it "recognize" only non-repeated permutations.

Does anyone know a way to use the actoradic syst开发者_Go百科em to unrank a permutation with repeated items ? (eg: abaac) ? If anyone knows, please I would love a small example and intuitive explanation, that sure will benifit many others in the future.

Thanks a lot :)

PS: Here is my attempted C++ code that I wrote MYSELF.I know its not optmized at all, but just to show you what I got so far: This code will work correct if no repeated items, but will be wrong with repeated items (next_permutation is not usable of course when say, I want the 1 billionth 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;
}

In a permutation where all elements are unique, we can generate each element, in a recursive fashion. To rewrite your implementation a bit (in pseudo-code)

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

Here we know a priori how many elements are in the subcollection, namely (k-1)!.

In a permutation with repeated elements, the number of remaining elements is (k-1)!/((# of 1s)!(# of 2s)! ... (# of ks)!) and this changes based on what element we choose on each level. We need to apply the same idea, but instead of being able to calculate the index on the fly, we need to determine how many sub-permutations there are if we choose element X at each level of the recursion. We subtract that from the permutation number and recurse.

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

The full listing in 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));