草庐IT

c++ - N选K、K-N、K-2N等，递归中递归

coder 2024-02-12 原文

我知道如何使用递归来生成所有可能的组合，即 N 选择 K。但是如何创建所有可能的 N/K 组 K？ N 当然总是可以被 K 整除。澄清一下:例如，如果 N 是 20，K 是 4，那么我想生成所有可能的五组四。如果，比方说，N 包含 1,2,3...20 而 K 是 4，那么这样的分组是 {1,2,3,4},{5,6,7,8},{9,10 ,11,12},{13,14,15,16},{17,18,19,20}。假设N比较小，递归可行

我觉得这是一个递归中的递归问题，因为生成所有可能的单组四(又名 N 选择 K)需要递归，然后生成下一组四变成 N - 4 选择 K ，然后下一个 N - 8 选择 K，等等。但是我在实现这个时遇到了问题...有什么帮助吗？

最佳答案

术语:你要的全是partitions将一组 N 个元素分成大小为 K 的部分。有 n!/((k!)^(n/k) (n/k)!) 这样的分区(参见 answer on math.SE )。

为了避免过度生成，让我们为每个决定一个“规范形式” partition: 比方说就是把每一部分按递增的顺序写出来，然后 按照最小元素的递增顺序编写这些部分。

现在您可以将分区的生成可视化为丢球的过程 编号为 1 到 N，一个接一个，放入 N/K 个 bins 中。每个箱子的约束 (部分)必须按递增顺序自动满足(当然 您应该按照插入元素的顺序“阅读”每个容器)，并且 如果我们确保不跳过空箱，则零件的约束得到满足 在填充下一个之前。

现在将其转化为代码。让我们将我们的分区(或一堆 bin)建模为 vector 的 vector 。

#include <iostream>
#include <vector>
#include <cassert>

std::vector< std::vector<int> > partition;
int N, K;
int num_partitions_found = 0;

void OutputPartition();

一般来说，当递归生成结构时(或编写任何递归 算法)，你的递归函数被赋予一个特定的“状态”，并尝试 扩展该状态的每种增量方式。在不同的选择之间，只是 确保将状态恢复到您获得的状态。

因此，让我们将递归函数编写为一个状态，其中最多 n-1 的球已放入箱中，并通过放置球 n在所有可能的地方。

void GeneratePartitions(int n) {
  // When we've placed all N elements, output and stop.
  if (n == N + 1) {
    OutputPartition();
    return;
  }
  // Place ball n into each allowed bin.
  for (int i = 0; i < N / K; ++i) {
    // Cannot place into a full bin
    if (partition[i].size() == K) continue;
    // Cannot skip an empty bin
    if (i > 0 && partition[i-1].empty()) break;
    // Place the ball here: extending the state
    partition[i].push_back(n);
    // How to extend the new state is left to the recursive call
    GeneratePartitions(n + 1);
    // Make sure you restore state after each recursive call!
    partition[i].pop_back();
  }
}

这就是递归的核心。该程序的其余部分是脚手架。

void OutputPartition() {
  assert(partition.size() == N/K);
  ++num_partitions_found;
  for (int i = 0; i < N/K; ++i) {
    assert(partition[i].size() == K);
    std::cout << "{";
    for (int j = 0; j < K; ++j) {
      std::cout << partition[i][j] << (j == K - 1 ? "}" : ", ");
    }
    if (i < N/K - 1) std::cout << ", ";
  }
  std::cout << std::endl;
}

int main() {
  std::cin >> N >> K;
  assert(N % K == 0);
  partition.resize(N / K);
  GeneratePartitions(1);
  std::cout << num_partitions_found << " found" << std::endl;
}

注意:这篇文章是literate program : 如果您将代码片段放在一起，您就有了一个有效的工作程序。

或者，如果您想试用该程序(查看它的运行速度等)，另一个版本是 here on github : 它不使用全局变量，对分区使用普通数组(更快)，并仅为小 N 打印所有找到的分区(编辑代码以更改它)。

回到您的问题，我们发现通过仔细考虑问题一段时间，您可以避免使用不同类型的递归。即使你这样做了，编写递归程序的一般方法仍然是:编写一个接受状态的递归函数，以所有可能的方式将其扩展一步(将这些状态的进一步扩展传递给递归调用)，然后清理直至其原始状态。 (有时，当状态很小时，您不必进行任何清理 — 您可以通过函数调用传递状态 — 但有时让递归调用共享状态会更干净。)

关于c++ - N选K、K-N、K-2N等，递归中递归，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/21105154/

amp43partitionltsectionc++calgorithmrecursion

有关c++ - N选K、K-N、K-2N等，递归中递归的更多相关文章

  1. ruby-on-rails - 如何优雅地重启 thin + nginx？ - 2

    我的瘦服务器配置了nginx，我的ROR应用程序正在它们上运行。在我发布代码更新时运行thinrestart会给我的应用程序带来一些停机时间。我试图弄清楚如何优雅地重启正在运行的Thin实例，但找不到好的解决方案。有没有人能做到这一点？ 最佳答案 #Restartjustthethinserverdescribedbythatconfigsudothin-C/etc/thin/mysite.ymlrestartNginx将继续运行并代理请求。如果您将Nginx设置为使用多个上游服务器，例如server{listen80;server

  2. ruby - 使用 `+=` 和 `send` 方法 - 2

    如何将send与+=一起使用？a=20;a.send"+=",10undefinedmethod`+='for20:Fixnuma=20;a+=10=>30 最佳答案 恐怕你不能。+=不是方法，而是语法糖。参见http://www.ruby-doc.org/docs/ProgrammingRuby/html/tut_expressions.html它说Incommonwithmanyotherlanguages,Rubyhasasyntacticshortcut:a=a+2maybewrittenasa+=2.你能做的最好的事情是:

  3. ruby - 如何计算 Liquid 中的变量 +1 - 2

    我对如何计算通过{%assignvar=0%}赋值的变量加一完全感到困惑。这应该是最简单的任务。到目前为止，这是我尝试过的:{%assignamount=0%}{%forvariantinproduct.variants%}{%assignamount=amount+1%}{%endfor%}Amount:{{amount}}结果总是0。也许我忽略了一些明显的东西。也许有更好的方法。我想要存档的只是获取运行的迭代次数。 最佳答案 因为{{incrementamount}}将输出您的变量值并且不会影响{%assign%}定义的变量，我

  4. arrays - Ruby 数组 += vs 推送 - 2

    我有一个数组数组，想将元素附加到子数组。+=做我想做的，但我想了解为什么push不做。我期望的行为(并与+=一起工作):b=Array.new(3,[])b[0]+=["apple"]b[1]+=["orange"]b[2]+=["frog"]b=>[["苹果"],["橙子"],["Frog"]]通过推送，我将推送的元素附加到每个子数组(为什么？):a=Array.new(3,[])a[0].push("apple")a[1].push("orange")a[2].push("frog")a=>[[“苹果”、“橙子”、“Frog”]、[“苹果”、“橙子”、“Frog”]、[“苹果”、“

  5. ruby - 递归地将所有数字字符串转换为 Ruby 哈希中的整数 - 2

    我有一个随机大小的散列，它可能有类似"100"的值，我想将其转换为整数。我知道我可以使用value.to_iifvalue.to_i.to_s==value来做到这一点，但我不确定我将如何在我的散列中递归地做到这一点，考虑到一个值可以是一个字符串，或一个数组(哈希或字符串)，或另一个哈希。 最佳答案 这是一个非常简单的递归实现(尽管必须同时处理数组和散列会增加一些技巧)。deffixnumifyobjifobj.respond_to?:to_i#IfwecancastittoaFixnum,doit.obj.to_ielsifobj

  6. Ruby:标准递归模式 - 2

    我经常迷上ruby​​的一件事是递归模式。例如，假设我有一个数组，它可能包含无限深度的数组作为元素。所以，例如:my_array=[1,[2,3,[4,5,[6,7]]]]我想创建一个方法，可以将数组展平为[1,2,3,4,5,6,7]。我知道.flatten可以完成这项工作，但这个问题是作为我经常遇到的递归问题的一个例子-因此我试图找到一个更可重用的解决方案。简而言之-我猜这种事情有一个标准模式，但我想不出任何特别优雅的东西。任何想法表示赞赏 最佳答案 递归是一种方法，它不依赖于语言。您在编写算法时要考虑两种情况:再次调用函数的情

  7. += 的 Ruby 方法 - 2

    有没有办法让Ruby能够做这样的事情？classPlane@moved=0@x=0defx+=(v)#thisiserror@x+=v@moved+=1enddefto_s"moved#{@moved}times,currentxis#{@x}"endendplane=Plane.newplane.x+=5plane.x+=10putsplane.to_s#moved2times,currentxis15 最佳答案 您不能在Ruby中覆盖复合赋值运算符。任务在内部处理。您应该覆盖+，而不是+=。plane.a+=b与plane.a=

  8. ruby - Sinatra + Heroku + Datamapper 使用 dm-sqlite-adapter 部署问题 - 2

    出于某种原因，heroku尝试要求dm-sqlite-adapter，即使它应该在这里使用Postgres。请注意，这发生在我打开任何URL时-而不是在gitpush本身期间。我构建了一个默认的Facebook应用程序。gem文件:source:gemcuttergem"foreman"gem"sinatra"gem"mogli"gem"json"gem"httparty"gem"thin"gem"data_mapper"gem"heroku"group:productiondogem"pg"gem"dm-postgres-adapter"endgroup:development,:t

  9. ruby - Ruby 中字符串运算符 + 和 << 的区别 - 2

    我是Ruby和这个网站的新手。下面两个函数是不同的，一个在函数外修改变量，一个不修改。defm1(x)x我想确保我理解正确-当调用m1时，对str的引用被复制并传递给将其视为x的函数。运算符当调用m2时，对str的引用被复制并传递给将其视为x的函数。运算符+创建一个新字符串，赋值x=x+"4"只是将x重定向到新字符串，而原始str变量保持不变。对吧？谢谢 最佳答案 String#+::str+other_str→new_strConcatenation—ReturnsanewStringcontainingother_strconc

  10. ruby - 为什么我用递归得到 "stack level too deep"？ - 2

    我有这个ruby代码:defget_sumnreturn0ifn似乎正在为999之前的值工作。当我尝试9999时，它给了我这个:stackleveltoodeep(SystemStackError)所以，我添加了这个:RubyVM::InstructionSequence.compile_option={:tailcall_optimization=>true,:trace_instruction=>false}但什么也没发生。我的ruby版本是:ruby1.9.3p392(2013-02-22revision39386)[x86_64-darwin12.2.1]我还增加了机器的堆栈大

随机推荐