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

Помощь дата->рейтинг Поиск Почта RSS канал Статистика nickolay.info Домой

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

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

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

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

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

Рекурсивный метод 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>

теги: javascript числа сервис

комментарии (1)

18.04.2016, 12:04; рейтинг: 3528

  свежие записипоиск по блогукомментироватьстатистика

Наверх Яндекс.Метрика
© PerS
вход