Re: [問題] 數學 組合的問題
※ 引述《l314520 (一生一世我愛你)》之銘言：
: 遇到的問題： (題意請描述清楚)
: 不知道該怎麼去寫這個程式
: 我想配的是，例如說我給五組字串
: apple
: banana
: grape
: peach
: orange
: 然後我要組成
: I love apple, banana, grape, peach, orange
: 這個是C5取5的情況
: 假設是C5取1就是
: I love apple
: I love banana
: I love grape
: I love peach
: I love orange
: 變成五行
: C5取2 = 10
: I love apple, banana
: I love apple, grape
: I love apple, peach
: I love apple, orange
: I lvoe banana, grape
: I love banana, peach
: I love banana, orange
: I love grape, peach
: I love grape, orange
: I love peach, orange
: 有沒有什麼好的演算法可以去運算這個呢
: 印象中老師有教過dynamic programming可以處理這種問題
: 不過我一直都沒學會 囧 太混
以 C(n, m) 表示 Cn 取 m 的數量。
C(n, m) =
C(n-1, m-1) <===== 選取了第一個
+
C(n-1, m) <===== 第一個不選取
在設計產生 Cn 取 m 的所有結果也可以使用同樣的概念去做。
例如以 Python 來實作：
def combin(sam, n):
if len(sam) == n: return [list(sam[:])]
if n == 1:
return [[x] for x in sam]
a = sam[0]
c1 = [[a] + x for x in combin(sam[1:], n - 1)]
c2 = combin(sam[1:], n)
return c1 + c2
def list_combin(sample, n):
for x in combin(sample, n):
print ' '.join(x)
S=['apple', 'banana', 'graph', 'peach', 'orange']
list_combin(S, 2)
output:
apple banana
apple graph
apple peach
apple orange
banana graph
banana peach
banana orange
graph peach
graph orange
peach orange
list_combin(S, 3)
output:
apple banana graph
apple banana peach
apple banana orange
apple graph peach
apple graph orange
apple peach orange
banana graph peach
banana graph orange
banana peach orange
graph peach orange
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 218.173.144.174
※ 編輯: sbrhsieh 來自: 218.173.144.174 (01/20 14:44)
討論串 (同標題文章)