Obtaining all subpacks from a pack

Question

PowerSet<Pack<Types...>>::type is to give a pack consisting of packs formed by all subsets of Types... (for now assume the static assertion that every type in Types... are distinct). For example,

PowerSet<Pack<int, char, double>>::type

is to be

Pack<Pack<>, Pack<int>, Pack<char>, Pack<double>, Pack<int, char>, Pack<int, double>, Pack<char, double>, Pack<int, char, double>>

Now, I've solved this exercise and tested it, but my solution is very long and would like to hear some more elegant ideas. I'm not asking anyone to review my solution, but suggest a new method altogether, perhaps sketch their idea with some pseudocode.

In case you wanted to know, this is what I did: First, I recalled from high school that a set of N elements has 2^N subsets. Each subset corresponds to an N-digit binary number, e.g. 001010...01 (N digits long), where 0 means that the element is in the subset and 1 means that the element is not in the subset. Thus 000...0 would represent the empty subset, and 111...1 would represent the entire set itself. So using the (template) sequence 0,1,2,3,...2^N-1, I formed 2^N index_sequence's, each corresponding to the binary representation of the integers in that sequence, e.g. index_sequence<1,1,0,1> would correspond to 13 from that sequence. Then each of those 2^N index_sequence's will be converted to the desired 2^N subsets of Pack<Types...>.

My solution below is quite long, and I know that there is a more elegant method than the very mechanical one described above. If you've thought of a better plan (perhaps shorter too because it is more recursive or whatever), please post your idea so that I can take on your better plan, hoping to write out a shorter solution. I don't expect you to write out your solution in full if you think it will probably take some time (unless you want to). But currently, I can't think of another way than what I've done. Here is my current longish solution in case you want to read it:

#include <iostream>
#include <cmath>
#include <typeinfo>

// SubsetFromBinaryDigits<P<Types...>, Is...>::type gives the sub-pack of P<Types...> where 1 takes the type and 0 does not take the type.  The size of the two packs must be the same.
// For example, SubsetFromBinaryDigits<Pack<int, double, char>, 1,0,1>::type gives Pack<int, char>.

template <typename, typename, int...> struct SubsetFromBinaryDigitsHelper;

template <template <typename...> class P, typename... Accumulated, int... Is>
struct SubsetFromBinaryDigitsHelper<P<>, P<Accumulated...>, Is...> {
    using type = P<Accumulated...>;
};

template <template <typename...> class P, typename First, typename... Rest, typename... Accumulated, int FirstInt, int... RestInt>
struct SubsetFromBinaryDigitsHelper<P<First, Rest...>, P<Accumulated...>, FirstInt, RestInt...> :
    std::conditional<FirstInt == 0,
        SubsetFromBinaryDigitsHelper<P<Rest...>, P<Accumulated...>, RestInt...>,
        SubsetFromBinaryDigitsHelper<P<Rest...>, P<Accumulated..., First>, RestInt...>
    >::type {};

template <typename, int...> struct SubsetFromBinaryDigits;

template <template <typename...> class P, typename... Types, int... Is>
struct SubsetFromBinaryDigits<P<Types...>, Is...> : SubsetFromBinaryDigitsHelper<P<Types...>, P<>, Is...> {};

// struct NSubsets<P<Types...>, IntPacks...>::type is a pack of packs, with each inner pack being the subset formed by the IntPacks.
// For example, NSubsets< Pack<int, char, long, Object, float, double, Blob, short>, index_sequence<0,1,1,0,1,0,1,1>, index_sequence<0,1,1,0,1,0,1,0>, index_sequence<1,1,1,0,1,0,1,0> >::type will give
// Pack< Pack<char, long, float, Blob, short>, Pack<char, long, float, Blob>, Pack<int, char, long, float, Blob> >

template <typename, typename, typename...> struct NSubsetsHelper;

template <template <typename...> class P, typename... Types, typename... Accumulated>
struct NSubsetsHelper<P<Types...>, P<Accumulated...>> {
    using type = P<Accumulated...>;
};

template <template <typename...> class P, typename... Types, typename... Accumulated, template <int...> class Z, int... Is, typename... Rest>
struct NSubsetsHelper<P<Types...>, P<Accumulated...>, Z<Is...>, Rest...> :
    NSubsetsHelper<P<Types...>, P<Accumulated..., typename SubsetFromBinaryDigits<P<Types...>, Is...>::type>, Rest...> {};

template <typename, typename...> struct NSubsets;

template <template <typename...> class P, typename... Types, typename... IntPacks>
struct NSubsets<P<Types...>, IntPacks...> : NSubsetsHelper<P<Types...>, P<>, IntPacks...> {};

// Now, given a pack with N types, we transform index_sequence<0,1,2,...,2^N> to a pack of 2^N index_sequence packs, with the 0's and 1's of each
// index_sequence pack forming the binary representation of the integer.  For example, if N = 2, then we have
// Pack<index_sequence<0,0>, index_sequence<0,1>, index_sequence<1,0>, index_sequence<1,1>>.  From these, we can get the
// power set, i.e. the set of all subsets of the original pack.

template <int N, int Exponent, int PowerOfTwo>
struct LargestPowerOfTwoUpToHelper {
    using type = typename std::conditional<(PowerOfTwo > N),
        std::integral_constant<int, Exponent>,
        LargestPowerOfTwoUpToHelper<N, Exponent + 1, 2 * PowerOfTwo>
    >::type;
    static const int value = type::value;
};

template <int N>
struct LargestPowerOfTwoUpTo : std::integral_constant<int, LargestPowerOfTwoUpToHelper<N, -1, 1>::value> {};

constexpr int power (int base, int exponent) {
    return std::pow (base, exponent);
}

template <int...> struct index_sequence {};

// For example, PreBinaryIndexSequence<13>::type is to be index_sequence<0,2,3>, since 13 = 2^3 + 2^2 + 2^0.
template <int N, int... Accumulated>
struct PreBinaryIndexSequence {  // Could use another helper, since LargestPowerOfTwoUpToHelper<N, -1, 1>::value is being used twice.
    using type = typename PreBinaryIndexSequence<N - power(2, LargestPowerOfTwoUpToHelper<N, -1, 1>::value), LargestPowerOfTwoUpToHelper<N, -1, 1>::value, Accumulated...>::type;
};

template <int... Accumulated>
struct PreBinaryIndexSequence<0, Accumulated...> {
    using type = index_sequence<Accumulated...>;
};

// For example, BinaryIndexSequenceHelper<index_sequence<>, index_sequence<0,2,3>, 0, 7>::type is to be index_sequence<1,0,1,1,0,0,0,0> (the first index with position 0, and the last index is position 7).
template <typename, typename, int, int> struct BinaryIndexSequenceHelper;

template <template <int...> class Z, int... Accumulated, int First, int... Rest, int Count, int MaxCount>
struct BinaryIndexSequenceHelper<Z<Accumulated...>, Z<First, Rest...>, Count, MaxCount> : std::conditional<First == Count,
        BinaryIndexSequenceHelper<Z<Accumulated..., 1>, Z<Rest...>, Count + 1, MaxCount>,
        BinaryIndexSequenceHelper<Z<Accumulated..., 0>, Z<First, Rest...>, Count + 1, MaxCount>
    >::type {};

// When the input pack is emptied, but Count is still less than MaxCount, fill the rest of the acccumator pack with 0's.
template <template <int...> class Z, int... Accumulated, int Count, int MaxCount>
struct BinaryIndexSequenceHelper<Z<Accumulated...>, Z<>, Count, MaxCount> : BinaryIndexSequenceHelper<Z<Accumulated..., 0>, Z<>, Count + 1, MaxCount> {};

template <template <int...> class Z, int... Accumulated, int MaxCount>
struct BinaryIndexSequenceHelper<Z<Accumulated...>, Z<>, MaxCount, MaxCount> {
    using type = Z<Accumulated...>;
};

// At last, BinaryIndexSequence<N> is the binary representation of N using index_sequence, e.g. BinaryIndexSequence<13,7> is index_sequence<1,0,1,1,0,0,0>.
template <int N, int NumDigits>
using BinaryIndexSequence = typename BinaryIndexSequenceHelper<index_sequence<>, typename PreBinaryIndexSequence<N>::type, 0, NumDigits>::type;

// Now define make_index_sequence<N> to be index_sequence<0,1,2,...,N-1>.
template <int N, int... Is>
struct make_index_sequence_helper : make_index_sequence_helper<N-1, N-1, Is...> {};  // make_index_sequence_helper<N-1, N-1, Is...> is derived from make_index_sequence_helper<N-2, N-2, N-1, Is...>, which is derived from make_index_sequence_helper<N-3, N-3, N-2, N-1, Is...>, which is derived from ... which is derived from make_index_sequence_helper<0, 0, 1, 2, ..., N-2, N-1, Is...>

template <int... Is>
struct make_index_sequence_helper<0, Is...> {
    using type = index_sequence<Is...>;
};

template <int N>
using make_index_sequence = typename make_index_sequence_helper<N>::type;

// Finally, ready to define PowerSet itself.
template <typename, typename> struct PowerSetHelper;

template <template <typename...> class P, typename... Types, template <int...> class Z, int... Is>
struct PowerSetHelper<P<Types...>, Z<Is...>> : NSubsets< P<Types...>, BinaryIndexSequence<Is, sizeof...(Types)>... > {};

template <typename> struct PowerSet;

template <template <typename...> class P, typename... Types>
struct PowerSet<P<Types...>> : PowerSetHelper<P<Types...>, make_index_sequence<power(2, sizeof...(Types))>> {};

// -----------------------------------------------------------------------------------------------------------------------------------------------
// Testing

template <typename...> struct Pack {};

template <typename Last>
struct Pack<Last> {
    static void print() {std::cout << typeid(Last).name() << std::endl;}
};

template <typename First, typename ... Rest>
struct Pack<First, Rest...> {
    static void print() {std::cout << typeid(First).name() << ' ';  Pack<Rest...>::print();}
};

template <int Last>
struct index_sequence<Last> {
    static void print() {std::cout << Last << std::endl;}
};

template <int First, int ... Rest>
struct index_sequence<First, Rest...> {
    static void print() {std::cout << First << ' ';  index_sequence<Rest...>::print();}
};

int main() {
    PowerSet<Pack<int, char, double>>::type powerSet;
    powerSet.print();
}

Answer 1

Here's my attempt:

template<typename,typename> struct Append;

template<typename...Ts,typename T>
struct Append<Pack<Ts...>,T>
{
    using type = Pack<Ts...,T>;
};

template<typename,typename T=Pack<Pack<>>>
struct PowerPack
{
    using type = T;
};

template<typename T,typename...Ts,typename...Us>
struct PowerPack<Pack<T,Ts...>,Pack<Us...>>
    : PowerPack<Pack<Ts...>,Pack<Us...,typename Append<Us,T>::type...>>
{
};

Live example

Answer 2

The key is to establish a recurrence relation:

PowerSet of {A, B, C}
== (PowerSet of {B,C}) U (PowerSet of {B,C} w/ A)

where the w/ A part simply refers to adding A into every subset. Given that, we need three metafunctions: Plus, to take the union of two Packs, Prefix, to add a type to every element in a Pack, and lastly, PowerSet. The Three Ps, if you will.

In increasing order of complexity. Plus just jams the packs together:

template <typename A, typename B> struct Plus;

template <typename... A, typename... B>
struct Plus<Pack<A...>, Pack<B...>> {
    using type = Pack<A..., B...>;
};

Prefix just uses Plus to add Pack<A> to everything:

template <typename A, typename P> struct Prefix;

template <typename A, typename... P>
struct Prefix<A, Pack<P...> >
{
    using type = Pack<typename Plus<Pack<A>, P>::type...>;
};

And then PowerSet is a direct translation of the recurrence:

template <typename P> struct PowerSet;

template <typename T0, typename... T>
struct PowerSet<Pack<T0, T...>>
{
    using rest = typename PowerSet<Pack<T...>>::type;
    using type = typename Plus<rest,
                               typename Prefix<T0, rest>::type
                               >::type;
};

template <>
struct PowerSet<Pack<>>
{
    using type = Pack<Pack<>>;
};