作者chris70211 (克里斯)
看板C_Sharp
标题[问题] 如何有效找出所有可能性组合
时间Tue Jul 16 21:47:15 2013
目前因为程式上需求 需要写一个能够找出一阵列内所有相加後可能的值
例如：一阵列内容有1 2 3 4 5
那可能会产生的值就会有
1 2 3 4 5
1+2 1+3 1+4 1+5 2+3 2+4 2+5 3+4 3+5 4+5
1+2+3 1+2+4 1+2+5 1+3+4 1+3+5 1+4+5 2+3+4 2+3+5 3+4+5
1+2+3+4 1+2+3+5 2+3+4+5
1+2+3+4+5
不知道大家有没有碰过相关的问题
不知道统计或是数学上有没有这种的公式可以使用的
还在努力想有什麽相关联>"<
--
※ 发信站: 批踢踢实业坊(ptt.cc)
◆ From: 114.38.122.183
2F：推 qwer820404:你这样列出来之後 你可以去观察一下 其实有个特性在 07/17 01:32
3F：推 qwer820404:我会先对阵列做排序，排完後会有个特性 每个组合的後数 07/17 07:56
4F：→ qwer820404:一定大於他前数 (在於阵列值不会有重复出现的情况下) 07/17 07:57
5F：→ qwer820404:那如果说 值有可能重覆 那要的组合方式有二种情况 07/17 07:58
6F：→ qwer820404:重覆的值 在一个组合里只会出现一次 也就是说 出现一个 07/17 07:59
7F：→ qwer820404:跟出现100个同样的值 还是等同於出现一次 就可以先用 07/17 07:59
8F：→ qwer820404:就可以先 消除掉不必要的 只留下最後确定有用的再处理 07/17 08:00
9F：→ qwer820404:那如果重覆的值 可以出现多次 就代表说 可以用个技巧 07/17 08:01
10F：→ qwer820404:让程式 会把一样的值 当作都是不一样的东西 07/17 08:01
11F：→ qwer820404:那如果这种要用递回做 後数会是大於等於他前数 07/17 08:02
12F：→ qwer820404:如果小弟的做法有什麽可改或思考有不对的 欢迎指教 07/17 08:03
可能一开始规则没订好 假设我的矩阵目前有15个值
1 2 3 3 4 4 5 6 7 7 8 9 10 11 12
然後要根据这十五个值排出其相加所有能够产生的值
例如1+2 +3+3+4=13
所以一楼的那个做法可能就没办法了QQ
目前用比较笨的方法 假设我的阵列B1=[1 2 2 3 4]
5个值我就设五层的FOR回圈 然後用一个ArrayList用放所以可能产生的值
for i=0;i<5i++
{
A1.Add(B1[i]);
for j=2:5 (简写)
if (j>i)
{
A1.Add(B1[i]+B1[j]);
for k=3:5
{
if (k>j)
{
A1.Add(B1[i}+B1[j]+B1[k]);
for L=4:5
{
if(L>k)
{
A1.Add(B1[i]+B1[j]+B1[k]+B1[L]);
for (M=5;M<=5;M++)
{
if(K>M)
{
A1.Add(B1[i]+B1[j]+B1[k]+B1[L]+B1[M]);
}}}}}}}}
这样的做法就能够把所有可能产生的值列出来
1
1+2
1+2+3
1+2+3+4
1+2+3+4+5
1+2+3+5
1+2+4
1+2+4+5
1+2+5
1+3
.
.
.
这样的做法成找出所以相加的可能性
之後再将A1用两个回圈去判定有没有重覆的 重复的就移除罗!!
不过除了这样的方法有没有什麽更好的方法
不知道2楼的大大是不是跟我一样的意思
因为这个方法还满耗时间的 而且算是暴力破解法吧(汗)
希望大家一起讨论看看罗!!
※ 编辑: chris70211 来自: 114.38.119.227 (07/17 22:23)
13F：推 qwer820404:我得比较不同耶 我是在做组合前就先考量重覆性定义 07/17 23:50
14F：→ qwer820404:你是在组合後 才去做 所以 你的COST会比较高吧 07/17 23:50
15F：→ StupidGaGa:这问题像学校出的，考基础逻辑概念 07/18 10:24
16F：→ StupidGaGa:如果要考虑到程式的弹性 建议这问题切割成许多function 07/18 10:26
17F：→ StupidGaGa:1.先做n相异物不重复取出m组合，先简称Cnm 07/18 10:29
18F：→ StupidGaGa:2. 把n跟m变化 07/18 10:30
19F：→ StupidGaGa:两个大Function概念是这样 07/18 10:31
因为重点在於矩阵数值的相加的值
所以如果在相加之前就考虑重覆性会把相加的可能性降低
例如 1 2 2
相加的值就会有1 2 2 3 3 4 5
可是如果一开始就考虑重覆性的问题
相加的值就只会有 1 2 3不知道有没有误解你们的意思
※ 编辑: chris70211 来自: 114.38.122.29 (07/18 21:03)
20F：→ qwer820404:有…你还是在以结果面来看 结果都是一样的 07/19 00:09
21F：→ qwer820404:是做法上跟顺序不同 同样的结果 不一样的过程 07/19 00:10
22F：→ qwer820404:重覆不重覆是你的情境下设定的条件啊 07/19 00:10
23F：→ StupidGaGa:数值重复这本来就要等到全部做完才知道 07/19 02:10
24F：→ StupidGaGa:你先考虑数值重复在思考排列是本末倒置的做法 07/19 02:10
25F：→ StupidGaGa:有时候问题不只一种解法，要找适合你自己的解法 07/19 02:11
26F：→ StupidGaGa:不过可以确定的是，你那写法不太优.... 07/19 02:19
27F：→ StupidGaGa:如果你是学生，我认为你就照你的想法写没差 07/19 02:20
28F：→ StupidGaGa:如果在工作，你那样写法程式弹性不够，後人维护困难 07/19 02:21
29F：推 hangchu:这叫幕集合(power set)，我在 Programming 版有发问过 07/20 03:03