Почему эта функция не возвращает все перестановки заданного массива? - PullRequest
Новая
       30

Почему эта функция не возвращает все перестановки заданного массива?

1 голос
/ 02 апреля 2020

Я пытаюсь написать функцию, которая бы возвращала все перестановки заданного массива чисел, как в примерах ниже: 

a = [1, 1, 2]
permutator(a) = [
  [1,1,2],
  [1,2,1],
  [2,1,1]
]

b = [2, 3, 4]
permutator(b) = [
  [2,3,4],
  [2,4,3],
  [3,2,4],
  [3,4,2],
  [4,2,3],
  [4,3,2]
]

порядок результатов не точен

Можете ли вы объяснить, почему код ниже не работает? Я попытался отладить, и я думаю, что переменные temp и result не хранятся в памяти как массивы, но я не уверен, так ли это, и как это решить. 

permutator = (array) => {
  const result = [];

  array.forEach((num, i) => {
    array.forEach((num2, j) => {
      if (i !== j) {
        let temp = array;
        temp[i] = temp[j];
        temp[j] = num;
        console.log(`temp: ${temp}`);
        console.log(`result: ${result}`);
        if (!result.includes(temp)) result.push(temp);
        console.log(`result: ${result}`);
      }
    });
  });

  return result;
}

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

Ответы [ 2 ]

1 голос
/ 03 апреля 2020

Это работает для трех цифр, но я бы не назвал это элегантным: 

let indexAtEachPosition = function (ind, arr) {
  let arrayGroup = [];
  let arrLength = arr.length;
  let movedArray = [...arr];
  for (let indx = 0; indx < arrLength; indx++) {
    let firstItem = movedArray[0];
    let otherItems = movedArray.slice(1);
    otherItems[arrLength - 1] = firstItem
    movedArray = [...otherItems];
    arrayGroup.push(movedArray.join(" "));
  }
  return arrayGroup;
}

let permutator = function permutator(values) {
  let returnValue = new Set();
  let digitCount = values.length;
  returnValue.add(values.join(" "));

  values.forEach(digit => {
    indexAtEachPosition(digit, values).forEach(variation => {
      returnValue.add(variation);
    });
  });
  [...values.reverse()].forEach(digit => {
    indexAtEachPosition(digit, values).forEach(variation => {
      returnValue.add(variation);
    });
  });
  return [...returnValue].map(eachArr => {
    return eachArr.split(" ");
  });
};



// console.log( permutator([0,0,0]) );
// console.log( permutator([1,0,0]) );
// console.log( permutator([1,2,3]) );
console.log( permutator([1,1,2]) );
console.log( permutator([2,3,4]) );

Я не уверен, какова цель этого, но это заинтриговало меня как какой-то тест кода, поэтому я попытался решить его.

0 голосов
/ 27 апреля 2020

Этот ответ является самым элегантным решением, которое я нашел . 

const permutator = (inputArr) => {
  let result = [];

  const permute = (arr, m = []) => {
    if (arr.length === 0) {
      result.push(m)
    } else {
      for (let i = 0; i < arr.length; i++) {
        let curr = arr.slice();
        let next = curr.splice(i, 1);
        permute(curr.slice(), m.concat(next))
      }
    }
  }

  permute(inputArr)

  return result;
}

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