3

Пытаюсь перебрать элементы массива и получить все комбинации с заданным количеством элементов (длина комбинации задается в функции):

function printPermutations(array, k) { 
    var combinations = [];
    var indices = [];
    function run(level, start) {
        for (var i = 0; i < array.length; i++) {
            if (!indices[i]) {
                indices[i] = true;
                combinations[level] = array[i];
                if (level < k - 1) {
                    combinations.push(Array(run(level + 1, i + 1)));
                } else {
                    combinations.join(" ");
                }
            indices[i] = false;
            }
        }
    }
    run(0, 0);
}
console.log(printPermutations([1, 2, 3, 4], 3));

Для того чтобы получился такой результат:

[[1 2 3],
[1 2 4],
[1 3 2],
[1 3 4],
[1 4 2],
[1 4 3],
[2 1 3],
[2 1 4],
[2 3 1],
[2 3 4],
[2 4 1],
[2 4 3],
[3 1 2],
[3 1 4],
[3 2 1],
[3 2 4],
[3 4 1],
[3 4 2],
[4 1 2],
[4 1 3],
[4 2 1],
[4 2 3],
[4 3 1],
[4 3 2]]

Что я делаю не так?

2 ответа 2

3

Вот еще один вариант ответа, на мой взгляд самый компактный:

function printPermutations(array, k){
  var m=[];
  var combinations = [];
  var indices = [];
  var len=array.length;
  function run(level){    
    for(var i=0; i < len; i++){            
	  if(!indices[i]){            
	    indices[i] = true;                
		combinations[level] = array[i];                
		if(level < k - 1){
		  run(level + 1, i + 1);
		} else {
		  m.push(([]).concat(combinations));
		}                
		indices[i] = false;
	  }
	}        
  }    
  run(0);
  return m;
}
console.log(printPermutations([1, 2, 3, 4], 3));

0

У вас как-то не хватает половины алгоритма, а имеющаяся часть делает непонятно что.

Что можно сделать:

  • Для заданной позиции (от 0 до k - 1, в коде это index) пробегаться по всем элементам (индексам) массива (i = 0; i < array.length; i++)
  • Исключать те элементы массива, которые уже входят в формируемую комбинацию (alreadyInCombination(i, index))
  • Для каждого неисключенного делать рекурсивный вызов с позицией + 1 (next(index + 1)), предварительно сохранив зафиксированный элемент в комбинацию (indices[index] = i)
  • Если дошли до позиции k, то сохраняем полученную комбинацию в итоговый результат и возвращаемся на предыдущую позицию.

Код:

function printPermutations(array, k) {
  var combinations = [];
  var indices = [];
  function next(index) {
    if (index == k) {
      var result = [];
      for (var i = 0; i < k; i++) {
        result[i] = array[indices[i]];
      }
      combinations.push(result);
      return;
    }
    for (var i = 0; i < array.length; i++) {
      if (alreadyInCombination(i, index))
        continue;
      indices[index] = i;
      next(index + 1);
    }
  }
  function alreadyInCombination(i, index) {
      for (var j = 0; j < index; j++) {
        if (indices[j] == i) {
          return true;
        }
      }
      return false;
  }
  next(0);
  return combinations;
}

console.log(printPermutations([1, 2, 3, 4], 3));

Ваш ответ

Нажимая на кнопку «Отправить ответ», вы соглашаетесь с нашими условиями использования и подтверждаете, что прочитали и поняли наши политику конфиденциальности и нормы поведения.

Всё ещё ищете ответ? Посмотрите другие вопросы с метками или задайте свой вопрос.