Javascript: мини-сервис для определения количества перестановок и комбинаций символов

Вводим любую строку, сервис сам её чистит от разделителей и повторяющихся символов, нажимаем кнопку :) Вот в работе прямо здесь:

Извините, для работы приложения нужен включённый Javascript

Что полезного в коде:

• простые замыкания для функций, см. getPermutations, getCombinations. Зачем они нужны? А чтобы сделать общую область видимости для внешних данных рекурсивной функции и самой этой функции;
• вложение пользовательской функции сортировки для стандартной функции сортировки sort. Строки массива сортируются сначала по убыванию длины, затем по алфавиту, если длины одинакова. Кстати, sort при некоторых условиях "глючит", может не переставить последнюю пару элементов;
• метод deleteRepeats (string) с помощью регулярного выражения удаляет из строки string все повторяющиеся символы.

Рекурсивный метод permutate(chars) для параметра-массива chars, состоящего из переставляемых символов, находит число перестановок, равное факториалу от количества символов строки.

Рекурсивный метод combinate (chars, str) для строки-параметра str (первый параметр при первом вызове пуст) вычисляет "цэшки", то бишь, Cnk при k, меняющемся от 1 до n включительно, где n - длина строки, переданной вторым параметром. В Excel это делает стандатная функция =ЧИСЛКОМБ(n,k). Также его можно использовать для вывода всех подмножеств множества, общее количество которых, не считая пустого множества, равно 2 в степени n-1.

К сожалению, Javascript - медленный язык, так что длину строки ввода я ограничил всего семью символами. Также не заморачивался случаем, когда внутренний порядок элементов в группе имеет значение.

Исходник приложения (на момент написания и без обрамляющих тегов HTML):

<script type="text/javascript">

function trimAll(string) { //удалить все разделители из строки
 return string.replace (/\s+/g,""); 
}

function deleteRepeats (string) { //удалить все повторы символов из строки
 return string.replace(/(.)(?=.*\1)/g, "");
}

function getPermutations (str) { //замыкание для функции вычисления перестановок (permutations)
 var permutations = [], //массив для хранения перестановок
     nextWord = [],     //следующее слово 
     chars = [];        //символы
    ;
 if (typeof str === 'string') chars = str.split(''); 
 else if (typeof str === 'number') {
  str = str + ''; //конвертировать число в строку на Javascript - самое простое :)
  chars = str.split('');
 }
 permutate(chars);
 return permutations;

 function permutate(chars) { //рекурсивная функция для генерации перестановок
  if (chars.length === 0) permutations.push(nextWord.join(''));            
  for (var i=0; i < chars.length; i++) {
   chars.push(chars.shift());
   nextWord.push(chars[0]);  
   permutate(chars.slice(1));
   nextWord.pop();             
  }
 }
}

function Permutations () {  //функция для получения данных и вывода результатов о перестановках
 var str = document.perform.str.value;
 var newstr = deleteRepeats(trimAll(str));
 document.perform.str.value = newstr;
 var per = getPermutations (newstr);
 var res = '';
 for (var i=per.length-1; i > -1 ; i--) res += per[i]+' ';
 if (per.length>1) res += '<br>Всего перестановок: ' + per.length;
 document.getElementById('perres').innerHTML = res;
}

function getCombinations (chars, str) { 
 //замыкание для функции вычисления комбинаций (combinations) по k=1,2,...,n из n, n == длине строки str
 var combinations = [];  //массив для хранения комбинаций
 if (typeof str === 'number') str = str + '';
 combinate (chars, str);
 return combinations;

 function combinate (chars, str) { //рекурсивная функция для генерации комбинаций
  if (str.length == 0) {
   combinations.push(chars);
  } 
  else {
   combinate (chars + str.charAt(0), str.substring(1, str.length));
   combinate (chars, str.substring(1, str.length));
  }
 }
}

function Combinations () {  //функция для получения данных и вывода результатов о комбинациях
 var str = document.perform.str.value;
 var newstr = deleteRepeats(trimAll(str));
 document.perform.str.value = newstr;
 var comb = getCombinations ('', newstr);
 var res = '';
 comb.sort (
  function (a,b) {
   var a0=a+'',b0=b+'';
   if (a0.length!=b0.length) return a0.length-b0.length;
   else return a0<b0;
  }
 );
 var len = newstr.length, cnt = 0;
 for (var i=comb.length-1; i > -1  ; i--) {
  if (comb[i].length < len) {
   res += ' ; C('+newstr.length+','+len+')='+cnt+'<br>';
   len--; cnt=0;
  }
  res += comb[i]+' ';
  cnt++;
 }
 res += 'Всего подмножеств: ' + (comb.length-1);
 document.getElementById('perres').innerHTML = res;
}


function clearMe () { //очистка формы
 document.perform.str.value = '';
 document.getElementById('perres').innerHTML = '';
}

</script>
<noscript><p>Извините, для работы приложения нужен включённый Javascript</p></noscript>

<table align="center" width="50%" cellpadding="0" cellspacing="4" border="0">
 <tr>
  <td align="center" valign="middle">
   <form name="perform" method="post">
    <p><font size="1">Введите строку, все разделители и повторы символов будут удалены:</font>
    <br>
     <input type="text" name="str" size="9" maxlength="7" value="" />
     <input type="button" name="action1" value="Перестановки" onclick="Permutations();" />
     <input type="button" name="action2" value="Комбинации" onclick="Combinations();" />
     <input type="button" name="clear" value="Очистить" onclick="clearMe();" />
    </p>
   </form>
  </td>
 </tr>
 <tr>
  <td valign="middle">
   <div id = "perres"></div>
  </td>
 </tr>
</table>

18.04.2016, 12:04 [5937 просмотров]