使用乘法获得整数的独特组合的算法

我得到了一堆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。

有人可以提出一个算法来做到这一点？

来源

2010-11-12 chappar

作业？一个比赛？对于现实生活中的问题听起来有些过于虚构。 – Bolo 2010-11-12 18:55:36

对于我试图解决的投影仪问题:-)。有一个暴力方法，但我不满意。 – chappar 2010-11-12 19:00:43

因为这里的一个被乘数超过10. – chappar 2010-11-12 19:08:55

该解决方案可以递归构建。将输入视为一个数字列表，如[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]

来源

2010-11-12 19:17:42

错过了一些有效的组合，例如'[8，6，9]'。我想你想在范围（1，len（d）+ 1）中为'prefix_len：'。 – 2010-11-13 00:59:46

这不会打印所有组合。例如：对于列表[2，2，3，3]，它不会打印[6,6] – chappar 2010-11-13 06:05:39

@matthew感谢您指出了这一点。它是固定的。 @chapprar我认为OP不希望列表中数字的切换次序，所以[4,9]有效，而[6,6]不是。这只是我的假设。 – 2010-11-13 22:01:47

如果为了事项（即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使用，如果列表可以分为元素x 。剩下的，stuffNil是空列表）

这是在行动：

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) + 
     ....

所以你从最后一项开始 - 只有一种可能性 - 然后按顺序使用这个公式。（如果这是你以后的事情，我会写代码，但希望算法足够清晰。）

来源

2010-11-12 19:35:29

使用乘法获得整数的独特组合的算法

回答

相关问题