javascript - JS : How to create an array containing permutations of a sequence 0 to n in which adjacent numbers must have a difference greater than 1?

Question

只是详细说明所问的问题。假设您有一个从 0 到 n (0,1,2, ... n-1,n) 的序列。我想返回一个数组，其中包含满足相邻数字必须具有大于 1 的差异的条件的所有可能排列。例如，给定序列 (0,1,2,3)，唯一有效的排列是 ( 1,3,0,2) 和 (2,0,3,1)。

我实际上已经有了一个工作函数。

function validSequences(n) {
  let all = [],
    baseSequence = [],
    startingValue = 0,
    sequenceLastIndex = 0;
  for (let x=0; x<n; x++) {
    baseSequence.push(x);
  }
  while (startingValue < n) {
    while (sequenceLastIndex < (n-1)) {
      if (sequenceLastIndex == 0) {
        let nextPossibleValues = baseSequence.filter((i) => {
          return Math.abs(startingValue - i) > 1;
        });
        nextPossibleValues.forEach((value) => {
          all.push([startingValue, value]);
        });
      } else {
        all.forEach((sequence) => {
          if (sequence[0] == startingValue) {
            let nextPossibleValues = baseSequence.filter((i) => {
              return Math.abs(sequence[sequenceLastIndex] - i) > 1 && !sequence.includes(i);
            });
            if (nextPossibleValues.length == 0) {
              all = all.filter((keep) => {
                return keep !== sequence;
              });
            } else {
              nextPossibleValues.forEach((value) => {
                let copy = [...sequence];
                copy.push(value);
                all.push(copy);
              });
            }
            all = all.filter((keep) => {
              return keep[0] !== startingValue || keep.length == (sequenceLastIndex + 2);
            });
          }
        });
      }
      sequenceLastIndex++;
    }
    sequenceLastIndex = 0;
    startingValue++;
  }
  return all;
}

上述函数将产生 0-7 序列的瞬时结果。任何高于此的事情都将花费大量时间。谁能想出一种可以处理更长序列的解决方案，或者比我目前拥有的解决方案更高效/更优雅的解决方案？

Answer 1

您肯定需要更优雅的东西来使代码易于维护。我建议从一个普通的递归解决方案开始，也许是一个奇特(且高效)的生成器函数:

function* permutations(array, i) {
    if (i >= array.length)
        yield array;
    else
        for (let j=i; j<array.length; j++)
            yield* permutations([
                ...array.slice(0, i),
                array[j],
                ...array.slice(i, j),
                ...array.slice(j+1)
            ], i+1);
}
Array.from(permutations(['a', 'b', 'c', 'd'], 0))

现在您需要做的就是为相邻元素添加条件:

function* permutations(array, i) {
    if (i >= array.length)
        yield array;
    else
        for (let j=i; j<array.length; j++)
            if (i == 0 || Math.abs(array[i-1] - array[j]) > 1)
                yield* permutations([
                    ...array.slice(0, i),
                    array[j],
                    ...array.slice(i, j),
                    ...array.slice(j+1)
                ], i+1);
}
Array.from(permutations([0, 1, 2, 3], 0))

Anything above sequences up to 0-7 will take a ridiculous amount of time

这很正常。这种大小的数组有很多很多排列，而您的条件只会过滤掉其中的一些。这是一个快速表格:

length | number of solutions
-------+---------------------
 0     | 1
 1     | 1
 2     | 0
 3     | 0
 4     | 2
 5     | 14
 6     | 90
 7     | 646
 8     | 5242
 9     | 47622
 10    | 479306

…又名OEIS A002464 :-)