JavaScript中多个数组的条件笛卡尔积

jhkqcmku  于 2023-08-02  发布在  Java
关注(0)|答案(2)|浏览(111)

我想做的事情可能比我想象的要复杂。问题的前提如下:
鉴于:

  • let params = [[1,2,3], ["A","B","C"], [10,11,12]]
  • let pairRestrictions: {0:{2:{1:["A","B"]}}}

其中第一个:

  • key 0:参数的索引
  • 键2:第一个参数的值
  • 键1:第二参数的索引
  • ["A","B"]:第二个参数可以得到的可能值。

我想写一个计算params的笛卡尔积的算法。关于所给的条件。
因此,假设创建这些组合的函数被调用:

generateCombinations(params, pairRestrictions)

字符串
此函数应返回:

let result = [
  [1, 'A', 10], [1, 'A', 11], [1, 'A', 12],
  [1, 'B', 10], [1, 'B', 11], [1, 'B', 12],
  [1, 'C', 10], [1, 'C', 11], [1, 'C', 12],
  [2, 'A', 10], [2, 'A', 11], [2, 'A', 12],
  [2, 'B', 10], [2, 'B', 11], [2, 'B', 12],
  [3, 'A', 10], [3, 'A', 11], [3, 'A', 12],
  [3, 'B', 10], [3, 'B', 11], [3, 'B', 12],
  [3, 'C', 10], [3, 'C', 11], [3, 'C', 12]
]


提前感谢!
我可以创建笛卡尔积的代码段,但我不能设法有条件的一部分。
这是我目前使用的解决方案:

function recur(combinations = [], i) {
  let res = [];
  if (i === params.length) {
    return combinations;
  }
  for (let p in params[i]) {
    let combinationsCopy = [];
    for (let c in combinations) {
      combinationsCopy.push(combinations[c].concat(params[i][p]));
    }
    res = res.concat(combinationsCopy);
  }
  return recur(res, i + 1);
}
recur(
    params[0].map((x) => [x]),
    1
  );

brqmpdu1

brqmpdu11#

更新:切换到更高效的cartesian实现。

我们可以将您的限制转换为 predicate 函数数组,然后过滤在输入上调用cartesian函数的结果,以仅包含与所有这些 predicate 匹配的值。

const cartesian = ([xs, ...xss]) => ((kids) =>
  xs == undefined ? [[]] : xs .flatMap (x => kids .map (ys => [x, ...ys]))
)(xs && cartesian(xss))

const generateCombinations = (
  params, pairRestrictions, 
  fns = Object.entries(pairRestrictions).flatMap(
    ([k0, v0]) => Object.entries(v0).flatMap(
      ([k1, v1]) => Object.entries(v1).flatMap ( 
        ([k2, v2]) => (xs) => xs[k0] == k1 ? v2.includes(xs[k2]) : true
      )
    )
  )
) => cartesian(params).filter(xs => fns.every(fn => fn(xs)))

const params = [[1, 2, 3], ["A", "B", "C"], [10, 11, 12]]
const pairRestrictions1 = {0: {2: {1: ["A", "B"]}}}

const results1 = generateCombinations(params, pairRestrictions1)

console.log('If col 0 is 2, then col 1 must be "A" or "B":')
console.log(results1.map(r => `[${r.join(', ')}]`).join('\n'))

const pairRestrictions2 = {0: {2: {1: ["A", "B"]}, 3: {2: [11, 12]}}, 1: {C: {0: [1, 2]}}}

const results2 = generateCombinations(params, pairRestrictions2)
console .log ('------------------------------------------------------------')
console.log('If col 0 is 2, then col 1 must be "A" or "B"  AND')
console.log('If col 0 is 3, then col 2 must be 11 or 12  AND')
console.log('If col 1 is "C", then col 0 must be 1 or 2:')
console.log(results2.map(r => `[${r.join(', ')}]`).join('\n'))

个字符
我假设你的限制是累积的。如果你想包含所有符合 any 限制的值,那么你可以用.some替换函数最后一行的.every
因此,对于这样的pair限制对象:

{0: {2: {1: ["A", "B"]}, 3: {2: [11, 12]}}, 1: {C: {0: [1, 2]}}}


我们将得到以下三个函数的等价物:

(xs) => xs[0] == 2 ? ['A', 'B'].includes(xs[1]) : true
(xs) => xs[0] == 3 ? [11, 12].includes(xs[2]) : true
(xs) => xs[1] == 'C' ? [1, 2].includes(xs[0]) : true


如果我们更喜欢一个更短但不太明确的等价物,比如:

(xs) => xs[0] != 2 || ['A', 'B'].includes(xs[1])
(xs) => xs[0] != 3 || [11, 12].includes(xs[2])
(xs) => xs[1] != C || [1, 2].includes(xs[0])


我们可以将函数中的关键行替换为:

([k2, v2]) => (xs) => xs[k0] != k1 || v2.includes(xs[k2])


请注意,整个限制配置技术有一个明显的局限性:我们测试的值,除了在最深的数组中,不能有任意类型:它们必须作为对象键工作。这意味着,字符串,数字,还有,我猜,符号。任何其他类型都会失败。

8oomwypt

8oomwypt2#

可能不是对象

条件逻辑和布尔表达式可以表示复杂的思想,这些思想很难用基于对象的编码完全捕获。
如果col 0是2,那么col 1必须是“A”或“B”:

let pairRestrictions: {0:{2:{1:["A","B"]}}}

字符串
在JavaScript中捕获条件逻辑的自然方法是一个函数-

function *myfilter(p) {
  for (const [x, y, z] of p) {  // destructure columns
    if (x == 2)
      if (y != "A" && y != "B") // or !["A","B"].includes(y), 
        continue
    yield [x, y, z]
  }
}


使用简单的product生成器-

function *product(a, ...more) {
  if (a == null) return yield []
  for (const v of a)
    for (const c of product(...more))
      yield [v, ...c]
}


让我们对产品进行筛选,看看结果--

function *myfilter(p) {
  for (const [x, y, z] of p) {
    if (x == 2)
      if (y != "A" && y != "B")
        continue
    yield [x, y, z]    
  }
}

function *product(a, ...more) {
  if (a == null) return yield []
  for (const v of a)
    for (const c of product(...more))
      yield [v, ...c]
}

const data = [[1, 2, 3], ["A", "B", "C"], [10, 11, 12]]

for (const p of myfilter(product(...data)))
  console.log(p.join(","))
.as-console-wrapper { min-height: 100%; top: 0; }
1,A,10
1,A,11
1,A,12
1,B,10
1,B,11
1,B,12
1,C,10
1,C,11
1,C,12
2,A,10
2,A,11
2,A,12
2,B,10
2,B,11
2,B,12
3,A,10
3,A,11
3,A,12
3,B,10
3,B,11
3,B,12
3,C,10
3,C,11
3,C,12

逻辑蕴涵

上面我们用否定来过滤掉,但也许你想得更多 “如果x =..然后如果y =..",即logical implication,即x implies y -

function implies(a, b) {
  return a ? b : true
}

function *myfilter(p) {
  for (const [x, y, z] of p) {
    if (implies(x == 2, y == "A" || y == "B")) // ✅ positive
      yield [x, y, z]
  }
}

function *product(a, ...more) {
  if (a == null) return yield []
  for (const v of a)
    for (const c of product(...more))
      yield [v, ...c]
}

const data = [[1, 2, 3], ["A", "B", "C"], [10, 11, 12]]

for (const p of myfilter(product(...data)))
  console.log(p.join(","))
.as-console-wrapper { min-height: 100%; top: 0; }

我们可以看到被测物体的极限-
如果col 0是2,则col 1必须是“A”或“B”,并且
如果col 0为3,则col 2必须为11或12,并且
如果col 1是“C”,则col 0必须是1或2:

const pairRestrictions2 = {0: {2: {1: ["A", "B"]}, 3: {2: [11, 12]}}, 1: {C: {0: [1, 2]}}}


相比之下,蕴涵帮助我们编写正过滤器,我们的表达式可以很容易地组合起来表示更复杂的逻辑-

.as-console-wrapper { min-height: 100%; top: 0; }
1,A,10
1,A,11
1,A,12
1,B,10
1,B,11
1,B,12
1,C,10
1,C,11
1,C,12
2,A,10
2,A,11
2,A,12
2,B,10
2,B,11
2,B,12
3,A,11
3,A,12
3,B,11
3,B,12

自由思考

或者如果你用否定的方式思考,你可以这样写,达到同样的效果-

function *myfilter(p) {
  for (const [x, y, z] of p) {
    if (x == 2)
      if (y != "A" && y != "B")
        continue
    if (x == 3)
      if (z != 11 && z != 12)
        continue 
    if (y == "C")
      if(x != 1 && x != 2)
        continue
    yield [x, y, z]    
  }
}

灵活性

能力组成(分解隐含!)过滤器允许增加灵活性,并且当顺序可能很重要时可以排序-

function *filter1(p) {
  for (const [x, y, z] of p)
    if (
      implies(x == 2, y == "A" || y == "B") &&
      implies(x == 3, z == 11 || z == 12)
    ) yield [x, y, z]
}

function *filter2(p) {
  for (const [x, y, z] of p) {
    if (y == "C")
      if(x != 1 && x != 2)
        continue
    yield [x, y, z]    
  }
}
for (const [x,y,z] of filter1(filter2(product(...input))))
  // ...

for (const [x,y,z] of filter2(filter1(product(...input))))
  // ...

生成器

即使您看到多个for循环,生成器也是惰性运行的,因此每个产生的值都是临时处理的。这使得它们成为组合数学或其他大型数据集的良好选择,在这些数据集中,当元素变得可用时,调用者可以立即访问它们。相比之下,数组是有限的,必须在调用方获得对任何元素的访问权之前进行完整计算。
还有一个优化的product函数,我们一直在使用!详情请参见this Q&A

相关问题