从模板包生成所有大小为 N 的子包

Question

NSubsets<N, Pack<Types...>>::type 是由大小为 N 的 Types... 的所有子集组成的包的包。例如，

NSubsets<2, Pack<int, char, double>>::type

即将

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

一种方法是简单地从中获取 PowerSet 解决方案的输出，然后删除每个不是 N 大小的包。但这对于大 N 来说效率太低了（而且很糟糕）。这是我的想法（灵感来自 PowerSet 的优雅解决方案）：假设我们有 Pack<A,B,C,D>，并且 N = 2。从 Pack<> 开始，我们遍历 Pack<A,B,C,D> 中的类型并附加每个类型，如下所示：在附加任何内容之前，我们有：

Pack<>

将 A 附加到前一个（并保留前一个），我们得到：

Pack<>, Pack<A>

将 B 附加到前一个（并保留前一个），我们得到：

Pack<>, Pack<A>, Pack<B>, Pack<A,B>,

但是 Pack<A,B> 的尺寸为 2，所以把它藏起来，然后从这个列表中取出，留下：

Pack<>, Pack<A>, Pack<B>

将 C 附加到前一个（并保留前一个），我们得到：

Pack<>, Pack<A>, Pack<B>, Pack<C>, Pack<A,C>, Pack<B,C>.

像上面一样，藏起来Pack<A,C>, Pack<B,C>:

Pack<>, Pack<A>, Pack<B>, Pack<C>

将 D 附加到前一个（并保留前一个），我们得到：

Pack<D>, Pack<A,D>, Pack<B,D>, Pack<C,D>.

再拿 2 号的，我们现在终于有了

Pack<Pack<A,B>, Pack<A,C>, Pack<B,C>, Pack<A,D>, Pack<B,D>, Pack<C,D>>

作为我们想要的输出。

请注意，此算法的一个缺陷是无缘无故地在倒数第二步中保留 Pack<>。如果 N 大于 2，这个多余的部分真的很浪费时间。 以下是我使用上述方法的代码，但输出为 false，我无法追踪原因（目前）。但即使如果它确实工作正常，我仍然不太喜欢它，主要是因为我刚才提到的缺陷，我不知道如何也可以消除该缺陷。

#include <iostream>
#include <type_traits>

template <int, typename> struct IsSize;

template <int N, template <typename...> class P, typename... Types>
struct IsSize<N, P<Types...>> : std::integral_constant<bool, sizeof...(Types) == N> {};

template <int, typename, typename, typename> struct PartitionPacksBySizeHelper;

template <int N, template <typename...> class P, typename... KeptPacks, typename... SizeNPacks>
struct PartitionPacksBySizeHelper<N, P<>, P<KeptPacks...>, P<SizeNPacks...>> {
    using not_sizeN_types = P<KeptPacks...>;
    using sizeN_types = P<SizeNPacks...>;
};

template <int N, template <typename...> class P, typename First, typename... Rest, typename... KeptPacks, typename... SizeNPacks>
struct PartitionPacksBySizeHelper<N, P<First, Rest...>, P<KeptPacks...>, P<SizeNPacks...>> : std::conditional<IsSize<N, First>::value,
        PartitionPacksBySizeHelper<N, P<Rest...>, P<KeptPacks...>, P<SizeNPacks..., First>>,
        PartitionPacksBySizeHelper<N, P<Rest...>, P<KeptPacks..., First>, P<SizeNPacks...>>
    >::type {};

template <int, typename> struct PartitionPacksBySize;

template <int N, template <typename...> class P, typename... Packs>
struct PartitionPacksBySize<N, P<Packs...>> : PartitionPacksBySizeHelper<N, P<Packs...>, P<>, P<>> {};

template <typename, typename> struct Append;

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

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

template <int N, template <typename...> class P, typename... CurrentPacks, typename... AccumulatedPacks>
struct NSubsetsHelper<N, P<>, P<CurrentPacks...>, P<AccumulatedPacks...>> {
    using type = P<AccumulatedPacks...>;
};

template <int N, template <typename...> class P, typename First, typename... Rest, typename... KeptPacks, typename... SizeNPacks>
struct NSubsetsHelper<N, P<First, Rest...>, P<KeptPacks...>, P<SizeNPacks...>>
    : NSubsetsHelper<N, P<Rest...>,
        typename PartitionPacksBySize<N, P<KeptPacks..., typename Append<First, KeptPacks>::type...>>::not_sizeN_types,
        typename PartitionPacksBySize<N, P<KeptPacks..., typename Append<First, KeptPacks>::type...>>::sizeN_types> {};

template <int, typename> struct NSubsets;

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

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

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

int main() {
    std::cout << std::boolalpha << std::is_same< NSubsets<2, Pack<int, char, double>>::type,
        Pack<Pack<int, char>, Pack<int, double>, Pack<char, double>>
    >::value << std::endl;  // false (darn!)
}

我在纸上查了一下输出应该是上面的包，当我改变包的顺序时，还是报错。但是，正如我上面提到的，无论如何，这种方法还是很差。对更好的方法有什么建议吗？

更新： 发现错误，替换

typename PartitionPacksBySize<N, P<KeptPacks..., typename Append<First, KeptPacks>::type...>>::sizeN_types>

和

typename Merge<P<SizeNPacks...>, typename PartitionPacksBySize<N, P<KeptPacks..., typename Append<First, KeptPacks>::type...>>::sizeN_types>::type

但是，当 N 很大时，您看到我的算法在最后 N 次迭代中是如何浪费时间的吗？

Answer 1

我们可以从一开始就精确地生成大小为 k 的子集——这样会更有效率，因为我们只需要做 O(n^k) 的工作而不是 O(2^n) 的工作。这里的算法只是遍历所有 n 位恰好 k 1 的单词的排列，并为每个单词添加适当的 Pack.

我们首先从 bithack 开始，以 constexpr 形式找到 next permutation：

constexpr int ctz(size_t n) {
    return n & 1 ? 0 : 1 + ctz(n >> 1); 
}

constexpr size_t next_perm_impl(size_t v, size_t t) {
    return (t + 1) | (((~t & -~t) - 1) >> (ctz(v) + 1));
}

constexpr size_t next_perm(size_t v) {
    return next_perm_impl(v, v | (v - 1));
}

接下来，我获取 Columbo 的累加器，他出于某种原因删除了您对上一个问题的回答：

template <class... T> struct Pack { using type = Pack; };

template <size_t size, class result, class>
struct accumulator : result { };

template <size_t j, class... R, class T1, class... T>
struct accumulator<j, Pack<R...>, Pack<T1, T...>>
: accumulator<(j>>1), typename std::conditional<j&1, Pack<R..., T1>, Pack<R...>>::type, Pack<T...>>
{};

给定值 j，我们可以确定与这些元素关联的 Pack。现在我们只需要从 (1 << k) - 1 迭代到 (1 << N) + (1 << (k-1)) - 1。可能有更有效的方法来执行此操作，但以下方法有效：

template <typename P, typename Result, size_t CUR, size_t LAST>
struct PowerPackImpl;

template <typename P, typename... R, size_t CUR, size_t LAST>
struct PowerPackImpl<P, Pack<R...>, CUR, LAST>
: PowerPackImpl<P,
                Pack<R..., typename accumulator<CUR, Pack<>, P>::type>,
                next_perm(CUR),
                LAST>
{ };

template <typename P, typename... R, size_t LAST>
struct PowerPackImpl<P, Pack<R...>, LAST, LAST>
: Pack<R...> { };

template <typename P, size_t K> struct PowerPack;

template <typename... P, size_t K>
struct PowerPack<Pack<P...>, K>
: PowerPackImpl<Pack<P...>, Pack<>, (1 << K) - 1, (1 << sizeof...(P)) + (1 << (K-1)) - 1>
{ };

例如：

static_assert(std::is_same<
    typename PowerPack<Pack<int, char, double, float>, 1>::type,
    Pack<Pack<int>, Pack<char>, Pack<double>, Pack<float>>
>::value, "1 works");

static_assert(std::is_same<
    typename PowerPack<Pack<int, char, double, float>, 2>::type,
    Pack<Pack<int, char>, Pack<int, double>, Pack<char, double>, Pack<int, float>, Pack<char, float>, Pack<double, float> >
>::value, "2 works");

Answer 2

这是基于 PowerPack 的解决方案，但过长条目的过滤发生在每个步骤中，因此比仅在最后过滤更有效。

第 1 步：NAppend<N,Pack<...>,T> 仅将新类型 T 附加到 Pack<...>，前提是它之后的条目不超过 N。

template<std::size_t,typename,typename>
struct NAppend
{
    using type = void;
};

template<std::size_t N,typename...Ts,typename T>
struct NAppend<N,Pack<Ts...>,T>
{
    using type =
        typename std::conditional<
            sizeof...(Ts)==N,
            void,
            Pack<Ts...,T>
        >::type;
};

第 2 步：ShrinkPack 从 Pack 的 Pack 和 void 中删除 void。

template<typename,typename U=Pack<>>
struct ShrinkPack
{
    using type = U;
};

template<typename T,typename...Ts,typename...Us>
struct ShrinkPack<Pack<T,Ts...>,Pack<Us...>>
    : std::conditional<
        std::is_void<T>::value,
        ShrinkPack<Pack<Ts...>,Pack<Us...>>,
        ShrinkPack<Pack<Ts...>,Pack<Us...,T>>
      >::type
{
};

第 3 步：NPack 过滤掉所有不大小合适的条目。

template<std::size_t,typename,typename U=Pack<>>
struct NPack
{
    using type = U;
};

template<std::size_t N,typename...Ts,typename...Us,typename...Vs>
struct NPack<N,Pack<Pack<Ts...>,Us...>,Pack<Vs...>>
    : std::conditional<
        sizeof...(Ts)==N,
        NPack<N,Pack<Us...>,Pack<Vs...,Pack<Ts...>>>,
        NPack<N,Pack<Us...>,Pack<Vs...>>
      >::type
{
};

最后一步：适应的扩展，类似于 PowerPack 并在每个扩展步骤应用 ShrinkPack 并在最后应用一次 NPack。

template<std::size_t N,typename,typename T=Pack<Pack<>>>
struct NPowerPack
{
    using type = typename NPack<N,T>::type;
};

template<std::size_t N,typename T,typename...Ts,typename...Us>
struct NPowerPack<N,Pack<T,Ts...>,Pack<Us...>>
    : NPowerPack<N,Pack<Ts...>,typename ShrinkPack<Pack<Us...,typename NAppend<N,Us,T>::type...>>::type>
{
};

测试：

static_assert(std::is_same<
    NPowerPack<1,Pack<int, char, double>>::type,
    Pack<Pack<int>, Pack<char>, Pack<double>>
>(), "");

static_assert(std::is_same<
    NPowerPack<2,Pack<int, char, double>>::type,
    Pack<Pack<int, char>, Pack<int, double>, Pack<char, double>>
>(), "");

Live example

从模板包生成所有大小为 N 的子包

Generating all subpacks of size N from a template pack

c++

templates

combinatorics

variadic-templates

c++11