Как сделать перестановочную пару без использования глобальной переменной в JavaScript?

Question

Мне нужно создать массив всех возможных комбинаций элементов массива, таких как перестановка, вопрос о структуре данных с широким разбросом.Чтобы узнать больше о вопросе, можете проверить здесь: случайные хаки , geeksforgeeks и мир математики .

Примечание: не хочучтобы использовать любую библиотеку JS, просто структура данных здесь

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

arr = [1,2,3];
combination = [[1,2,3], [1,3,2], [2,1,3], [2,3,1], [3,1,2], [3,2,1]];
// combination.length is factorial of arr.length

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

let ans = [];  // Global variable to store combinations

function permute(arr) {
  let l = arguments[1] || 0,
      r = arguments[2] || arr.length-1;

  if (l == r) {
    let a = [];

    a.push(...arr);  // To overcome reference problem here.
    ans.push(a);
  }
  else {
    for (let i = l; i <= r; i++) {
      [arr[l], arr[i]] = [arr[i], arr[l]];  // Swap with help of new destructuring
      permute(arr, l+1, r);
      [arr[l], arr[i]] = [arr[i], arr[l]];  // Swap with help of new destructuring
    }
  }

  return ans;
}

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

Спасибо, что попробовали и помогли.

Answer 1

Вы также можете попробовать использовать Array.map с рекурсией, как показано ниже, для достижения перестановки.Я также использовал Array.flat (на данный момент Edge не поддерживается, и для поддержки браузера Edge требуется polyfill)

function getForwardArr(arr, i) {
  return [...arr.slice(i+1), ...arr.slice(0, i)]
}

function permute(arr) {
  if (arr.length == 2) return [[...arr], arr.reverse()]
  else return arr.map((d, i) => permute(getForwardArr(arr, i)).map(v => [d, v].flat())).flat()
}

console.log(permute([1,2]))

console.log(permute([1,2,3]))

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

Answer 2

Другой способ сделать это - не передавать «вниз» что-либо, а повторно использовать результаты меньших подзадач для построения массива перестановок и возвращать его.

Так, например, для построения всех перестановок из 3 элементов,вы бы поставили каждый элемент на первое место и соединили его со всеми 2-мя перестановками элементов оставшихся элементов (которые вы получите при рекурсивном вызове):

function permutations(arr) {
  if (arr.length <= 1) return [arr];
  var res = [];
  arr.forEach((e, i) => {
    var smaller = permutations([...arr.slice(0, i), ...arr.slice(i + 1)]);
    smaller.forEach(p => res.push([e].concat(p)))
  });
  return res;
}

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

Answer 3

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

function permute(_arr) {
  let ans = [];
  (function _permute(arr) {
    let l = arguments[1] || 0,
      r = arguments[2] || arr.length - 1;

    if (l == r) {
      let a = [];

      a.push(...arr);  // To overcome reference problem here.
      ans.push(a);
    }
    else {
      for (let i = l; i <= r; i++) {
        [arr[l], arr[i]] = [arr[i], arr[l]];  // Swap with help of new destructuring
        _permute(arr, l + 1, r);
        [arr[l], arr[i]] = [arr[i], arr[l]];  // Swap with help of new destructuring
      }
    }
  })(_arr);
  return ans;
}

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

Answer 4

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

 function* permutations(array, positions = [], previous = []) {
  if(previous.length === array.length) yield previous;

  for(let i = 0; i < array.length; i++) {
   if(positions.includes(i)) continue;

   const chosen = array[i];
   yield* permutations(array, [...positions, i], [...previous, chosen]);
  }
}

const permutate = arr => [...permutations(arr)];

Answer 5

Вы делаете рекурсию без сдачи аккумулятора.Чтобы облегчить это, сделайте ...

function permuteRecursive(permutees, accumulator) {
  // if not created before, create first instance of accumulator
  accumulator = accumulator || [];

  let l = arguments[2] || 0,
      r = arguments[3] || permutees.length-1;

  if (l == r) {
    let a = [];

    a.push(...permutees);  // To overcome reference problem here.
    accumulator.push(a);
  }
  else {
    for (let i = l; i <= r; i++) {
      [permutees[l], permutees[i]] = [permutees[i], permutees[l]];  // Swap with help of new destructuring
      permuteRecursive(permutees, accumulator, l+1, r);
      [permutees[l], permutees[i]] = [permutees[i], permutees[l]];  // Swap with help of new destructuring
    }
  }

  return accumulator;
}

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