java - 组合和排列算法(递归)

Question

我正在做一项 Java 作业，但我完全被难住了。

问题是:

使用递归编写一个函数来执行以下操作:您有 X 张不同的卡片。您只有 Y 个信封。 Y 小于或等于 X。对于任何给定的 X 和 Y 值，

1. 显示当顺序不重要且不允许重复时填充 Y 信封的所有可能方法。 提示:X!/((X-Y)!* Y!)

2. 当顺序很重要且允许重复时，显示填充 Y 信封的所有可能方式提示:X^Y

3. 当顺序很重要且不允许重复时，显示填充 Y 信封的所有可能方式提示:X!/(X – Y)!

4. 显示当顺序不重要且允许重复时填充 Y 信封的所有可能方式提示:(X + Y – 1)!/(Y! * (X – 1)!)

例如，在情况 (1) 下，如果 X = {J, Q, K, A) 且 Y = 3，则输出应为:{J,Q,K} {J,Q,A} {J,K,A} {Q,K,A}。

我不想让任何人发布任何代码，我也不想找任何人来帮我解决这个问题!我希望一旦我完成第一部分(问题a)，它就会打开防洪闸门。有人可以提供一些关于制定伪代码算法的指导吗，这是我所能得到的:

按照递增的卡片顺序填充 Y 个信封(例如:X=5、Y=3){1、2、3}。 将最高的信封替换为最高的卡片 {1, 2, 5}，递减，直到我们找到它的原始值 {1, 2, 4}。 对从最高到最低的每个信封(其中编号尚未使用)执行此操作{1, 5, 4} {1, 3, 4} {5, 3, 4} {2, 3, 4}。

这就是我在它崩溃之前得到的信息，因为它缺少 3 个组合 {1, 5, 3} {3, 4, 5} {5, 3, 2}。

我非常感谢任何帮助，因为这是一项任务，我将重申，我不需要解决方案，我需要帮助自己找到解决方案。 谢谢!

编辑:我已经尝试了列出的所有 3 个解决方案，但仍然没有得到它。这是我到目前为止所得到的:

public static void comboNoRep(String[] a, int y, boolean[] used)
{

    if(y == 0) {
        // found a valid solution.
        System.out.println(result);
    }

    for(int i=0; i<a.length; i++) {
        if(!used[i]) {
            used[i] = true;
            result = result + a[i];
            comboNoRep(a, y - 1, used);
            result = result + " ";
            used[i] = false;
        }
        else {
        }
    }

}

谁能帮我指出我的缺陷吗？

Answer 1

你的老师希望你使用递归。

对于给定的 X，如果 Y 为零，答案是什么？使用您的代码解决此问题。

对于给定的 X，如果我免费给出 Y = 某个随机整数 n 的解，那么 n + 1 的解是什么？换句话说，如果我告诉你 X = 5, Y = 3 的解是 { { ... }, { ... }, ... }，你能轻松算出 X = 5, Y = 3 + 1 = 4 的解吗？

这是一个完全不同问题的示例:

假设您知道前两个斐波那契数是 1 和 1。那么找到下一个斐波那契数就很容易了，对吧？是 2。现在假设您知道前两个是 1 和 2，下一个是 3!如果前两个是2和3，那么下一个就是5!

一些伪代码:

public int fib(int stop) {
     if (stop < 2) return 1;
     return fibHelp(stop - 2, 1, 1);
}

public int fibHelp(int stop, int oneBelow, int twoBelow) {
   if (stop == 0) return oneBelow;

   return fibHelp(stop - 1, oneBelow + twoBelow, oneBelow);
}

看看 fibHelp 如何调用自身？这就是递归!只需确保您有一个停止条件(我的 if 语句)。

对于您的具体问题，请勿返回 void ，而是 comboNoRep返回 Set<Set<Integer>> 。当y=0 ，返回 Set包含一个元素(空 Set )。 y=1 ，返回 Set构建了一堆 Set通过向较大集合中的每个集合添加一个元素(在 y=1 的情况下，Set 为空，依此类推)。

使用Set而不是List因为您想确保没有重复项。