Re: [問題] 請問關於排列組合程式
※ 引述《zgmfx2000 (千月星痕)》之銘言：
: 開發平台(Platform):DevC++
: 問題(Question)： 我想寫個排列組合的程式C n取r的那種...
: (不考慮字元相同但排序不同的組合)
: 但是想要讓使用者自訂n和r的數字...
: 我是先訂一個很大的陣列塞進字元串，
: 然後用指標下去跑，但是自訂r的話就不知道該怎做
恕刪。
若不要求字典順序輸出，
這裡提另一個早期看過的方法 (應算早期的 code 吧 , 出處真忘了)
如果真的不想碰 recursive 的話再來看
如果知道出處的話煩請告知。
---
這裡假設用二進位方式，決定該元素要不要輸出，
假設元素為 abcde (長度 n=5) , 取 3 (取 m=3)
abcde
flag = 11100 ----> 輸出 abc
flag = 01011 ----> 輸出 bde
重點就變成：flag 該如何變化。接下來是演算法步驟部份
------
(1) 初始化 : flag 前 m 個設 1，其它設 0
(2) 由左掃到右，當掃到 "10" 時，變 "01"，並將左邊的 1 全移到最左邊去。
如,
01(10)10 ---> 10(01)10
(3) 當 flag 前 n-m 個元素都為 0 時，即為最後一筆資料，如
000111
--------
範例 , abcdef C(6,3)
abcdef
111000 ,abc
110100 ,abd
101100 ,acd
011100 ,bcd
110010 ,abe
101010 ,ace
011010 ,bce
100110 ,ade
010110 ,bde
001110 ,cde
110001 ,abf
101001 ,acf
011001 ,bcf
100101 ,adf
010101 ,bdf
001101 ,cdf
100011 ,aef
010011 ,bef
001011 ,cef
000111 ,def
------
程式碼參考
void comb(char *str, int m)
{
int i,cnt=0;
int n = strlen(str); /* 元素個數 */
char *flag = (char*)malloc(n);
char *end = (char*)malloc(n-m);
memset(flag, 0, n), memset(flag, 1, m); /* 前 m 個設1 */
memset(end, 0, n-m);
while(memcmp(flag, end, n-m)){
/* output */
for(i=0; i!=n; ++i) if(flag[i]) putchar(str[i]);
puts("");
/* adjust flag , 10-->01 */
for(cnt=i=0; /*i!=n-1 && */ !(flag[i]&& !flag[i+1]); ++i)
cnt+=flag[i];
flag[i]=0, flag[i+1]=1;
/* adjust flag , move 1 to left */
memset(flag, 1, cnt);
memset(flag+cnt, 0, i-cnt);
}
/* last output */
puts(str+n-m);
free(flag), free(end);
}
----------
概念蠻簡單的，但實做起來，要快，不容易，
上述程式碼也有許多修改空間，唯供參考。
--
When I saw the turth of love,
I feel the pain which the world brings to me.
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 180.177.78.41
→
08/12 05:07, , 1F
08/12 05:07, 1F
→
08/12 05:33, , 2F
08/12 05:33, 2F
→
08/12 05:59, , 3F
08/12 05:59, 3F
推
08/12 06:02, , 4F
08/12 06:02, 4F
→
08/12 06:02, , 5F
08/12 06:02, 5F
→
08/12 06:03, , 6F
08/12 06:03, 6F
推
08/12 16:45, , 7F
08/12 16:45, 7F
→
08/12 17:07, , 8F
08/12 17:07, 8F
→
08/12 21:54, , 9F
08/12 21:54, 9F
討論串 (同標題文章)