Generate all possible permutations of n objects.

heap.cpp

// non-recursive version of algorythm presented here:
// http://ruslanledesma.com/2016/06/17/why-does-heap-work.html

#include <algorithm>
#include <array>
#include <stddef.h>
#include <stdio.h>
#include <vector>

template <typename type_t>
struct heap_permute_t {

  struct state_t {
    size_t i, n;
  };

  heap_permute_t(type_t *data, size_t size)
    : len(size), s(data) {
    state.reserve(size);
    state.push_back(state_t{0, size});
  }

  bool permute() {
    bool broken = false;
    while (!state.empty()) {
      size_t &i = state.back().i;
      size_t &n = state.back().n;
      if (!broken) {
        if (n > 2) {
          state.push_back(state_t{0, n - 1});
          continue /* enter */;
        }
      }
      // <---- note: we effectively go here when we break
      broken = false;
      if (i >= n - 1) {
        state.pop_back();
        broken = true;
        continue /* break */;
      }
      std::swap(s[(n & 1) ? 0 : i], s[n - 1]);
      ++i;
      return true /* yield */;
    }
    return false /* final exit */;
  }

protected:
  std::vector<state_t> state;
  size_t n, len;
  type_t *s;
};

int main() {
  std::array<char, 1024> s = {0};
  printf("enter text: ");
  scanf("%s", s.data());
  const size_t len = strlen(s.data());
  heap_permute_t<char> itt{s.data(), len};
  do {
    printf("%s\n", s.data());
  } while (itt.permute());
  return 0;
}