Is Heap's algorithm for generating permutations faster than next_ permutation()? [closed]

Question

Is there a method faster than this method to print all permutations of a string:

#include <bits/stdc++.h>
using namespace std;
int main()
{
  string s;
  cin >> s;
  sort(s.begin(), s.end());
  do {
    cout << s <<" ";
  } while (next_permutation(s.begin(), s.end()));
}

Answer 1

The typical implementation of next_permutation is stateless and requires scanning the input array once to detect an element that is not in order, then an other scan to detect the next largest element and finally reversing a subsection. While this has the asymptotic complexity of merely O(N), it has still some work done for the logic.

With N nested loops one can obviously reduce some of the complexity. N nested loops can also be emulated with a stack.

Dealing with duplicate letters is a concern that is probably not that easily implemented exactly as std::next_permutation does it.