typescript 查找所有路径组合

yks3o0rb  于 2023-10-22  发布在  TypeScript
关注(0)|答案(4)|浏览(141)

不知道这是否有一个特定的名称,但我需要展平一个一维数组和简单元素的数组,以一种方式,所有的组合,直到一个叶子“节点”报告。这里有一个例子,因为上面的内容给我们留下了很多想象空间:

// 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”的参数。
我的代码有什么问题,或者有更好的(更习惯的)方法来做到这一点。

u0sqgete

u0sqgete1#

您可以在不向下传递上下文数组的情况下处理此问题,方法是使用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]]
 // [[]]
pbpqsu0x

pbpqsu0x2#

这是生成器函数的一个很好的用例,因为它允许您在离开注解处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 ]
]
*/
htrmnn0y

htrmnn0y3#

我可以编译你的代码,但它进入无限循环。我认为问题出在这一部分;

for (let ar of result) {
            result.push(last);
        }

在遍历result数组时,将元素推入该数组。这会导致无限循环。
要解决这个问题,您可以创建一个单独的数组来存储新元素,然后将其与循环外的result数组连接起来。
以下工作正常;

const newElements = [];
        for (let ar of result) {
            newElements.push(last);
        }
        result = result.concat(newElements);
clj7thdc

clj7thdc4#

这个版本,独立编写,表达了相同的算法,从皮尔彻德的答案。但它清理了一些东西,并使用纯表达式而不是语句,正如我一直喜欢的那样:

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的回答还表达了对输入中可能存在undefined值的担忧。如果这是一个问题,一个简单的解决方案是引入一个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值。

相关问题