4
\$\begingroup\$

As a follow of a post I made on the Mathematics Stack Exchange I wrote out a simple program that computes the K-th permutation from 0 to N-1 where the number of permutations is N!. What I was wondering is could I get some pointers on how to improve and re-write the permutation function to be more efficient--e.g. possibly getting rid of the vector and the for-loop to calculate the factorial.

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

The function factorial_permutation calculates the factorial representation of K--the K-th iteration--in a sequence from 0 to (N-1)! possible permutations. The main() function does simple conversion from the factorial representation to building the actual sequence. I would like to combine the two and see if I can negate the vectors all together for the sake of performance.

I'm also aware that I can remove the vector in factorial_permutation by using a basic array, but I can't seem to negate the one in the main() function.

\$\endgroup\$
  • \$\begingroup\$ Any particular C++ standard you are using for this? C++11/14/17? \$\endgroup\$ – Arnav Borborah Feb 27 '18 at 1:23
  • \$\begingroup\$ Doesn't matter. For sake of reference, C++17. \$\endgroup\$ – FatalSleep Feb 27 '18 at 2:11
4
\$\begingroup\$
  • The loop

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

    is idiomatically expressed as std::iota(s.begin(), s.end(), 0) (you'd need to #include <numeric>).

  • A no naked loops principle demands giving a name to the

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

    loop. It surely represents an important algorithm. What exactly does it do?

    In any case, the s and e vectors shall not be exposed to the client.

  • Computing factorials restricts the utility of the code to N < 21 (21! = 0x2_c507_7d36_b8c4_0000 doesn't fit in 64 bits). Unfortunately you cannot even express K within uint64_t limits for larger N. Consider BigInteger.

  • It is possible to avoid factorials (as well as ancillary vectors) by working other way around. Consider a pseudocode:

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

    While correct, it doesn't produce the same K'th permutation as your code does. May I suggest changing it to produce the correct sequence as an exercise?

PS: a mandatory warning on using namespace std

\$\endgroup\$
  • 2
    \$\begingroup\$ std::iota() isn't a direct replacement there - it's a shame there's no std::iota_n that could take a back-insert iterator. \$\endgroup\$ – Toby Speight Feb 27 '18 at 8:44
  • \$\begingroup\$ Thank you for the answer I've revised my code to include comments. My apologies it's not the best code/commented. I mocked it up really quick. \$\endgroup\$ – FatalSleep Feb 27 '18 at 17:15
  • \$\begingroup\$ @vnp unfortunately std:iota() doesn't work here if s is a length of 0. Unless I defined s as vector<uint64_t> s(N); which might save some performance, if any. \$\endgroup\$ – FatalSleep Feb 27 '18 at 17:25
  • \$\begingroup\$ @vnp I'll try out your changes here and get back to you. I don't care how it produces the permutations, just that it produces them faster and without duplicates and covers the N! number of permutations requirements. \$\endgroup\$ – FatalSleep Feb 27 '18 at 17:30

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.