使用乘法获得唯一整数组合的算法

Question

我有一堆 2 和 3，我必须将它们相乘。现在我想生成这些数字的每个唯一组合，这样当这些组合相乘时不超过 10。

例如，我有这样的东西。

2*2*2*2*3*3*3

我可以从上面得到以下有效组合。

4*4*9*3
8*6*9
4*2*6*9

但下面的组合是错误的。 16*3*9 和 4*4*27。

有人可以建议一种算法来做到这一点吗？

Answer 1

该解决方案可以递归地建立。将输入视为数字列表，例如 [2,2,2,2,3,3,3]。将列表分为前缀（例如 [2,2]）和相应的后缀（本例中为 [2,2,3,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]

Answer 2

如果顺序很重要（即 2*4*2 与 2*2*4 不同）并且您必须列出它们（即“生成”），那么您应该递归地执行所有操作。 In Scala：

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，因此以下是这三种情况的工作原理。第一种情况：列表至少还剩下两个元素。挑选第一个元素并将其添加到所有可能的后续组合中。然后，如果您可以合并第一个和第二个元素，那么就这样做，并找到以此开头的列表的所有组合。第二种情况：只有一个元素的简单列表；将其作为列表中唯一的内容返回。第三种情况：简并输入（没有给出值）；返回一个空列表。

（在 Scala 中，::: 将两个列表连接在一起，而 x :: list 将 x 粘贴在 listx和其余元素，则使用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) 为 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) +
       ....

，您从最后一项开始（只有一种可能性），然后使用此公式按顺序倒退。 （如果这就是您想要的，我将编写执行此操作的代码，但希望该算法足够清晰。）