Перестановка Javascript

Итак, у меня есть этот код сейчас, и на входе у меня есть в порядке возрастания буквы моего имени «ahimrsu». Мне нужно показать правильный номер для «марихуа» из всех комбинаций, которые должны быть 2170. На данный момент это только показывает ahimrsu, ahimrus, ahimsru, ahimsur, ahimurs, ahimusr, ahirmus, ahirmsu .... и т. Д. Как я могу сделать это?Перестановка Javascript

<!DOCTYPE HTML> 

<html> 
<head> 
<!--Script Function Start Here--> 
<script type="text/javascript"> 
     function perms(data) { 
    if (!(data instanceof Array)) { 
     throw new TypeError("input data must be an Array"); 
    } 

    data = data.slice(); // make a copy 
    var permutations = [], 
     stack = []; 

    function doPerm() { 
     if (data.length == 0) { 
      permutations.push(stack.slice()); 
     } 
     for (var i = 0; i < data.length; i++) { 
      var x = data.splice(i, 1); 
      stack.push(x); 
      doPerm(); 
      stack.pop(); 
      data.splice(i, 0, x); 
     } 
    } 

    doPerm(); 
    return permutations; 
} 

var input = "ahimrsu".split(''); 
var result = perms(input); 
for (var i = 0; i < result.length; i++) { 
    result[i] = result[i].join(''); 
} 
console.log(result); 
</script> 
<!--Header start here--> 
</head> 
<body> 
<!--Script Result--> 
<script type="text/javascript"> 
     document.write(result); 
</script> 

</body> 
</html>

источник

2014-10-22 Markus Hayner

Алгоритма строки перестановки будет рекурсивным (простейшие). – dfsq

Он покажет все комбинации этих букв. –

Дайте мне несколько минут, чтобы закодировать его. – dfsq

Это мое решение из следующего ответа: https://stackoverflow.com/a/18879232/783743

var permute = (function() { 
    return permute; 

    function permute(list) { 
     return list.length ? 
      list.reduce(permutate, []) : 
      [[]]; 
    } 

    function permutate(permutations, item, index, list) { 
     return permutations.concat(permute(
      list.slice(0, index).concat(
      list.slice(index + 1))) 
      .map(concat, [item])); 
    } 

    function concat(list) { 
     return this.concat(list); 
    } 
}());

Вы можете использовать функцию permute для нахождения всех перестановок массива:

var array = "ahimrsu".split(""); 
var permutations = permute(array).map(join); 
var index = permutations.indexOf("maruish"); 

function join(array) { 
    return array.join(""); 
}

Алгоритм очень прост для понимания:

Мы хотим, чтобы функция permute типа [a] -> [[a]] (т.е. заданный список a s, он возвращает список перестановок ввода).
Учитывая пустой список ([]), вход представляет собой пустой список перестановок ([[]]).
В противном случае для каждого элемента:
1. Мы удаляем элемент из списка.
2. Мы рекурсивно находим перестановки остальных элементов.
3. Мы добавим элемент, который мы удалили в начало каждой перестановки.

Например, предположим, что мы хотим найти перестановку массива [1, 2, 3]:

1. permute([1, 2, 3]) === [1, 2, 3].reduce(permutate, []) 
    1. permutate([], 1, 0, [1, 2, 3]) 
     1. permute([2, 3]) === [2, 3].reduce(permutate, []) 
      1. permutate([], 2, 0, [2, 3]) 
       1. permute([3]) === [3].reduce(permutate, []) 
        1. permutate([], 3, 0, [3]) 
         1. permute([]) === [[]] 
         2. [[]].map(concat, [3]) === [[3]] 
         3. [].concat([[3]]) === [[3]] 
       2. [[3]].map(concat, [2]) === [[2, 3]] 
       3. [].concat([[2, 3]]) === [[2, 3]] 
      2. permutate([[2, 3]], 3, 1, [2, 3]) 
       1. permute([2]) === [2].reduce(permutate, []) 
        1. permutate([], 2, 0, [2]) 
         1. permute([]) === [[]] 
         2. [[]].map(concat, [2]) === [[2]] 
         3. [].concat([[2]]) === [[2]] 
       2. [[2]].map(concat, [3]) === [[3, 2]] 
       3. [[2, 3]].concat([[3, 2]]) === [[2, 3], [3, 2]] 
     2. [[2, 3], [3, 2]].map(concat, [1]) === [[1, 2, 3], [1, 3, 2]] 
     3. [].concat([[1, 2, 3], [1, 3, 2]]) === [[1, 2, 3], [1, 3, 2]] 
    2. permutate([[1, 2, 3], [1, 3, 2]], 2, 1, [1, 2, 3]) 
     1. permute([1, 3]) === [1, 3].reduce(permutate, []) 
     2. [[1, 3], [3, 1]].map(concat, [2]) === [[2, 1, 3], [2, 3, 1]] 
     3. [[1, 2, 3], [1, 3, 2]].concat([[2, 1, 3], [2, 3, 1]]) 
    3. permutate([[1, 2, 3], [1, 3, 2], [2, 1, 3], [2, 3, 1]], 3, 2, [1, 2, 3]) 
     1. permute([1, 2]) === [1, 2].reduce(permutate, []) 
     2. [[1, 2], [2, 1]].map(concat, [3]) === [[3, 1, 2], [3, 2, 1]] 
     3. [[1, 2, 3], [1, 3, 2], [2, 1, 3], [2, 3, 1]].concat([[3, 1, 2], [3, 2, 1]])

Старый объяснение:

Сначала удалить первый элемент списка. Следовательно, у нас есть пункт 1 и список [2, 3].
1. Далее мы найдем перестановки [2, 3].
  1. Мы удаляем первый элемент. Следовательно, у нас есть пункт 2 и список [3].
    1. Далее мы найдем перестановки [3].
      1. Мы удаляем первый элемент. Следовательно, у нас есть пункт 3 и список [].
        
        Далее мы найдем перестановки [], которые являются [[]].
      2. Мы добавляем 3 в начало каждой перестановки.
      3. Результат [[3]].
    2. Мы добавляем 2 в начало каждой перестановки.
    3. Результат [[2, 3]].
  2. Мы удаляем второй элемент. Следовательно, у нас есть пункт 3 и список [[2]].
    1. Далее мы найдем перестановки [2].
      1. Мы удаляем первый элемент. Следовательно, у нас есть пункт 2 и список [].
        
        Далее мы найдем перестановки [], которые являются [[]].
      2. Мы добавляем 2 в начало каждой перестановки.
      3. Результат [[2]].
    2. Мы добавляем 3 в начало каждой перестановки.
    3. Результат [[3, 2]].
  3. Мы объединяем два списка.
  4. Результат [[2, 3], [3, 2]].
2. Мы добавляем 1 в начало каждой перестановки.
3. Результат [[1, 2, 3], [1, 3, 2]].
То же самое касается второго элемента: item 2 и список [1, 3].
То же самое для третьего элемента: item 3 и список [1, 2].
Мы объединяем три списка.
Результат [[1, 2, 3], [1, 3, 2], [2, 1, 3], [2, 3, 1], [3, 1, 2], [3, 2, 1]].

Смотреть демо:

var permute = (function() { 
 
    return permute; 
 

 
    function permute(list) { 
 
     return list.length ? 
 
      list.reduce(permutate, []) : 
 
      [[]]; 
 
    } 
 

 
    function permutate(permutations, item, index, list) { 
 
     return permutations.concat(permute(
 
      list.slice(0, index).concat(
 
      list.slice(index + 1))) 
 
      .map(concat, [item])); 
 
    } 
 

 
    function concat(list) { 
 
     return this.concat(list); 
 
    } 
 
}()); 
 

 
var array = "ahimrsu".split(""); 
 
var permutations = permute(array).map(join); 
 
var index = permutations.indexOf("maruish"); 
 

 
alert("maruish is the " + (index + 1) + "th permutation of ahimrsu."); 
 

 
function join(array) { 
 
    return array.join(""); 
 
}

Надежда, что помогает.

источник

2014-10-22 13:48:34

То, что я не могу понять, это то, где я хочу вставить var array = "ahimrsu" .split (""); var permutations = permute (array); var index = permutations.indexOf ("maruish"); –

Я добавил демо. Это должно прояснить ситуацию. –

Алгоритма строки перестановки будет немного сложнее с рекурсивным шагом (это можно кодировать без рекурсии, хотя).

Следующая Javascript реализация основана на описании алгоритма из этого answer:

Снимите первую букву

Найти все перестановки остальных букв (рекурсивный шаг)

Вставьте письмо, которое было удалено во всех возможных местах.

Реализация тогда что-то вроде этого:

function permutation(str) { 

    if (str.length == 1) { 
     return [str]; 
    } 

    var first = str[0], // Step #1 
     perms = permutation(str.slice(1)), // Step #2 
     result = []; 

    // Step #3 
    for (var i = 0; i < perms.length; i++) { 
     for (var j = 0; j <= perms[i].length; j++) { 
      result.push(perms[i].slice(0, j) + first + perms[i].slice(j)); 
     } 
    } 

    return result; 
} 

console.log(permutation('ahimrsu'));

Над реализацией дает 5040 комбинации, которые, как представляется, корректным, так как 7! == 5040 (число перестановок является факториалом числа символов).

Теперь, когда у вас есть все возможные перестановки массива вы можете легко найти конкретную строку возникновения:

var combinations = permutation('ahimrsu'); 
var index = combinations.indexOf('mariush'); // Index of the "mariush" 
alert('"mariush" is the ' + (index + 1) + 'th permutation of "ahimrsu".');

источник

2014-10-22 12:00:55 dfsq

Он будет делать то же, что и мой. Может быть, я не объясню правильно. между «ahimrsu» и «usmhira» вы можете иметь 5040 комбинаций, обозначенных 0 для ahimrsu, 1 для ahimrus, 2 для ahimsru, 3 для ahimsur и т. д. 2170 для марихуа. Мне нужно показать, что мариуш находится в положении 2170. –

Если вам нужно найти позицию определенной строки в массиве, вы должны использовать метод indexOf. Подобно 'var combination = перестановка ('ahimrsu'); var mariush = combination.indexOf ('mariush') '. – dfsq

Thats звучит хорошо, вы можете редактировать свой код сверху? –

Ну, «Мариуш» на самом деле перестановки 2220, если мы используя вашу схему заказа:

/*jslint white: true*/ 
 
var perm = function(s){ 
 
    'use strict'; 
 
    if(s.length === 1){ 
 
     return [s]; 
 
    } 
 
    // For each character c in s, generate the permuations p of all 
 
    // the other letters in s, prefixed with c. 
 
    return [].reduce.call(s, function(p,c,i){ // permutations, char, index 
 
     var other = s.slice(0,i) + s.slice(i+1); 
 
     return p.concat(perm(other).map(function(oneperm){ 
 
      return c + oneperm; 
 
     })); 
 
    }, []); 
 
}; 
 

 
alert(perm('ahimrsu').indexOf('mariush') + 1); // 2220

источник

2014-10-22 14:43:25 1983

Хорошее использование сокращения! – dfsq

Перестановка Javascript

ответ

Смежные вопросы