利用乘法求整数唯一组合的算法

解决方案可以递归地构建。将输入看作一个数字列表,如[2,2,2,2,3,3,3]。将列表分成前缀(例如[2,2])和相应的后缀(在本例中为[2,2,3,3])。现在,将前缀中的条目进行多个(在本例中我们得到4个),并递归地解决后缀的相同问题。将值从多重性插入到后缀的每个解的开头,我们就得到了原始问题的答案。

在下面的Python代码中,递归逻辑在函数中定义 collapse ,它查找所有有效的前缀(其多重性小于10),并将多重性插入到在删除前缀后折叠剩余数据时返回的所有结果中( collapse(d[prefix_len:]) ).

a = [2,2,2,2,3,3,3]

def collapse(d):
    if len(d) > 0:
        for prefix_len in range(1, len(d) + 1):
            prefix = reduce(lambda x,y: x*y, d[:prefix_len], 1)
            if prefix > 10:
                break
            for suffix in collapse(d[prefix_len:]):
                yield [prefix] + suffix
    else:
        yield d

for i in collapse(a):
    print i

输出为

[2, 2, 2, 2, 3, 3, 3]
[2, 2, 2, 2, 3, 9]
[2, 2, 2, 2, 9, 3]
[2, 2, 2, 6, 3, 3]
[2, 2, 2, 6, 9]
[2, 2, 4, 3, 3, 3]
[2, 2, 4, 3, 9]
[2, 2, 4, 9, 3]
[2, 4, 2, 3, 3, 3]
[2, 4, 2, 3, 9]
[2, 4, 2, 9, 3]
[2, 4, 6, 3, 3]
[2, 4, 6, 9]
[2, 8, 3, 3, 3]
[2, 8, 3, 9]
[2, 8, 9, 3]
[4, 2, 2, 3, 3, 3]
[4, 2, 2, 3, 9]
[4, 2, 2, 9, 3]
[4, 2, 6, 3, 3]
[4, 2, 6, 9]
[4, 4, 3, 3, 3]
[4, 4, 3, 9]
[4, 4, 9, 3]
[8, 2, 3, 3, 3]
[8, 2, 3, 9]
[8, 2, 9, 3]
[8, 6, 3, 3]
[8, 6, 9]

如果顺序很重要(即2*4*2和2*2*4不一样),你必须列出它们(即“生成”),那么你应该递归地全部完成。在斯卡拉:

def combine(who: List[Int], limit: Int=10): List[List[Int]] = who match {
  case x :: y :: more =>
    combine(y :: more, limit).map(x :: _) :::
    (if (x*y<limit) combine((x*y) :: more, limit) else Nil)
  case x :: Nil => List(who)
  case Nil => List()
}

你可能不了解Scala,下面是这三个案例的工作原理。第一种情况:列表至少还有两个元素。选取第一个元素并将其添加到所有可能的后续组合中。那么, 如果 您可以合并第一个和第二个元素,然后查找以该元素开头的列表的所有组合。第二种情况:只有一个元素的平凡列表;将其作为列表中的唯一元素返回。第三种情况:退化输入(没有给定值);返回空列表。

(在斯卡拉, ::: 将两个列表连接在一起,而 x :: list 棍枝 x 在前面 list . 当你匹配时,它会反过来: case x :: stuff 如果列表可以分解为元素,则使用 十 其余的, stuff . Nil 是空列表。)

这就是它的作用:

scala> combine( List(2,2,2,2,3,3,3) )

res18: List[List[Int]] = List(List(2, 2, 2, 2, 3, 3, 3), List(2, 2, 2, 2, 3, 9),
  List(2, 2, 2, 2, 9, 3), List(2, 2, 2, 6, 3, 3), List(2, 2, 2, 6, 9),
  List(2, 2, 4, 3, 3, 3), List(2, 2, 4, 3, 9), List(2, 2, 4, 9, 3),
  List(2, 4, 2, 3, 3, 3), List(2, 4, 2, 3, 9), List(2, 4, 2, 9, 3), List(2, 4, 6, 3, 3),
  List(2, 4, 6, 9), List(2, 8, 3, 3, 3), List(2, 8, 3, 9), List(2, 8, 9, 3),
  List(4, 2, 2, 3, 3, 3), List(4, 2, 2, 3, 9), List(4, 2, 2, 9, 3), List(4, 2, 6, 3, 3),
  List(4, 2, 6, 9), List(4, 4, 3, 3, 3), List(4, 4, 3, 9), List(4, 4, 9, 3),
  List(8, 2, 3, 3, 3), List(8, 2, 3, 9), List(8, 2, 9, 3), List(8, 6, 3, 3), List(8, 6, 9))

编辑:如果你只是想数数,你可以使用不同类型的重复。让 S(n) 是从 n 向前,让 L(n) 是 n个 你名单上的第项。那么

S(i) = S(i+1) +
       if (L(i)+L(i+1)<10) S(i+2) +
       if (L(i)+...+L(i+2)<10) S(i+3) +
       ....

所以你从最后一项开始——只有一种可能性——然后按照这个公式的顺序反向工作。(如果这正是您所追求的,我将编写实现它的代码,但希望算法足够清晰。)