Как использовать Факторическую систему для получения или отмены K-й перестановки С повторяющимися элементами - PullRequest
Новая
       7

Как использовать Факторическую систему для получения или отмены K-й перестановки С повторяющимися элементами

4 голосов
/ 10 июня 2011

Вчера я провел весь день, пытаясь решить проблему, которая требует, чтобы я получил k-ю перестановку или отменил перестановку. Я обнаружил, что лучшим способом были факторные цифры, после нескольких часов поиска в Google и чтения десятков PDF-файлов \ powerpoints мне наконец-то удалось заставить его работать идеально как карандашом, бумагой, так и кодом.

Проблема теперь в том, что есть повторяющиеся предметы.

Я попробовал все, но не смог заставить вещь работать так, как она должна работать. Факторика всегда генерирует гораздо больший ранг для перестановки, не может просто позволить ей «распознавать» только неповторяющиеся перестановки.

Кто-нибудь знает способ использования акторадической системы, чтобы отменить перестановку с повторяющимися предметами? (например: 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;
}

1 Ответ

2 голосов
/ 11 июня 2011

В перестановке, где все элементы уникальны, мы можем сгенерировать каждый элемент рекурсивным способом. Немного переписать вашу реализацию (в псевдокоде) 

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