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

coder 2024-02-22 原文

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

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

应该是

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

一种方法是简单地获取 PowerSet 的输出来自 Obtaining all subpacks from a pack 的解决方案, 然后删除每个不是 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 次迭代中是如何浪费时间的吗？

最佳答案

我们可以精确地生成大小为 k 的子集从一开始 - 这将更有效率，因为我们只需要做 O(n^k)代替 O(2^n) 工作工作。这里的算法只是迭代n的所有单词排列。正好有 k 的位1s，并为每个单词添加适当的Pack .

我们首先从寻找 next permutation 的 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));
}

接下来，我获取 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");

关于c++ - 从模板包生成所有大小为 N 的子包，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/28504167/

amp 43 lt gt typename c++templates c++11 variadic-templates combinatorics

有关c++ - 从模板包生成所有大小为 N 的子包的更多相关文章

ruby - 使用 RubyZip 生成 ZIP 文件时设置压缩级别 - 2
我有一个Ruby程序，它使用rubyzip压缩XML文件的目录树。gem。我的问题是文件开始变得很重，我想提高压缩级别，因为压缩时间不是问题。我在rubyzipdocumentation中找不到一种为创建的ZIP文件指定压缩级别的方法。有人知道如何更改此设置吗？是否有另一个允许指定压缩级别的Ruby库？最佳答案这是我通过查看rubyzip内部创建的代码。level=Zlib::BEST_COMPRESSIONZip::ZipOutputStream.open(zip_file)do|zip|Dir.glob("**/*")d
ruby-on-rails - 在 Rails 中将文件大小字符串转换为等效千字节 - 2
我的目标是转换表单输入，例如“100兆字节”或“1GB”，并将其转换为我可以存储在数据库中的文件大小(以千字节为单位)。目前，我有这个:defquota_convert@regex=/([0-9]+)(.*)s/@sizes=%w{kilobytemegabytegigabyte}m=self.quota.match(@regex)if@sizes.include?m[2]eval("self.quota=#{m[1]}.#{m[2]}")endend这有效，但前提是输入是倍数(“gigabytes”，而不是“gigabyte”)并且由于使用了eval看起来疯狂不安全。所以，功能正常，
ruby - 如何以所有可能的方式将字符串拆分为长度最多为 3 的连续子字符串？ - 2
我试图获取一个长度在1到10之间的字符串，并输出将字符串分解为大小为1、2或3的连续子字符串的所有可能方式。例如:输入:123456将整数分割成单个字符，然后继续查找组合。该代码将返回以下所有数组。[1,2,3,4,5,6][12,3,4,5,6][1,23,4,5,6][1,2,34,5,6][1,2,3,45,6][1,2,3,4,56][12,34,5,6][12,3,45,6][12,3,4,56][1,23,45,6][1,2,34,56][1,23,4,56][12,34,56][123,4,5,6][1,234,5,6][1,2,345,6][1,2,3,456][123
ruby-on-rails - 如何优雅地重启 thin + nginx？ - 2
我的瘦服务器配置了nginx，我的ROR应用程序正在它们上运行。在我发布代码更新时运行thinrestart会给我的应用程序带来一些停机时间。我试图弄清楚如何优雅地重启正在运行的Thin实例，但找不到好的解决方案。有没有人能做到这一点？最佳答案 #Restartjustthethinserverdescribedbythatconfigsudothin-C/etc/thin/mysite.ymlrestartNginx将继续运行并代理请求。如果您将Nginx设置为使用多个上游服务器，例如server{listen80;server
ruby - 在 jRuby 中使用 'fork' 生成进程的替代方案？ - 2
在MRIRuby中我可以这样做:deftransferinternal_server=self.init_serverpid=forkdointernal_server.runend#Maketheserverprocessrunindependently.Process.detach(pid)internal_client=self.init_client#Dootherstuffwithconnectingtointernal_server...internal_client.post('somedata')ensure#KillserverProcess.kill('KILL',
ruby - 通过 erb 模板输出 ruby 数组 - 2
我正在使用puppet为ruby程序提供一组常量。我需要提供一组主机名，我的程序将对其进行迭代。在我之前使用的bash脚本中，我只是将它作为一个puppet变量hosts=>"host1,host2"我将其提供给bash脚本作为HOSTS=显然这对ruby不太适用——我需要它的格式hosts=["host1","host2"]自从phosts和putsmy_array.inspect提供输出["host1","host2"]我希望使用其中之一。不幸的是，我终其一生都无法弄清楚如何让它发挥作用。我尝试了以下各项:我发现某处他们指出我需要在函数调用前放置“function_”……这
ruby - 如何使用 Ruby aws/s3 Gem 生成安全 URL 以从 s3 下载文件 - 2
我正在编写一个小脚本来定位aws存储桶中的特定文件，并创建一个临时验证的url以发送给同事。(理想情况下，这将创建类似于在控制台上右键单击存储桶中的文件并复制链接地址的结果)。我研究过回形针，它似乎不符合这个标准，但我可能只是不知道它的全部功能。我尝试了以下方法:defauthenticated_url(file_name,bucket)AWS::S3::S3Object.url_for(file_name,bucket,:secure=>true,:expires=>20*60)end产生这种类型的结果:...-1.amazonaws.com/file_path/file.zip.A
ruby-on-rails - 跳过状态机方法的所有验证 - 2
当我的预订模型通过rake任务在状态机上转换时，我试图找出如何跳过对ActiveRecord对象的特定实例的验证。我想在reservation.close时跳过所有验证!叫做。希望调用reservation.close!(:validate=>false)之类的东西。仅供引用，我们正在使用https://github.com/pluginaweek/state_machine用于状态机。这是我的预订模型的示例。classReservation["requested","negotiating","approved"])}state_machine:initial=>'requested
ruby - Nokogiri 剥离所有属性 - 2
我有这个html标记:我想得到这个:我如何使用Nokogiri做到这一点？最佳答案 require'nokogiri'doc=Nokogiri::HTML('')您可以通过xpath删除所有属性:doc.xpath('//@*').remove或者，如果您需要做一些更复杂的事情，有时使用以下方法遍历所有元素会更容易:doc.traversedo|node|node.keys.eachdo|attribute|node.deleteattributeendend 关于ruby-Nokog
ruby - 获取模块中定义的所有常量的值 - 2
我想获取模块中定义的所有常量的值:moduleLettersA='apple'.freezeB='boy'.freezeendconstants给了我常量的名字:Letters.constants(false)#=>[:A,:B]如何获取它们的值的数组，即["apple","boy"]？最佳答案为了做到这一点，请使用mapLetters.constants(false).map&Letters.method(:const_get)这将返回["a","b"]第二种方式:Letters.constants(false).map{|c

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

有关c++ - 从模板包生成所有大小为 N 的子包的更多相关文章

随机推荐