Вычислить перестановку из представления факториала K-й итерации n-го перестановки


В продолжение поста я сделал по математике стека обмен я написал простую программу, которая вычисляет K-ую перестановку от 0 до N-1, где число перестановок N!. Что мне стало это интересно, я мог бы получить некоторые указатели на том, как улучшить и переписать функцию перестановки, чтобы быть более эффективным, например, возможно, избавившись от вектор и цикл for для вычисления факториала.

#include <iostream>
#include <vector>
#include <cmath>
using namespace std;

///<summary>Calculates the permutation of K in range of 0 to N!. (MAX of N = 20--2^61).</summary>
vector<size_t> factorial_permutation(size_t N, uint64_t K) {
    vector<size_t> Perm;

    uint64_t FactN = N,  //Factorial of N
        RmdrK = K, //Remainder of K/(N-1)!
        IterN = N, //Downward iterator for N
        PostK; //The factorial position of K for each sub permutation.

    for(uint64_t I = N-1; I > 1; I--)
        FactN *= I;
    for (uint64_t I = 1; I <= N; I++) {
        FactN /= IterN--;
        PostK = RmdrK / FactN;
        RmdrK = RmdrK - (PostK * FactN);
        Perm.push_back(PostK);
    }

    return Perm;
}

int main() {
    size_t N = 0;
    uint64_t K = 0;
    vector<size_t> c = factorial_permutation(N, K);
    vector<size_t> s; //The factorial permutation sequence
    vector<size_t> e; //The permutation built from the factorial sequence

    //Builds the basic order sequence 0 to N-1 before permutation.
    for(int i = 0; i < N; i++)
        s.push_back(i);

    //Pushes the final result converted from factorial permutation to real permutation. For each entry of sequence s[c[i]] is an index into e[i] to build the permutation.
    for (int i = 0; i < N; i++) {
        e.push_back(s[c[i]]);
        s.erase(s.begin() + c[i]);
    }

    // Outputs the final permutation.
    for (int i = 0; i < N; i++)
        cout << e[i];

    cin.get();
};

Функция factorial_permutation вычисляет факториал представлением K--K-й итерации--в последовательности от 0 to (N-1)! возможных перестановок. В main() функция делает простым переход от факторного представительство в построении фактической последовательности. Я хотел бы объединить два и посмотреть, если я могу свести вектора всех вместе ради производительности.

Я также знаю, что я могу удалить вектор в factorial_permutation С помощью основного массива, но я не могу показаться, чтобы свести на нет в main() функция.



225
4
задан 27 февраля 2018 в 12:02 Источник Поделиться
Комментарии
1 ответ


  • Цикл

    for(int i = 0; i < N; i++)
    s.push_back(i);

    это идиоматически выражаться как std::iota(s.begin(), s.end(), 0) (вам нужно #include <numeric>).


  • А не голые петли принцип требует дать имя

        for (int i = 0; i < N; i++) {
    e.push_back(s[c[i]]);
    s.erase(s.begin() + c[i]);
    }

    петли. Она, безусловно, представляет собой важный алгоритм. Что именно он делает?

    В любом случае s и e векторы не будут показаны клиенту.


  • Вычисления факториалов ограничивает полезность кода N < 21 (21! = 0x2_c507_7d36_b8c4_0000 не помещается в 64 бита). К сожалению, вы не можете даже выразить K в uint64_t лимиты для больших N. Рассмотрим BigInteger.

  • Это позволило избежать факториалов (а также вспомогательных векторов), работая наоборот. Рассмотрим псевдокод:

        while N > 0:
    index = K % N
    swap a[N-1] with a[index]
    K /= N
    N -= 1

    Хотя правильно, не плодить одинаковые K'ой перестановки, как ваш код делает. Может я предлагаю изменить его, чтобы производить правильную последовательность в качестве упражнения?


ПС: обязательное предупреждение о использование имен std

4
ответ дан 27 февраля 2018 в 04:02 Источник Поделиться