列出所有排列方式

Question

我试图列出所有的三个字母排列组合，下面是我的代码 -

  window.permute = function(){
    var alphabet = "abcdefghijklmnopqrstuvwxyz";
    var searchTerm ="aaa";
    var position = 2; 
    changeString(searchTerm, position); 
}

window.changeString = function(searchTerm, position){
    if (position <0){
        alert(newString);

    return; 
    }
    var alphabet = "abcdefghijklmnopqrstuvwxyz"
    for (j=0; j < 26;j++){
        var newString = searchTerm.substr(0, position) + alphabet[j] + searchTerm.substr(position+1);
        var newPosition = position -1; 
        changeString(newString,newPosition);
    }
    return;
}

它不能正常工作，我不确定原因- 有人可以帮忙吗？

- scubadiver

---

你能提供更多的上下文吗？ - Kris Krause

目前，我只能改变第一个字母 - 我需要所有的排列。 - scubadiver

这个可能重要，也可能不重要，但请注意，你正在尝试生成 26!/(26-3)! = 15,600 个字符串。 - nwellcome

Answer 1

var permutate = (function() {
    var results = [];    
    function doPermute(input, output, used, size, level) {        
        if (size == level) {
            var word = output.join('');
            results.push(word);
            return;
        } 
        level++;
        for (var i = 0; i < input.length; i++) {
            if (used[i]) {
                continue;
            }            
            used[i] = true;
            output.push(input[i]);
            doPermute(input, output, used, size, level);
            used[i] = false;
            output.pop();
        }
    }

    return {
        getPermutations: function(input, size) {
            var chars = input.split('');
            var output = [];
            var used = new Array(chars.length);      
            doPermute(chars, output, used, size, 0);        
            return results;    
        }
    }
})();

欲了解更多信息，请访问http://jinwolf.tumblr.com/post/26476479113/draw-something-cheat。 要查看一个工作示例，请查看此jsfiddle http://jsfiddle.net/jinwolf/Ek4N5/31/

- Jin

Answer 2

alert(newString);

newString在那里没有被定义。相反，您应该使用传递的参数：

alert(searchTerm);

---

编辑：我不太确定你的方法。它似乎过于复杂了。这个方法似乎可以工作。我知道你更喜欢自己的代码能够运行，但也许这可以帮助你解决问题。我不太理解你的substr部分。

http://jsfiddle.net/NUG2A/2/

var alphabet = "abc"; // shortened to save time

function permute(text) {
    if(text.length === 3) { // if length is 3, combination is valid; alert
        console.log(text); // or alert
    } else {
        var newalphabet = alphabet.split("").filter(function(v) {
            return text.indexOf(v) === -1;
        }); // construct a new alphabet of characters that are not used yet
            // because each letter may only occur once in each combination

        for(var i = 0; i < newalphabet.length; i++) {
            permute(text + newalphabet[i]); // call permute with current text + new
                                            // letter from filtered alphabet
        }
    }
}

permute("");

这将导致调用以下内容：

permute("");
permute("a");
permute("ab");
permute("abc"); // alert
permute("ac");
permute("acb"); // alert
permute("b");
// ...

- pimvdb

---

面掌 - 即使如此，我只改变了第一个字母。 - scubadiver

这意味着其中一个返回并没有按照我的意愿执行。 - scubadiver

你所产生的是一个幂集，而非排列。 - wsanville

@pimvdb：如果他需要幂集，那么只有微不足道的2^26 = 67,108,864个字符串... - nwellcome

Answer 3

从你的问题中，我不确定你是否指的是“排列”，因为通常排列不包括重复元素，而你似乎想包括“aaa”。

这里有几个算法可以列出排列，你可以去查看。如果你确实需要重复，那么pimvdb已经帮你解决了。

编辑：所以你知道运行时间是多少：

• 有重复（aaa，aab，...）：n^k = 26^3 = 17,576
• 没有重复（abc，bac，...）：n!/(n-k)! = 26!/(26-3)! = 15,600

- nwellcome

---

也不是组合问题。一个集合的组合是指无论顺序如何，取出所有排列的集合，而不是从带有替换的集合中取出排列。 - Jimmy

没错，我滥用了定义，现在抛弃了那个方法，只是使用了带有和不带有重复的排列。 - nwellcome

Answer 4

for (j=0; j < 26;j++){

应该是

for (var j=0; j<26; j++) {

没有声明的话，j 就是一个全局变量，所以只需迭代一次就会到达 26 然后所有循环都终止。

- Jimmy

---

等一下-那有什么区别吗？为什么控制台没有出现错误？ - scubadiver

@scubadiver 哦，你不知道自动全局声明的影响是多么微妙。 - Liviu T.

Answer 5

对于排列问题，像pimvd展示的递归算法总是很好，但不要忘记当N很小时，你也可以用for循环来暴力解决它：

for(int x1=0; x1 < 26; x1++)
for(int x2=0; x2 < 26; x2++)
for(int x3=0; x3 < 26; x3++){
    //do something with x1, x2, x3
}

- hugomg

Answer 6

在C＃中：

    void DoPermuation(string s)
    {
        var pool = new HashSet<string>();
        //Permute("", , pool);
        pool = Permute(new List<char>(s));
        int i = 0;
        foreach (var item in pool) Console.WriteLine("{0:D2}: {1}", ++i, item);      
    }

    HashSet<string> Permute(List<char> range)
    {
        if (range.Count == 1) return new HashSet<string>(new string[] { range[0].ToString() });

        var pool = new HashSet<string>();
        foreach (var c in range)
        {             
            var list = new List<char>(range);
            list.Remove(c);
            foreach (var item in Permute(list)) pool.Add(c + item);                
        }

        return pool;
    }

- user950851

---

假设问题需要使用C#进行回答，那么这应该在问题中有所体现。 - Mark Parnell