Re: [問題] 排列組合，相同物品分發制不同容器

[lovesnake (【忠犬攻一枚】)]

※ 引述《yauhh (喲)》之銘言：
: ※ 引述《lovesnake (【忠犬攻一枚】)》之銘言：
: : 我原本的想法是把物品分成三堆各一個，然後剩下假如說是兩個
: : 用字典順序排出以後，找出個數 = 剩餘物品個數的SubSet
: : 加到原本的三堆裡面...
: : 您那個想法....是說先做出單一情況，然後在排列組合，有另外6種組合
: : 最後列出全部的意思嗎?
: : 不過列出單一情況這邊的演算法就卡住了Orz
: : 1 1 6
: : 1 2 5
: : 1 3 4
: : 2 1 5
: : 2 2 4
: : 2 3 3
: : 這是所有的相同東西分到相同堆的結果
: : 該怎麼用演算法跑出這樣的結果呢?
: 這部份應該是簡單到不需要講的吧. 方法很明確,只看你程式會不會寫而已.
: 對總和8來說,要分為三個數字,因為每個數字至少為1,所以每個數字最多填到6.
: 所以這是六取三排列,但限定總和為8.

阿...用while寫的話，會跑到
1 1 6
1 2 5
1 3 4
2 1 5
2 2 4
2 3 3
3 1 4 (重複了)

相等於 八個相同的東西分到三個相同的容器裡
這好像只能列舉....(可能我數學比較爛)
所以變成每一次做出一種組合都要去判斷是否跟前面的組合有重複
不知道是否是這樣呢?
關於六取三排列...不太懂..您說的是P(6 3)嗎?

: : 且如果用出另外六組組合，也會有重複的必須做後面的剔除動作
: : 可能有耗效能之嫌 (雖然微不足道啦)
: : 對您的想法不了解的大概這兩點，謝謝!!
: 所謂重複,是什麼重複,堆的重複或者是東西的重複?
: 我以為你是拿那些東西雖然每個都相同,但彼此仍視為不同 (如東西上有打編號之類)
: 如果是把東西全都看成相同,分堆會變得比較簡單,甚至不用分了, 1 1 6 就是一種分堆
: 情況, 1 2 5 是第二種情況, ......等.

我所說的重複情況是 2 2 4
排出六種
2 2 4
2 2 4
2 4 2
2 4 2
4 2 2
4 2 2
有一半會是重複的，需要在判斷。

因為原題目是---相同的東西分到不同的容器，也就是H。
變成 H(3 8) = (10 2) = 45種 這樣
所以
2 2 4
4 2 2
2 4 2
這三種是不同的情況

謝謝!!

--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 140.121.216.68
→ yauhh:但你原文不是說分到不同容器所以有差別?
→ yauhh:3 1 4 對 1 3 4 並沒有重複
→ lovesnake:對阿~ 134是不會重複 但224會重複
→ lovesnake:對阿~分到不同容器所以有差別
→ lovesnake:所以224 跟422跟242 這三種是不一樣的
→ lovesnake:組合阿~ 所以才會有重複
→ lovesnake:因為三個東西做組合會有六組
→ lovesnake:勢必會有 224 224 (程式裡跑出來)
→ lovesnake:242 242 422 422 這六組 其中兩兩重複
→ lovesnake:大概是這樣 ((我幹嘛不用編輯Orz
→ yauhh:那你422之後怎麼還會出現422?
→ yauhh:我覺得422之後應該是431然後就到512了
喔~ 可能是有誤解....我以為你是先做出八個相同的分三個相同的堆
然後再去排列
您說的是直接將後面的元素列為一個集合，隨時修改他的極限值嗎?
像是 10個分4堆

{1 [1 (1 7)]} 這樣嗎?
最後一個Set總和八
第二個總和九
第一個總和十
然後最後一個SET組合都跑完了以後第二個SET+1 最後一個SET總和-1
繼續跑?

※ 編輯: lovesnake       來自: 140.121.216.68       (04/14 11:54)
→ yauhh:喔我搞錯了. P(6,3).
那種想法我有想過，可是程式該怎麼實作呢?
當初想到這個想法我以為有解了...結果程式寫不出來XD
懇請賜教
※ 編輯: lovesnake       來自: 140.121.216.68       (04/14 11:55)
推 EdisonX:換句話說,就是分割數問題嗎？
※ 編輯: lovesnake       來自: 140.121.216.68       (04/14 14:25)
→ lovesnake:不太一樣窩...分割數是相同堆 這是不同
→ lovesnake:不過這名詞好像查的到很多東西XD 感謝
→ yauhh:我原本想法應該沒錯,第一個數字取4,則第二個
→ yauhh:數字可以是1或2或3,取了2,則第三個數字只會2