生成可能的组合

Question

我有几个哈希映射,我需要生成以下组合:

A: [x->1, y->2,...]
B: [x->1, a->4,...]
C: [x->1, b->5,...]
...

一些可能的组合:

A+B; A; A+C; A+B+C...

对于每个组合,我需要生成联合散列映射,并在两个散列映射中使用相同的键执行键值对的操作.

我能想到的就是使用二进制计数器并将数字映射到相应的哈希映射:

001 -> A
101 -> A,C
...

虽然这个解决方案有效,但当我有超过100个哈希映射时,模运算很耗时.我是Scala的新手,但我相信必须有更好的方法来实现这一目标吗？

Answer 1

Scala序列具有一个combinations功能.这为您提供了从总数中选择特定数字的组合.从你的问题看起来你想要选择所有不同的数字,所以理论上的代码可能是这样的:

val elements = List('a, 'b, 'c, 'd)
(1 to elements.size).flatMap(elements.combinations).toList

/* List[List[Symbol]] = List(List('a), List('b), List('c), List('d), List('a, 'b), 
   List('a, 'c), List('a, 'd), List('b, 'c), List('b, 'd), List('c, 'd), 
   List('a, 'b, 'c), List('a, 'b, 'd), List('a, 'c, 'd), List('b, 'c, 'd), 
   List('a, 'b, 'c, 'd)) */

但正如所指出的,所有组合都会太多.使用100个元素,从100中选择2将给你4950个组合,3个给你161700,4个给你3921225,5个可能会给你一个溢出错误.因此,如果您只是将参数保持combinations为2或3,那么您应该没问题.

Answer 2

好吧,想想你的地图有多少组合:假设你有N个地图.

(the maps individually) + (pairs of maps) + (triples of maps) + ... + (all the maps)

这当然是

(N choose 1) + (N choose 2) + ... + (N choose N-1)

在哪里N choose M定义为:

N! / (M! * (N-M)!)

对于N=100和M=50,N choose M超过100,000,000,000,000,000,000,000,000,000,000这么"耗时"真的不能正确解决问题!

哦,这假设排序是无关紧要的 - 那A + B就是等于B + A.如果这个假设是错误的,那么你所面临的排列明显多于可见宇宙中的粒子

为什么scala可能会帮助解决这个问题:它的并行集合框架!