algorithm - 可变长度元组的集合和具有多个值的映射到加权组合

Question

这个问题来自“Scala 中的函数式编程原则”@Coursera，所以我需要避免在这个问题中使用完整的代码——它已经过了最后期限，但总有几年的时间。我一直在寻找有关实现此转换的方法的一般性建议。

我有一组可变长度的元组，一些小写字符串的完整子集

val indexes = Set('a', 'b', 'c')

和一组元组，每个字符允许出现次数最多

val occurences = Set(('a', 1), ('b', 5), ('c', 2))

我想获得加权元组的组合:

val result = Seq(Set(), Set((a, 1)), Set((b, 1)), Set((b, 2)) ... Set((a, 1 )(b, 2)(c, 2)) ...)

我的作业建议通过递归迭代构建结果的简单方法。

我想用更“结构化”的方式来做？方式。我的想法是获取所有可能的 char 子集，并多路复用那些增加了权重的子集(〜帖子最后一行中的伪代码)。

我通过 subsets 运算符得到了子集

val subsets = Seq(Set(), Set(a), Set(b), Set(c), Set(a, b), Set(a, c), Set(b, c) , 设置(a, b, c)

还有每个字符的特定 Int 值的映射，

val weightsMax Map(a -> 1, b -> 5, c -> 2)

val weightsAll Map(a -> List(1), b -> List(5,4,3,2,1), c -> List(2,1))

我真的不知道我应该为这个操作使用哪种语言功能。 我知道 for 和集合操作，但没有在这个级别上操作这些操作的经验，因为我是函数范式(以及集合操作)的新手。 我不介意制作一些公司风格的 java/XML 来解决这个问题(是的......)。

我想定义类似的东西:

FOREACH 子集(将字符映射到(字符的权重组合))

Answer 1

您可以递归地表达这个问题并以这种方式实现它。我们想构建一个名为 expend 的函数:Set[Char] => List[Set[(Char, Int)]] 返回一组字符的所有可能的权重组合(您编写的chars TO (COMBINATIONS OF weights FOR chars)).直观的“根据定义”方式是将每个可能的权重分配给第一个字符，然后将每个可能的权重分配给第二个字符，依此类推...

def expend(set: Set[Char]): List[Set[(Char, Int)]] =
  if(set isEmpty) Nil else
  allPairsFromChar(set head) flatMap (x => expend(set tail) map (_ + x))

其中 allPairsFromChar 与您的 weightsAll 无关，而您的 FOREACH 子集 (...) 是另一个 flatMap ;)