logo标签列表

找到所有路径组合

javascripttypescriptalgorithm
3

不知道这个有没有特定的名称，但是我需要将一个由一维数组和简单元素组成的数组展开，以便报告所有直到叶子“节点”的组合。这里有一个例子，因为上面的描述让人想象力丰富：

// My input array contains single elements or 1D arrays:
let input = [1, 2, [3, 4], [5, 6]];

每次遇到一个数组时，展开过程会将路径分割成与数组元素数量相同的部分。
// current result = [1, 2]
// unconsumed input [[3, 4], [5, 6]]
// ->
// current result = [ [1, 2, 3], [1, 2, 4] ]

// current result = [ [1, 2, 3], [1, 2, 4] ]
// unconsumed input [[5, 6]]
// ->
// final result = [ [1, 2, 3, 5], [1, 2, 4, 5], [1, 2, 3, 6], [1, 2, 4, 6] ]

我可能在复制和别名方面搞砸了，但似乎无法使其正常工作并处理特殊情况，例如：
let input1 = [1, 2, 3]; // No nested arrays
let input2 = [];        // Empty input

尝试反向构建结果，因为在这里使用.pop很方便，但无法使其正常工作。

function flatPath(input, result = [[]]) {
    while (input.length) {
        const last = input.pop();

        if (Array.isArray(last)) {
            result = flatPath(last, [...result, ...result]);
        } else {
            for (let ar of result) {
                result.push(last);
            }
        }
    }
    return result;
}

let result = flatPath([1, 2, [3, 4], [2, 5, 6] ]);

console.log(result);

但甚至连编译都无法通过（我正在使用TypeScript），因为我得到的只有：

参数 'input' 隐式具有 'any' 类型。

类型 'any' 的参数无法赋值给类型 'never' 的参数。

我的代码有什么问题，或者有没有更好（更符合惯用法）的方法来解决这个问题。

你可以尝试使用https://www.typescriptlang.org/play?target=99&jsx=0#code/GYVwdgxgLglg9mABMANgQygBQwCwBQxgAOIUAXInmCALYBGApgE6IA+i19zA2gLoCUffhU6MmfPogDeAKESIUDKIiYjaYib0QBeRNz68A3HORwWeRcrQATaw2uI4wRIRJR+0k-MuIbd6wCCTCy6QUxoAJ4AdDAAzmGReH72HgD8vrb2iBTcydZGXio6KlGoGACyaER4REwMAG46AHwZ-mFRNFVJzXpRfbUNADS+AvwmAL4mdVAgTEhMxpOgkLAIyOhYuACMBMSkFFTqzGwcR+ICQmpc55Ky8tOzSK6kJh1dDD0J0XFfeAxpiA+OQYAledWsIAgDAAPKIeLw+E08DU6vVhnkPNoWnd5ColI9WvZShtKtU0D0BvU3tUiD1uH0okR0aMJsN9LxQZMZD46rEQChlLoypsoPhuFthgAmNkAZmGABZeGzpYgAKzDABsHP4xhkEAQsTgiiiKDgAHM8Lz+e5DEA 进行尝试。 - Dimava
你可以尝试使用https://www.typescriptlang.org/play?target=99&jsx=0#code/GYVwdgxgLglg9mABMANgQygBQwCwBQxgAOIUAXInmCALYBGApgE6IA+i19zA2gLoCUffhU6MmfPogDeAKESIUDKIiYjaYib0QBeRNz68A3HORwWeRcrQATaw2uI4wRIRJR+0k-MuIbd6wCCTCy6QUxoAJ4AdDAAzmGReH72HgD8vrb2iBTcydZGXio6KlGoGACyaER4REwMAG46AHwZ-mFRNFVJzXpRfbUNADS+AvwmAL4mdVAgTEhMxpOgkLAIyOhYuACMBMSkFFTqzGwcR+ICQmpc55Ky8tOzSK6kJh1dDD0J0XFfeAxpiA+OQYAledWsIAgDAAPKIeLw+E08DU6vVhnkPNoWnd5ColI9WvZShtKtU0D0BvU3tUiD1uH0okR0aMJsN9LxQZMZD46rEQChlLoypsoPhuFthgAmNkAZmGABZeGzpYgAKzDABsHP4xhkEAQsTgiiiKDgAHM8Lz+e5DEA进行尝试。 - Dimava
4个回答
2
这是一个很好的生成器函数应用案例，因为它允许你在叶节点（其基数无法事先确定）上yield结果，而无需处理递归调用树向上聚合的过程。 

const flatPath = function*(array, prefix = []) {
  const next = array[0];
  if (next === undefined) { // base case
    yield prefix;
  } else if (next instanceof Array) {
    for (let item of next) {
      yield * flatPath(array.slice(1), [...prefix, item]);
    }
  } else {
    yield * flatPath(array.slice(1), [...prefix, next]);
  }
};

const result = Array.from(flatPath([1, 2, [3, 4], [2, 5, 6]]));
console.log(result);

/* output:
[
  [ 1, 2, 3, 2 ],
  [ 1, 2, 3, 5 ],
  [ 1, 2, 3, 6 ],
  [ 1, 2, 4, 2 ],
  [ 1, 2, 4, 5 ],
  [ 1, 2, 4, 6 ]
]
*/

1
好的注意到了！已修复。 - Christian Fritz
1
好抓到！已修复。 - Christian Fritz
2
你可以在这里从下往上聚合结果，使用map()将前一次调用的非数组元素添加到更深层次调用返回的子数组中，而无需传递上下文数组。 

function flatPath([next, ...rest]) {
  if (next === undefined) {
    return [[]];
  }

  if (Array.isArray(next)) {
    const temp = [];
    for (const n of next) {
      temp.push(...flatPath([n, ...rest]));
    }
    return temp;
  }

  return flatPath(rest).map(t => [next, ...[].concat(t)]);
}


// Test output
for (const test of [
  [1, 2, [3, 4], [5, 6]],
  [1, 2, 3], 
  [[1, 2, 3], 4], 
  []
]) {
  let result = flatPath(test);
  console.log(JSON.stringify(result));
}

 // [[1,2,3,5],[1,2,3,6],[1,2,4,5],[1,2,4,6]]
 // [[1,2,3]]
 // [[1,4],[2,4],[3,4]]
 // [[]]

如果您的数组中有一个undefined元素，上述方法将失败。通过检查...rest的长度来确定底部（并显式检查作为输入传递的空数组），可以解决这个问题。 

function flatPath(input) {
  if (input.length === 0) {
    return [];
  }

  const [next, ...rest] = input;

  if (Array.isArray(next)) {
    const temp = [];
    for (const n of next) {
      const tail = rest.length
        ? flatPath([n, ...rest])
        : flatPath([].concat(n));

      temp.push(...tail);
    }
    return temp;
  }

  return rest.length
    ? flatPath(rest).map(t => [next, ...[].concat(t)])
    : [next];
}

// Test output
for (const test of [
  [1, 2, [3, 4], [5, 6]],
  [1, 2, 3], 
  [[1, 2, 3], 4], 
  []
]) {
  let result = flatPath(test);
  console.log(JSON.stringify(result));
}

 // [[1,2,3,5],[1,2,3,6],[1,2,4,5],[1,2,4,6]]
 // [[1,2,3]]
 // [[1,4],[2,4],[3,4]]
 // [[]]

1
这个版本是独立编写的，表达了与pilchard的答案相同的算法。但它对一些细节进行了优化，并使用纯表达式而不是语句，因为我总是更喜欢这样做。 

const process = ([xs, ...xss], rs = xs !== undefined && process(xss)) =>
  xs === undefined
    ? [[]]
  : Array.isArray(xs)
    ? xs.flatMap(x => rs.map(r => [x, ...r]))
  : rs.map(r => [xs, ...r]);

const input = [1, 2, [3, 4], [5, 6]]

console .log(JSON.stringify(process (input)))

Pilchard的回答还表达了对输入中可能存在的未定义值的担忧。如果这是一个问题，一个简单的解决方案就是引入一个Symbol，像这样：
const None = Symbol()

const process = ([xs = None, ...xss], rs = xs !== None && process(xss)) =>
  xs === None
    ? [[]]
  : Array.isArray(xs)
    ? xs.flatMap(x => rs.map(r => [x, ...r]))
  : rs.map(r => [xs, ...r])

const input = [1, 2, [3, 4], [5, 6]]

但是除非你期望并且希望处理"undefined"的值，否则我不会费心。
1
我能够编译你的代码，但它进入了无限循环。我认为问题出在这部分；
        for (let ar of result) {
            result.push(last);
        }

你在遍历 result 数组时向其中添加元素，这导致了一个无限循环。
为了解决这个问题，你可以创建一个单独的数组来存储新的元素，然后在循环外将其与 result 数组连接起来。
以下方法可以正常工作；
        const newElements = [];
        for (let ar of result) {
            newElements.push(last);
        }
        result = result.concat(newElements);
网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接