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

NSubsets<N, Pack<Types...>>::type is to be the pack of packs consisting of all subsets of Types... of size N. For example,

NSubsets < N,包 <类型……类型是由所有类型的子集组成的包的集合。大小为n，例如，< p>

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

is to be

是

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

One method is to simply take the output of the PowerSet solution from Obtaining all subpacks from a pack, and then remove each pack that are not of size N. But this is way too inefficient for large N (and is plain bad anyway). Here is my idea (inspired by the elegant solutions for PowerSet): Suppose we have Pack<A,B,C,D>, and N = 2. Starting with Pack<>, we iterate through the types in Pack<A,B,C,D> and append each type like so: Before appending anything, we have:

一种方法是从一个包中获取所有子包的PowerSet解决方案的输出，然后删除每个大小不是N的包，但是这对于大N来说效率太低(无论如何都是很糟糕的)。这里是我的想法(灵感来自于PowerSet优雅的解决方案):假设我们有Pack 和N = 2。从Pack<>开始，我们对Pack 中的类型进行迭代，并将每一个类型添加如下: ,b,c,d> ,b,c,d>

Pack<>

Appending A to the previous (and keeping the previous as well), we get:

将A加到前一个(同时保留前一个)，我们得到:

Pack<>, Pack<A>

Appending B to the previous (and keeping the previous as well), we get:

将B加到前一个(同时保留前一个)，我们得到:

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

but Pack<A,B> has size 2 so stash it away and take it out from this list, leaving us with:

但是打包有2号所以把它藏起来，从这个列表中取出来，留给我们: ,b>

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

Appending C to the previous (and keeping the previous as well), we get:

将C加到前一个(同时保留前一个)，我们得到:

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

Like above, stash away Pack<A,C>, Pack<B,C>:

如上图所示，暗藏包，包 : ,c> ,c>

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

Appending D to the previous (and keeping the previous as well), we get:

在前一个后面加上D(也保留前一个)，我们得到:

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

Taking the ones of size 2 again, we now finally have

再看看2号的，我们终于有了

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

as our desired output.

正如我们所期望的输出。

Note that one flaw in this algorithm is keeping Pack<> in the second last step for no reason. If N is bigger than 2, this extraneous part can really waste time. The following is the code I have using the above method, but the output gives false, and I couldn't trace why (yet). But even if it did work correctly, I still don't like it too much, mainly because of the flaw above I just mentioned, and I don't know how to remove that flaw either.

注意，该算法的一个缺陷是在最后一步中毫无理由地保留Pack<>。如果N大于2，这个无关的部分就会浪费时间。下面是我使用上述方法的代码，但是输出是假的，我无法追踪原因(然而)。但是即使它正确地工作了，我还是不太喜欢它，主要是因为我刚才提到的缺陷，我也不知道如何去除那个缺陷。

#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!)
}

I traced on paper that the above pack should be the output, and when I change the order of the packs, it still gives false. But still, the method is inferior anyway, as I mentioned above. Any suggestions on a better method?

我在纸上追踪到上面的包应该是输出，当我改变包的顺序时，它仍然会给出false。但是，正如我上面提到的，这种方法还是很差。对更好的方法有什么建议吗?

Update: I found my mistake, and replaced

更新:我发现了我的错误，并被替换

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

with

与

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

But still, you see how my algorithm really wastes time in the last N iterations when N is large?

但是你看我的算法是如何在N大的时候浪费最后N次迭代的时间的?

2 个解决方案

#1

This is based on the PowerPack solution, but the filtering of too-long entries happens in each step and is therefore more efficient than just filtering at the end.

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

Step 1: NAppend<N,Pack<...>,T> only appends the new type T to the Pack<...> if it does not have more than N entries afterwards.

步骤1:NAppend < N,包<…>，T>只将新类型T附加到包<…>如果后面没有超过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;
};

Step 2: ShrinkPack removes void from a Pack of Packs and voids.

步骤2:ShrinkPack从包和空隙中移除空隙。

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
{
};

Step 3: NPack filters out all entries that are not of the right size.

步骤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
{
};

Final step: The adapted expansion, similar to PowerPack and applying ShrinkPack at each expansion step and NPack once at the end.

最后一步:适应的扩展，类似于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>
{
};

Tests:

测试:

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

生活的例子

#2

We can generate precisely the subsets of size k from the outset - this will be more efficient in that we only need to do O(n^k) work instead of O(2^n) work. The algorithm here is just to iterate over all the permutations of words of n bits that have exactly k 1s, and for each word to add the appropriate Pack.

我们可以生成精确的子集的大小k从一开始,这将是更有效的,我们只需要O(n ^ k)的工作,而不是O(2 ^ n)工作。这里的算法是遍历所有n位的排列它们都有k个1，每个单词都要加入相应的包。

We start first with a bithack for finding the next permutation, in constexpr form:

我们首先从一个bithack开始寻找下一个排列，以constexpr形式:

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));
}

Next I grab Columbo's accumulator that he deleted for some reason off the answer to your previous question:

接下来，我拿起科伦坡的蓄能器，他出于某种原因删除了你之前问题的答案:

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...>>
{};

Given a value j, we can determine the Pack associated with those elements. Now we just need to iterate from (1 << k) - 1 up to (1 << N) + (1 << (k-1)) - 1. There's probably a more efficient way to do this, but the following works:

给定一个值j，我们可以确定与这些元素相关联的包。现在我们只需要从(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>
{ };

For instance:

例如:

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");

#1