0

A bit of background first:

I am an amateur programmer, with a background of Mathematica (and more recently Haskell) programming revolving mostly around Codeabbey problems.

Recently I have been trying to implement a permutations generation code with repetition, that is a program which, given an input number, will produce a list of permutations taking into account duplicate numbers. So for example if I input 58883 it will output a list of only 20 numbers (5!/3!), not 120.

It has been brought to my attention that the code in this answer https://stackoverflow.com/a/26716166/2579629 does exactly that, and I can confirm that it does so extremely well resource-wise, because I can get as far as compiling with g++ and running it.

Other than that I am clueless when it comes to C and I can't understand how the code works. I believe that the core of the code is in these few lines

    while (*q) {
        if (used.find(*q) == used.end()) {
            std::swap(*p, *q);
            perm(str, index + 1);
            std::swap(*p, *q);

            used.insert(*q);
        }

that recursion is used and that a concept of Sets is used. Other than that I'm lost.

So, can someone explain to me how this algorithm is supposed to work, meaning an explanation of what is going on, in steps that the computer is supposed to follow, that is in plain English, independent of language syntax, and what purpose do Sets serve in this case?

Much obliged! Have a good day!

aaaaaa123456789
  • 5,541
  • 1
  • 20
  • 33
Κωστής Καρβουνιάρης
  • 197
  • 2
  • 10
  • 1
    The set is used to keep duplicates out. For each position in the string, the program keeps a set of characters that it has already tried at that index. But when the program backtracks it starts fresh with an empty set. – Jerry Jeremiah May 10 '21 at 07:19
  • I would use [`std::next_permutation`](https://en.cppreference.com/w/cpp/algorithm/next_permutation). – Jarod42 May 10 '21 at 08:08

0 Answers0