0

我有一个 javascript 应用程序,我需要在其中运行数字 0 到 6 的每个可能组合的测试,而不复制组合中的任何数字。

所以:0123456、0123465、0123546、0123564 ...

(但是,例如,0123455,不应该包括在内,因为 5 是重复的)

我已经迭代地完成了它:

function testAllCombinations(){
    for(var i = 0; i < 7; i++){
        for(var j = 0; j < 7; j++){
            if(j == i)
                continue;
            for(var k = 0; k < 7; k++){
                if(k == j || k == i)
                    continue;
                for(var l = 0; l < 7; l++){
                    if(l == k || l == j || l == i)
                        continue;
                    for(var m = 0; m < 7; m++){
                        if(m == l || m == k || m == j || m == i)
                            continue;
                        for(var n = 0; n < 7; n++){
                            if(n == m || n == l || n == k || n == j || n == i)
                                continue;
                            for(var o = 0; o < 7; o++){
                                if(o == n || o == m || o == l || o == l || o == j || o == i)
                                    continue;

                                runTest(i, j, k, l, m, n, o);
                            }
                        }
                    }
                }
            }
        }
    }
}

它工作正常,但我想递归地做,而且我很难构建算法。

谁能给我一些方向?

提前致谢。

4

2 回答 2

4

这看起来像是关于递归的一般问题。

递归算法可以分为两部分,基本情况和递归情况。首先,找出基本情况,这会导致不需要递归的微不足道的结果。可以有多个输入导致基本情况。从最琐碎的输入开始,然后从那里扩展。很快,您就会发现递归情况,它们是递归函数的关键因素。您会发现所有递归案例都可以使用由先前案例(包括基本案例)组成的类似模式来解决。

所以对于这个问题,假设用户可以输入一个字符串,并且您想打印字符串中的所有字符组合,我们将此调用称为 f(s)。如果用户输入长度为 0 或 1 的字符串,只需返回提供的字符串,因为只有一种组合可用。这里没什么特别的。这是基本情况。

如果用户输入长度为 2 的字符串(例如“01”),则很明显可能的组合是“01”和“10”。你是怎么得到这个答案的?
请注意,“01”=“0”+“1”和“10”=“1”+“0”。
Iow,我们遍历每个数字并将其与 f(s) 的结果相结合,其中 s = 剩余数字。
IE。"01" = "0" + f("1") 和 "10" = "1" + f("0")。
我们已经知道当长度为 1 时如何解决这个问题,所以现在我们知道当输入长度为 2 时如何解决这个问题。

现在,如果输入长度为 3(例如“012”),您知道答案是“012”、“021”、“102”、“120”、“201”、“210”。
请注意,“012”、“021”=“0”+“12”、“0”+“21”和“102”、“120”=“1”+“02”、“1”+“20”,和 "201", "210" = "2" + "01", "2" + "10" Iow,我们循环遍历每个数字并将其与 f(s) 的结果相结合,其中 s = 剩余数字。听起来有点熟?
IE。"012", "021" = "0" + f("12") 和 "102", "120" = "1" + f("02") 和 "201", "210" = "2" + F(”

你现在看到模式了吗?在每个级别(输入的长度),我们应用相同的原则,因此可以在问题的子集上一遍又一遍地使用相同的代码,最终将它们组合在一起形成最终答案。这就是递归如此优雅的原因。

请注意,当输入的长度为 4 时,我们可以再次应用相同的模式。
IE。f("0123") = "0" + f("123"), "1" + f("023"), "2" + f("013"), "3" + f("012") ,并且我们已经知道如何在长度为 3 时解决这个问题,所以现在我们知道如何解决输入长度为 4 时的问题。

我可以继续,也可以用代码写出解决方案,但毫无疑问有更好的资源来学习递归,所以我会让你自己寻找它们。但是,(我希望)我的解释足以让您朝着正确的方向思考,甚至​​可能无需阅读任何其他资源即可解决您的问题。

请记住,解决递归的关键是从最简单的情况开始,然后从那里开始构建。

于 2013-09-14T06:20:02.130 回答
0

您可能想查看以下按字典顺序生成下一个排列的算法。

在传递给生成算法之前,初始数组必须按升序排序。

以下算法在给定排列之后按字典顺序生成下一个排列。它就地改变了给定的排列。

  1. 找到最大的索引k,使得a[k] < a[k + 1]。如果不存在这样的索引,则排列是最后一个排列。
  2. 找到最大的索引l,使得a[k] < a[l]
  3. a[k]将 的值与的值交换a[l]
  4. 颠倒顺序,a[k + 1]直到并包括最后一个元素a[n]
于 2013-09-14T05:52:39.447 回答