Javascript 数组递归题——遍历"sections"

Question

我正在为 Javascript 苦苦思索如何找到深度为 n 的数组源的所有组合，该数组源被分成多个部分（下例中为 0、1 和 2）。我想以每一种可能的组合结束 - 每个 returned 数组应该包含每个组中的一个且只有一个值。我已经将解决方案硬编码为 4 个级别，但需要更大的灵活性——递归提供的灵活性。我已经查看了 of possible recursive solutions，虽然我了解这些工作原理，但我只是想不通如何让这个特定的源数据发挥作用。

sourceArr=[
     [0,60,100]
    ,[0,60,200]
    ,[0,66,300]
    ,[1,69,500]
    ,[2,70,600]
    ,[2,70,700]
    ,[2,77,800]
    ,[2,77,900]
]

预期 return 值...

[
    [{60,100],{69,500},{70,600}]
    ,[{60,100],{69,500},{70,700}]
    ,[{60,100],{69,500},{77,800}]
    ,[{60,100],{69,500},{77,900}]
    ,[{60,200],{69,500},{70,600}]
    ,[{60,200],{69,500},{70,700}]
    ,[{60,200],{69,500},{77,800}]
    ,[{60,200],{69,500},{77,900}]
    ,[{66,300],{69,500},{70,600}]
    ,[{66,300],{69,500},{70,700}]
    ,[{66,300],{69,500},{77,800}]
    ,[{66,300],{69,500},{77,900}]
]

Answer 1

本质上，这是一个cartesian product问题。但是您必须首先处理它，因为您没有想要分组到单独数组中的元素。因此，首先，您需要按第一个元素对数组进行分组，然后去掉第一个元素。

如果我们使用一些简单的实用函数，我们可以写一个像这样的简单版本：

const combine = pipe (
  group (head),
  map (map (tail)),
  cartesian
)

这里我们 pipe 将许多函数组合在一起，创建一个新函数，它接受一些输入，将其发送到第一个函数，然后将那个输出发送到第二个函数，以及到第三个，依此类推，返回最终输出。

我们在此管道中提供的第一个函数 group 是根据应用于每个元素的 head 函数的结果提供到数组中的元素（这只是 returns 第一个元素一个数组。）这将为我们留下这样的结构：

[
  [[0, 60, 100], [0, 60, 200], [0, 66, 300],
  [[1, 69, 500]],
  [[2, 70, 600], [2, 70, 700], [2, 77, 800], [2, 77, 900]]
]

接下来我们使用嵌套的 map 调用，将 tail 传递给最里面的那个。 tail 只是 returns 除了数组的第一个元素之外的所有内容。这会将上面的转换为

[
  [[60, 100], [60, 200], [66, 300],
  [[69, 500]],
  [[70, 600], [70, 700], [77, 800], [77, 900]]
]

现在这是供 Cartesian product 函数使用的格式，所以我们包含一个简单的 cartesian 函数，我们就完成了。

我们可以这样写那些助手：

// utility functions
const head = (xs) => xs [0]
const tail = (xs) => xs .slice (1)
const map = (fn) => (xs) =>
  xs .map (x => fn (x))
const pipe = (...fns) => (x) =>
  fns .reduce ((a, fn) => fn (a), x)
const group = (fn) => (xs) =>
  Object .values (xs .reduce (
    (a, x, _, __, k = fn (x)) => ((a[k] = [...(a[k] || []), x]), a), 
    {}
  ))
const cartesian = ([xs, ...xss]) =>
  xs == undefined
    ? [[]]
  : xs .flatMap (x => cartesian (xss) .map (ys => [x, ...ys]))

// main function
const combine = pipe (
  group (head),
  map (map (tail)),
  cartesian
) 

// sample data
const sourceArr = [[0, 60, 100], [0, 60, 200], [0, 66, 300], [1, 69, 500], [2, 70, 600], [2, 70, 700], [2, 77, 800], [2, 77, 900]]

// demo  -- stringify is to avoid SO's id-ref presentation
console .log (JSON.stringify(combine (sourceArr), null, 4))

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

请注意，为了做到这一点，我使用了我身边的功能。写这个答案所花的时间比编写代码所花的时间要长得多。这就是维护您可以根据需要获取的可重用函数库的优势。

这些特定的 API 与 Ramda 的设计类似。这并不奇怪，因为我是 Ramda 的创始人和维护者，但我们自己创建和维护它们很简单。

Javascript 数组递归题——遍历"sections"

Javascript array recursion question - looping through "sections"

javascript

arrays

recursion

nested

nested-loops