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

看板Programming作者 (【忠犬攻一枚】)時間12年前 (2012/04/14 11:31), 編輯推噓1(1017)
留言18則, 3人參與, 最新討論串5/11 (看更多)
※ 引述《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

04/14 11:43, , 1F
但你原文不是說分到不同容器所以有差別?
04/14 11:43, 1F

04/14 11:44, , 2F
3 1 4 對 1 3 4 並沒有重複
04/14 11:44, 2F

04/14 11:45, , 3F
對阿~ 134是不會重複 但224會重複
04/14 11:45, 3F

04/14 11:46, , 4F
對阿~分到不同容器所以有差別
04/14 11:46, 4F

04/14 11:46, , 5F
所以224 跟422跟242 這三種是不一樣的
04/14 11:46, 5F

04/14 11:46, , 6F
組合阿~ 所以才會有重複
04/14 11:46, 6F

04/14 11:47, , 7F
因為三個東西做組合會有六組
04/14 11:47, 7F

04/14 11:47, , 8F
勢必會有 224 224 (程式裡跑出來)
04/14 11:47, 8F

04/14 11:47, , 9F
242 242 422 422 這六組 其中兩兩重複
04/14 11:47, 9F

04/14 11:48, , 10F
大概是這樣 ((我幹嘛不用編輯Orz
04/14 11:48, 10F

04/14 11:48, , 11F
那你422之後怎麼還會出現422?
04/14 11:48, 11F

04/14 11:49, , 12F
我覺得422之後應該是431然後就到512了
04/14 11:49, 12F
喔~ 可能是有誤解....我以為你是先做出八個相同的分三個相同的堆 然後再去排列 您說的是直接將後面的元素列為一個集合,隨時修改他的極限值嗎? 像是 10個分4堆 {1 [1 (1 7)]} 這樣嗎? 最後一個Set總和八 第二個總和九 第一個總和十 然後最後一個SET組合都跑完了以後第二個SET+1 最後一個SET總和-1 繼續跑? ※ 編輯: lovesnake 來自: 140.121.216.68 (04/14 11:54)

04/14 11:51, , 13F
喔我搞錯了. P(6,3).
04/14 11:51, 13F
那種想法我有想過,可是程式該怎麼實作呢? 當初想到這個想法我以為有解了...結果程式寫不出來XD 懇請賜教 ※ 編輯: lovesnake 來自: 140.121.216.68 (04/14 11:55)

04/14 13:27, , 14F
換句話說,就是分割數問題嗎?
04/14 13:27, 14F
※ 編輯: lovesnake 來自: 140.121.216.68 (04/14 14:25)

04/14 14:28, , 15F
不太一樣窩...分割數是相同堆 這是不同
04/14 14:28, 15F

04/14 14:28, , 16F
不過這名詞好像查的到很多東西XD 感謝
04/14 14:28, 16F

04/14 18:05, , 17F
我原本想法應該沒錯,第一個數字取4,則第二個
04/14 18:05, 17F

04/14 18:06, , 18F
數字可以是1或2或3,取了2,則第三個數字只會2
04/14 18:06, 18F
文章代碼(AID): #1FYE-9xE (Programming)
討論串 (同標題文章)
本文引述了以下文章的的內容:
以下文章回應了本文
完整討論串 (本文為第 5 之 11 篇):
文章代碼(AID): #1FYE-9xE (Programming)