List all unique sets for a range of integers.

permutations.cc

// clang++ -std=c++11 permutations.cc -o permutations

#include <iostream>
#include <ostream>
#include <set>
#include <vector>

template<typename T>
auto operator<<(std::ostream &os, const std::set<T> &xs) -> std::ostream& {
  os << '{';
  if (xs.size()) {
    const auto last = --xs.end();
    auto it = xs.begin();
    for (; it != last; ++it)
      os << *it << ", ";
    os << *it;
  }
  os << '}';
  return os;
}

auto num_permut(size_t n) -> size_t {
  return (n == 0)? 0 : (1 << n);
}

auto main(int argc, char **argv) -> int {
  const auto n = (argc > 1)? atoi(argv[1]) : 5;
  const auto p = num_permut(n);
  auto v = std::vector<std::set<size_t>>(p);

  auto alpha = p;
  for (auto i = 0; i < n; ++i) {
    alpha /= 2;
    auto j = 0u;
    while (j < p) {
      for (auto a = 0; a < alpha; ++a)
        v[j++].insert(i);
      j += alpha;
    }
  }

  for (auto i = 0u; i < v.size(); ++i)
    std::cout << i << ": " << v[i] << std::endl;

  return 0;
}