Create a gist now

Instantly share code, notes, and snippets.

@8BitPimp /heap.cpp
Last active Jul 2, 2017

What would you like to do?
Generate all possible permutations of n objects.
// 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;
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment