Алгоритм перестановок с повторениями

by malikzh

HTML

<form id="form">
  <p>
    Строка
  </p>
  <div>
    <input type="text" name="str" value="abcd">
  </div>
  
  <p>
    Количество перестановок
  </p>
  <div>
    <input type="number" name="index" min="0" value="64">
  </div>
  
  <div style="margin-top: 10px;">
    <button type="submit">
      Обработать
    </button>
  </div>
  <hr>
  <pre id="result"></pre>
</form>

JavaScript

/**
 * Алгоритм генерации перестановок
 */
function gent(items, index)
{
	const length = items.length;
  
  const height = length - 1;
  const max    = length * height / 2;

	// Цикл перебирает все "выключатели" и меняет местами буквы, если бит в соответствующей позиции == 1
  // i - это просто счётчик от 0 до количества выключателей минус один
  // j - этаж на котором мы находимся в данный момент
  // k - ряд на котором мы находимся в данный момент
  for (let i=0, j=0, k=1; i < max; ++i,++k) {
  	
    // Здесь мы вычисляем, какие индексы массива мы будем менять местами
    let left = k - 1;
    let right = k + j;
    
    // Если "выключатель" включён, то меняем местами
    if ( index & (0x01 << i) ) {
    	const tmp = items[left];
      items[left] = items[right];
      items[right] = tmp;
    }
    
    // Увеличиваем высоту, если мы прошли ряд
    //console.log(i,j,k);
    if (k % (height - j) === 0) {
    	k -= (height - j);
    	++j;
    }
  }
  
  return items;
}

///////// Код для формы
document.querySelector('#form').addEventListener('submit', function (e) {
	e.preventDefault();
  
  let str = String(e.target.str.value);
  let idx = Number(e.target.index.value);
  
  let items = str.split('');
  
  let out = '';
  
  let arr = [];
  
  for (let i=0; i<idx; ++i) {
    
    arr.push(gent(items.slice(), i).join(''));
    
    out += i.toString().padStart(3, ' ') + ': ' + gent(items.slice(), i).join('') +  " - " + i.toString(2).padStart(6, '0') + "\n";
  }
  
  let qq = {};
  
  let ii = 0;
  for (let x of arr) {
  	if (!qq[x]) {
    	qq[x] = [ii++];
    } else {
    	qq[x].push(ii++);
    }
  }
  
  let qc = [];
  
  for (let t of Object.values(qq)) {
  	qc.push(t[0]);
  }
  
  let qqc = [];
  let qqa = 0;
  
  for (let u of qc) {
  	if (qqa !== u) {
    	qqc.push(qqa);
      qqa -= u;
      continue;
    }
    ++qqa;
  }
  
  console.log(qq);
  console.log(qc);
  
  document.querySelector('#result').textContent = out;
});