递归地进行排列而不存储在内存中

Question

我正在尝试使用递归函数遍历数组的所有可能排列。排列不需要存储在内存中。它们正在由递归函数立即处理。

这个想法是递归函数有一个参数 'used' 跟踪递归树中此时为 'fixed' 的元素，还有一个参数 'free'跟踪此时尚未固定的元素（即它们将在递归步骤中从那里沿着树向下重新排列）。因此，第一次使用空 'used' 数组和完整的 'free' 数组调用该函数。

我的下面的代码不知何故还不起作用。它只成功处理第一个排列。

const elements = [7, 23, 41, 65, 99]
const n = elements.length;

handlePermutations([], elements);

function handlePermutations(used, free) {
  if (used.length<n) {
    for (i = 0; i < free.length; i++) {
      newUsed = used.concat(free[i]);           // add element i from free to used
      newFree = free.filter(x => x != free[i])  // remove element i from free
      handlePermutations(newUsed, newFree);
    }
  } else {        
    // ... 'process' this permutation (do something useful with it) ...
  }
}

Answer 1

您正在使用（隐式声明的）全局 i，因此不会为每个函数重置。

改成let i解决问题

const elements = [7, 23, 41, 65, 99]
const n = elements.length;

handlePermutations([], elements);

function handlePermutations(used, free) {
  if (used.length < n) {
    for (let i = 0; i < free.length; i++) {
      let newUsed = used.concat(free[i]); // add element i from free to used
      let newFree = free.filter(x => x != free[i]) // remove element i from free
      handlePermutations(newUsed, newFree);
    }
  } else {
    console.log(...used)
    // ... 'process' this permutation (do something useful with it) ...
  }
}

顺便说一句，如果您有重复的项目，您当前的 free.filter(...) 就会中断。一种可能的方法是简单地更改它以检查传入的索引。

free.filter((x,index) => index!=i)

Answer 2

出于兴趣，这里是相同算法的生成器版本（有一些变化）。

const elements = [1, 2, 3, 4, 5]

for (let item of Permutations(elements)) {
  console.log(...item)
}

// note: this (OP's) algorithm use O(n**2) space afaict 
function Permutations(elements) {
  return handlePermutations([], elements)

  function* handlePermutations(used, free) {
    if (free.length == 0)
      yield used;
    else {
      for (let i = 0; i < free.length; i++) {
        let newUsed = used.concat(free[i]) // add element i from free to used
        let newFree = free.filter((x, index) => index != i) // remove element i from free
        yield* handlePermutations(newUsed, newFree);
      }
    }
  }
}

Answer 3

另一种方法。使用单个整数来确定该数组的不同排列。

因此生成数组的所有排列并处理它们将是：

function permutation(array, n) {
  let result = array.slice(); // don't mutate the input
  for (let i = 0, rest = result.length; rest > 1 && n > 0; ++i, n = Math.floor(n / rest--)) {
    let j = n % rest + i;
    if (i === j) continue;
    const tmp = result[i];
    result[i] = result[j];
    result[j] = tmp;
  }
  return result;
}

const elements = [1, 2, 3, 4, 5];
const length = elements.reduce((a,_,i) => a*(i+1), 1);
//const length = 5 * 4 * 3 * 2 * 1;

const map = {};
for (let i = 0; i <= length; ++i) {
  map[i] = permutation(elements, i).join();
}

console.log(map);
console.log("map[120] === map[0]", "We're back at the start. From now on this will just loop the results.");
console.log("expected %i, got %i (different values/permutations in the results)", length, new Set(Object.values(map)).size);

.as-console-wrapper{top:0;max-height:100%!important}

你说没有存储。我使用上面的 map 是因为此代码段只会存储最后 50 个 console.log，而它会在地图中显示所有 120 个 entries/lines。并在最后表明它没有创建重复项，map.

中确实有 120 种不同的排列

Answer 4

您可以采用一种简化的方法，只交出一组索引并采用两条规则：

如果最后一个元素大于前一个元素，则交换两者。
从数组末尾查找大于左右元素的索引

如果找到，则在找到的索引包括实际索引的右侧搜索下一个grater元素，将其作为组前的新元素，对其余元素进行排序并应用。

如果没有找到，结束递归。

function next([...array]) {
    console.log(...array);
    if (array[array.length - 2] < array[array.length - 1]) {
        [array[array.length - 2], array[array.length - 1]] = [array[array.length - 1], array[array.length - 2]];
        return next(array);
    }
    let index = array.length - 1;
    while (--index) {
        if (array[index - 1] < array[index] && array[index] > array[index + 1]) {
            let value = Math.min(...array.slice(index - 1).filter(v => v > array[index - 1]))
            array = [
              ...array.slice(0, index - 1),
              value,
              ...array.slice(index - 1).filter(v => v !== value).sort((a, b) => a - b)
            ];
            break;
        }
    }
    if (!index) return;

    return next(array);
}

next([0, 1, 2, 3, 4]);

.as-console-wrapper { max-height: 100% !important; top: 0; }

Answer 5

另一种方法是让您传递将用于每个排列的回调函数。

const excludeIndex = (i) => (xs) => 
  [... xs .slice (0, i), ... xs .slice (i + 1)]

const handlePermutations = (fn) => (free, used = []) =>
  free.length == 0
    ? fn (used)
    : free .forEach (
        (e, i) => handlePermutations (fn) (excludeIndex (i) (free), [...used, e])
      )

handlePermutations (xs => console. log(...xs)) ([7, 23, 41, 65])

.as-console-wrapper {max-height: 100% !important; top: 0}

我们包括简单的助手 excludeIndex，它 returns 缺少索引的数组副本。我们在递归调用中使用它以及将当前元素连接到 used.

我不太喜欢只为副作用编写代码，但由于这是问题的基本目标，我当然可以接受它。

时间复杂度是不可避免的O (n!)。 ~~Space 复杂度我认为是 O (n)，因为 free 和 used 一起包含原始的 n 个元素。~~（糟糕，看评论！）Space 复杂度是 O (n^2)

递归地进行排列而不存储在内存中

Recursively going through permutations without storing in memory

javascript

algorithm

recursion

permutation