Перестановки списков

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

Это не работает, и я не уверен, почему - кто-нибудь может помочь?

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/

Answer 2

Я не уверен в вашем вопросе, что вы имеете в виду "перестановки", потому что обычно перестановки не включают повторяющиеся элементы, если кажется, что вы хотите включить "aaa".

Вот несколько алгоритмов для перечисления перестановок, которые вы можете проверить. Если окажется, что вы хотите повторений, похоже, что pimvdb вас охватил.

Редактировать: Итак, вы знаете, что вы получаете во время выполнения:

• С повторением (ааа, ааа, ...): n ^ k = 26 ^ 3 = 17,576
• Без повторений (abc, bac, ...): n! / (N-k)! = 26! / (26-3)! = 15 600

Answer 3

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");
// ...

Answer 4

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

Answer 5

Для перестановок рекурсивный алгоритм, как показал pimvd, всегда хорош, но не забывайте, что вы можете просто перебрать его с помощью циклов for, когда N мало:

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
}

Answer 6

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

должно быть

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

Без объявления j является глобальной переменной, поэтому для достижения 26 требуется всего одна итерация, а затем все циклы завершаются.