遍历数组中的所有可能的值，总共给出1

我有一个4值的数组。例如：[0.1, 0.1, 0.5, 0.3]（元素的总和= 1）如何虽然迭代与增量0.1所有可能的值，以获得总和1.遍历数组中的所有可能的值，总共给出1

例如：

[1.0, 0.0, 0.0, 0,0] 
[0.9, 0.1, 0.0, 0,0] 
[0.9, 0.0, 0.1, 0,0] 
...... 
[0.7, 0.2, 0.0, 0,1]

优选地在Python或Java。或伪

来源

2014-10-02 Elizaveta Ivanova

这是硬币值为0.0,0.1,0.2，...，0.9,1.0的[硬币问题]（http://en.wikipedia.org/wiki/Coin_problem）。 – isedev 2014-10-02 19:35:39

你可以把它看成是找到10的整数分区（然后把每个分区的值除以10得到0.1,0.2等）。搜索“整数分区”的网页应该会出现很多匹配。 – 2014-10-03 17:49:16

这不是硬币问题（如链接）。这也比整数分区简单，因为我们不在寻找排序的排列。 – Teepeemm 2014-10-09 14:03:52

只是算法解释看一看和itertools.permutations：

import itertools 
allPermutations = itertools.permutations([0.0,0.1,0.2,0.3,0.4,0.5,0.6,0.7,0.8,0.9,1.0]*4, 4) 
Sum1Permutations = [x for x in allPermutations if sum(x) == 1]

由于@HuStmpHrrr指出，这是使用蛮力解决问题。产生所有这些增加1.0置换算法是这样的一个：

Sum1Permutations = [] 
for x in range(10): 
    for y in range(10-x+1): 
     for z in range(10-x-y+1): 
      Sum1Permutations.append([float(x)/10, float(y)/10, float(z)/10, float(10 - x - y - z)/10])

或者，使用列表理解：

Sum1Permutations = [[float(x)/10,float(y)/10,float(z)/10,float(10-x-y-z)/10] for x in range(10) for y in range(10-x+1) for z in range(10-x-y+1)]

来源

2014-10-02 20:34:54

这不聪明。这是蛮力搜索。 – HuStmpHrrr 2014-10-02 20:57:23

列表理解错过了许多排列，例如[0.8,0.2,0.0,0.0] – Paddy3118 2014-10-03 17:38:35

正确，边界存在问题。我修复了它。 – 2014-10-03 17:47:43

尝试dollowing列表理解：

>>> from itertools import product 
>>> s = [list(p/10. for p in prd) 
     for prd in product(range(11), repeat=4) if sum(prd) == 10] 
>>> len(s) 
286 
>>> [0.,1.,0.,0.] in s 
True 
>>> [.8,.2,.0,.0] in s 
True 
>>>

这里需要的是itertools.product。

来源

2014-10-03 18:06:39 Paddy3118

这仍然是蛮力。一种pythonic蛮力，但仍然。 – Teepeemm 2014-10-09 12:16:51

这基本上是一个整数问题作为一个浮点问题。它可以作为一个 FP问题来解决，但float表示的不精确性和Python内置的不可能性如range到提供浮点范围使其更加困难。因此，在整洁的精确整数领域中更容易解决它，然后将结果显示为浮点值。

可以生成所有可能的值组合，然后测试它们是否总和为目标值。这就是其他一些建议的解决方案。但这是一个有点蛮力。也有可能只生成这些向量/列表总和为目标值。该解决方案通过递归的生成器来完成。

def vectors(length, target): 
    """ 
    Generate all lists of whole numbers of given 
    length that add up to the target value. 
    """ 
    if length == 1: 
     yield [target] 
    else: 
     for firstval in range(target+1): 
      for rest in vectors(length-1, target-firstval): 
       yield [firstval] + rest 

TARGET=10 
LENGTH=4 
for vec in vectors(LENGTH, TARGET): 
    print [ v/float(TARGET) for v in vec ]

这产生了：

[0.0, 0.0, 0.0, 1.0] 
[0.0, 0.0, 0.1, 0.9] 
[0.0, 0.0, 0.2, 0.8] 
... 
[0.9, 0.0, 0.0, 0.1] 
[0.9, 0.0, 0.1, 0.0] 
[0.9, 0.1, 0.0, 0.0] 
[1.0, 0.0, 0.0, 0.0]

来源

2014-10-06 23:06:27

相反的值的，假装要拨打4子区间长度成1的间隔然后将四个值是由那些子间隔的三个端点精确地确定。

from itertools import combinations_with_replacement as cwr 

for (one,onetwo,onetwothree) in cwr(range(11),3): 
    print([one/10,(onetwo-one)/10,(onetwothree-onetwo)/10,(10-onetwothree)/10])

来源

2014-10-09 14:10:12 Teepeemm

遍历数组中的所有可能的值，总共给出1

回答

相关问题