组合和置换算法(递归)

本文介绍了组合和置换算法(递归)的处理方法，对大家解决问题具有一定的参考价值，需要的朋友们下面随着小编来一起学习吧！

问题描述

我正在做Java作业，我很沮丧.

问题是:

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

显示所有可能的方式，当顺序"不重要且不允许重复时，您可以填充Y信封. hint: X! / (( X-Y)! * Y!)
显示所有可能的方式，以在订单很重要且允许重复时填充Y信封hint: X^Y
显示所有可能的方式，以在顺序"很重要且不允许重复时填充Y信封.提示:X! / (X – Y)!
显示所有可能的方式，当顺序"不重要且允许重复时，您可以填充Y信封:(X + Y – 1)! / (Y! * (X – 1)!)

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

我不希望任何人发布任何代码，也不希望有人为我解决此问题！我希望一旦完成第一部分(问题a)，它将能够解锁防洪闸门.有人可以在制定伪代码算法方面提供一些指导吗，据我所知:

用增加的卡片依次填充Y信封(ex: 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 {
        }
    }

}

任何人都可以指出我的缺点吗?

解决方案

您的老师希望您使用递归.

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

对于给定的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为空，依此类推). /p>

使用Set而不是List，因为您要确保没有重复.

I am working on a Java assignment and I am absolutely stumped.

The question is:

Write a function using Recursion to do the following: You have X different cards. You have only Y envelopes. Y is less than or equal to X. For any given values of X and Y,

display all possible ways you can fill the Y envelopes when Order is not important and Repetition is not allowed. hint: X! / (( X-Y)! * Y!)
display all possible ways you can fill the Y envelopes when Order is important and Repetition is allowed hint: X^Y
display all possible ways you can fill the Y envelopes when Order is important and Repetition is not allowed hint: X! / (X – Y)!
display all possible ways you can fill the Y envelopes when Order is not important and Repetition is allowed hint: (X + Y – 1)! / (Y! * (X – 1)!)

for example, under case (1), if X = {J, Q, K, A) and Y = 3, then the output should be: {J,Q,K} {J,Q,A} {J,K,A} {Q,K,A}.

I do not want anyone to post any code and I'm not looking for anyone to solve this for me! I am hoping that once I get the first part (question a) done that it'll unlock the flood gates. Can someone please offer some guidance in working out the pseudocode algorithm, this is as far as I can get:

Fill the Y envelopes in order with increasing cards (ex: X=5, Y=3) {1, 2, 3}.Replace in the highest envelope with the highest card {1, 2, 5}, decrementing until we find it's original value {1, 2, 4}.Do this for every envelope from highest to lowest (where the number is not already in use) {1, 5, 4} {1, 3, 4} {5, 3, 4} {2, 3, 4}.

That's as far as I get before it falls apart because this is missing 3 combinations {1, 5, 3} {3, 4, 5} {5, 3, 2}.

I would appreciate any help at all and as it's an assignment I'll re-iterate, I don't want the solution, I want help in coming to the solution on my own.Thank you!

EDIT: I've tried all 3 solutions outlined and I'm still not getting it. This is what I'm getting so far:

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

}

Can anyone help point out my flaw?

解决方案

Your teacher wants you to use recursion.

What is the answer, for a given X, if Y is zero? Solve this using your code.

What is the answer, for a given X, if I give you the solution for Y = some random whole number n for free, what is the solution for n + 1? In other words, if I tell you that the solution for X = 5, Y = 3 is { { ... }, { ... }, ... }, can you easily figure out the solution for X = 5, Y = 3 + 1 = 4?

Here is an example for a totally different problem:

Lets say you know the first previous two Fibonacci numbers are 1 and 1. Then finding the next one is easy, right? it's 2. Now lets say you know the previous two are 1 and 2, the next one is 3! If the previous two are 2 and 3, the next one is 5!

Some pseudocode:

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

See how fibHelp calls itself? That's recursion! Just make sure you have a stop condition (my if statement).

For your specific problem, don't return void, instead have comboNoRep return a Set<Set<Integer>>. When y=0, return a Set with one element (an empty Set). y=1, return a Set that builds a bunch of Sets by adding one element to each set in the larger set (in the case of y=1 that Set is empty, and so forth).

Use Set and not List because you want to make sure that you don't have duplicates.

这篇关于组合和置换算法(递归)的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持！