首页 文章

打印子集的最佳递归算法

提问于
浏览 次
0

我正在尝试找到一个好的递归算法来打印出一组的子集 . 例如

大小5：给出 the set {1,2,3,4,5} and the subsets off length 3 gives this output:

{5,4,3}
{5,4,2}
{5,4,1}
{5,3,2}
{5,3,1}
{5,2,1}
{4,3,2}
{4,3,1}
{4,2,1}
{3,2,1}

我尝试了很多东西，但它不起作用 . 在互联网上所有的例子都是集算法，但我想写自己的，用于学习目的 .

有人可以帮我吗？

亲切的问候，

java algorithm recursion

3 回答

  • 1

    最后它有效：

    public static void Dvz(String s, int x, int y){
    int i;
    if(y > 0)
      for(i = x; i >= y; i--)
      Dvz(s+i, i-1, y-1);
    else
      System.out.println(s);

  }
    回复于
  • 1

    几年前我遇到了一个非常类似的问题 . 我最终实现这个的方式：
    1.将每个集存储为成员ID的排序数组（没有2个ID是相同的）
    2.用于迭代给定大小的子集N以原始集合的前N个元素开始
    3.到达下一个子集，你实现了一种"clockwork"机制 - 取你子集的最后一个（最高id）成员，并用超集中的邻居替换它（下一个更高的id） .
    4.如果超集中没有这样的高邻居，则递增子集的下一个较低成员，然后将原始最高成员设置为之后的下一个成员 .

    步骤3和4是递归的 .

    迭代{1,2,3,4,5}的所有三元组的示例结果序列：

    {1,2,3} - 3 lowest memebers
{1,2,4} - "increment" 3 to 4
{1,2,5} - 4 to 5
{1,3,4} - couldnt "increment" 5, so incremented 2-->3 and picked then next one as 3rd
{1,3,5} - 4-->5
{1,4,5} - couldnt increment 5 ...
{2,3,4} - couldnt increment 5, couldnt increment 4, incremented 1-->2 
{2,3,5}

    等等

    它比mark的提议更复杂，但占用更少的内存和堆栈空间 . 它也是“可重启的” - 这意味着你可以将任何子集传递到算法中，它将为你提供“下一个”子集 .

    回复于
  • 1

    要构造递归算法，您可以注意到来自{1,2,3,4,5}的每个长度为3的子集：

    • 包含{2,3,4,5}中的元素"1"和2个元素 .

    • 不包含{2,3,4,5}中的元素"1"和3个元素 .

    这两种情况中的每一种都可以通过递归调用函数来实现 .

    回复于

相关问题