遍歷數組中的所有可能的值，總共給出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

回答

相關問題