将一个递归嵌套的数组分成两个。

Question

我有一个如下的数组：
["this", "is", ["a", ["nested", "array", "I"], "want", "to"], "split"]

我想要一个函数来获取两个像这样的数组：
["this", "is", ["a", ["nested", "ar"]]] [[["ray", "I"], "want", "to"], "split"]

最好情况下，我希望这个函数的参数是初始数组、目标字符串和偏移量。所以在这里，它将是 recurSplit(foo, foo[2][1][1], 2)。但我也欢迎其他解决方案。

我已经制作了这个可行的解决方案，但是我并不满意，因为我的hasCut变量需要在函数外部。我想知道在函数内部如何判断我是在目标的左侧（或右侧）。

let hasCut = false
function recurSplit(element, target, offset) {
    let left, right
    if (typeof element == 'string') {
        if (element == target) {
            left = element.slice(0, offset)
            right = element.slice(offset)
            hasCut = true
        } else {
            left = hasCut ? false : element
            right = hasCut ? element : false
        }
    } else {
        left = []
        right = []
        for (const child of element) {
            const res = recurSplit(child, target, offset)
            if (res[0])
                left.push(res[0])
            if (res[1])
                right.push(res[1])
        }
    }
    return [left, right]
}

• 是的，我可以创建另一个递归检查它的函数，但那将是无用的处理。
• 是的，我可以将此函数设置为匿名函数并封装在另一个函数中，但那很特定于JS。

难道没有更好的方法吗？
谢谢！

- Florent Descroix

---

添加一个可选的context或state参数，其默认值为{hasCut: false}，并将其随递归调用一起传递，在函数内部更改该对象的值，而不是外部变量的值。 - Trevor Dixon

哦，使用对象而不是布尔值作为参数的好主意！ - Florent Descroix

Answer 1

不要直接传递内部元素，而是可以传递一个指向该元素的索引数组，然后对该数组进行递归，从内部向外部切片并返回一个元组，该元组在每个级别上展开。代码段解构传递的 path 数组 ([i, ...path])，然后检查尾随的 ...rest 数组中是否有任何剩余的索引。如果有，则递归，否则拆分单词并将其作为元组返回。

const input = ["this", "is", ["a", ["nested", "array", "I"], "want", "to"], "split"]

function recursiveSplit(array, [i, ...path], offset) {
  const [left, right] = path.length
    ? recursiveSplit(array[i], path, offset)
    : [array[i].slice(0, offset), array[i].slice(offset)];

  return [
    [...array.slice(0, i), left],
    [right, ...array.slice(i + 1)],
  ];
}

const [head, tail] = recursiveSplit(input, [2, 1, 1], 2);

console.log('head: ', JSON.stringify(head));
console.log('tail: ', JSON.stringify(tail));

如果你需要将目标作为字符串传递，你可以从递归的底部传递hasCut，如果hasCut为true，则中断循环并重新开始，否则返回完整的元素并继续搜索。

const input = ["this", "is", ["a", ['deep'], ["nested", "array", "I"], "want", "to"], "split"];

function recursiveSplit(array, target, offset) {
  let left, right, index, hasCut = false;

  for (const [i, element] of array.entries()) {
    index = i;

    if (element === target) {
      left = element.slice(0, offset);
      right = element.slice(offset);
      hasCut = true;
      break;
    }

    if (Array.isArray(element)) {
      ({ hasCut, left, right } = recursiveSplit(element, target, offset));
      if (hasCut) break;
    }
  }

  return {
    hasCut,
    left: hasCut ? [...array.slice(0, index), left] : array,
    right: hasCut ? [right, ...array.slice(index + 1)] : undefined
  }
}

const { left, right } = recursiveSplit(input, 'array', 2);

console.log('left: ', JSON.stringify(left));
console.log('right: ', JSON.stringify(right));

或者使用常见的模式，如在评论中提到的那样，通过传递上下文（context）或状态（state）参数向下传递。

const input = ["this", "is", ["a", ["deep", []], ["nested", "array", "I"], "want", "to"], "split"];

function recursiveSplit(array, target, offset, status = { cut: false }) {
  let left, right, index;

  for (const [i, element] of array.entries()) {
    index = i;

    if (element === target) {
      left = element.slice(0, offset);
      right = element.slice(offset);
      status.cut = true;
      break;
    }

    if (Array.isArray(element)) {
      [left, right] = recursiveSplit(element, target, offset, status);
      if (status.cut) break;
    }
  }

  return status.cut
    ? [[...array.slice(0, index), left], [right, ...array.slice(index + 1)]]
    : [array];
}

const [left, right] = recursiveSplit(input, 'array', 2);

console.log('left: ', JSON.stringify(left));
console.log('right: ', JSON.stringify(right));

- pilchard

Answer 2

在这段代码中，h 是值v的“容器”，这使得值v可以在递归的更深层次上被修改，以便修改在递归的较浅层次上可见。这个值v指示我们是否应该在输出中包含项目。

一旦找到匹配的字符串，就会翻转v的值（通过 h.v^=1实现）。这允许我们开始包含项目，然后翻转到不再包含任何项目，反之亦然。

函数f递归地访问所有数组的所有元素，并使用flatMap根据映射函数返回的空数组或非空数组来接受或拒绝元素。

我们调用f两次，一次是为了获取分割点之前的所有内容，另一次是为了获取分割点之后的所有内容。

let foo = ["this","is",[],["a",["deep",[]],["nested","array","I",[]],"want",[],"to"],"split"]

function f(x,m,p,h={v:0}) {
  return (x===m) ? [x.substring(...(h.v^=1)?[0,p]:[p])] : Array.isArray(x) ?
    [x.flatMap(i=>f(i,m,p,h))].filter(i=>!h.v||i.length) : (h.v?[]:[x])
}

function recurSplit(...g) { return [f(...g), f(...g,{v:1})].flat() }

let [x,y] = recurSplit(foo, foo[3][2][1], 2);

[foo,x,y].forEach(i=>console.log(JSON.stringify(i)))

- Andrew Parks

---

如果目标数组之前有完整的数组元素，则似乎会导致出错。例如在示例数组["this", "is", ["a", ['deep'], ["nested", "array", "I"], "want", "to"], "split"]中，结果为["this","is",["a",["deep"],["nested","ar"]]]和[[[],["ray","I"],"want","to"],"split"]，在右侧分割的开始处引入了一个空数组。 - pilchard

谢天谢地，这不是太依赖JS的啊啊！不管怎样，还是感谢这四行疯狂解决方案...虽然我需要几个小时才能理解它^^ - Florent Descroix

我已修复了空数组的问题，我认为。 - Andrew Parks

Answer 3

哦，有趣的问题，这里有一个可以处理给定字符串的多个出现版本。

它将每个元素推入新数组，直到发生分割，然后将该数组添加到最终结果中并替换为新数组。这样，您就不需要跟踪是否已发生分割。

const nested = ["this", ["endstart"], [], ["is"], "endstart", ["a", ["nested", "endstart", "endstart", "I"], "want", "to"], "split"]

function splitAtWord([el, ...rest], word, splitAt, result = [], current = []){
  if (!el) {
    return [...result, current] // push current to result
  }
  if (Array.isArray(el)) {
    const splits = splitAtWord(el, word, splitAt).map((e, i) => i === 0 ? [...current, e] : [e])
    current = splits.pop() // keep working with end of nested array
    result.push(...splits) // done with all others (if any after pop)
    return splitAtWord(rest, word, splitAt, result, current)
  }
  if (el !== word) {
    return splitAtWord(rest, word, splitAt, result, [...current, el]) // just copy to current
  }
  const left = word.substring(0, splitAt)
  const right = word.substring(splitAt)
  return splitAtWord(rest, word, splitAt, [...result, [...current, left]], [right]) // finish left side, keep working with right
}

console.log(JSON.stringify(splitAtWord(nested, 'endstart', 3)))

但如果你知道要在哪个特定索引处进行分割，那么使用它将变得更加容易:

let foo = ["this", "is", ["a", ["nested", "array", "I"], "want", "to"], "split"]

function splitAtIndex(arr, [ix, ...ixs], wordIx){
  const el = arr[ix];
  const [l,r] = Array.isArray(el) ?
    splitAtIndex(el, ixs, wordIx) : 
    [el.substring(0, wordIx), el.substring(wordIx)]
  return [[...arr.slice(0, ix), l], [r, ...arr.slice(ix+1)]]
}

console.log(JSON.stringify(splitAtIndex(foo, [2,1,1],2)))

- Moritz Ringler