排列組合的問題

小雞雞

unread,

May 13, 2003, 7:32:12 AM5/13/03

to

請問各位先進... 我現在想把一串不重複的數字(size=m)取出其中的n個值出來(n<m)
,而且將所有排列組合秀出來..

[ 有點類似樂透,在1~42的數字中取出7個數字的所有排列組合 ]

請問有沒有特別的演算法可以跑出所有的組合呢...
或是那裡有相關的網站跟paper呢....

--
[m [1;33m※來源 : [1;36m 台北科大計中紅樓資訊站 [1;35mredbbs.cc.ntut.edu.tw
[1;32m※FROM : [1;37m140.124.42.124 [m

藍色爵士貓

unread,

May 13, 2003, 8:41:40 AM5/13/03

to

※ 引述《smalltu...@redbbs.cc.ntut.edu.tw (小雞雞)》之銘言：
: 請問各位先進... 我現在想把一串不重複的數字(size=m)取出其中的n個值出來(n<m)
: ,而且將所有排列組合秀出來..
: [ 有點類似樂透,在1~42的數字中取出7個數字的所有排列組合 ]
: 請問有沒有特別的演算法可以跑出所有的組合呢...
: 或是那裡有相關的網站跟paper呢....
http://caterpiliar.adsldns.org/phpBB2/viewtopic.php?t=96
--
[m※ Origin: 臺大電機 Maxwell 站 ◆ From: sw59-219-250.adsl.seed.net.tw

小雞雞

unread,

May 13, 2003, 8:57:04 AM5/13/03

to

【在 Ju...@bbs.ee.ntu.edu.tw (藍色爵士貓) 的大作中提到: 】
: ※ 引述《smalltu...@redbbs.cc.ntut.edu.tw (小雞雞)》之銘言：

: : 請問各位先進... 我現在想把一串不重複的數字(size=m)取出其中的n個值出來(n<m)
: : ,而且將所有排列組合秀出來..
: : [ 有點類似樂透,在1~42的數字中取出7個數字的所有排列組合 ]
: : 請問有沒有特別的演算法可以跑出所有的組合呢...
: : 或是那裡有相關的網站跟paper呢....
: http://caterpiliar.adsldns.org/phpBB2/viewtopic.php?t=96

謝謝這位先進... 不過小弟所想知道的是如過在沒有加入排序的情況下
所有組合的演算法...

--
[m [1;33m※來源 : [1;36m 台北科大計中紅樓資訊站 [1;35mredbbs.cc.ntut.edu.tw

[1;32m※FROM : [1;37m211.21.92.54 [m

藍色爵士貓

unread,

May 13, 2003, 9:13:18 AM5/13/03

to

※ 引述《smalltu...@redbbs.cc.ntut.edu.tw (小雞雞)》之銘言：
: 【在 Ju...@bbs.ee.ntu.edu.tw (藍色爵士貓) 的大作中提到: 】
: : http://caterpiliar.adsldns.org/phpBB2/viewtopic.php?t=96
: 謝謝這位先進... 不過小弟所想知道的是如過在沒有加入排序的情況下
: 所有組合的演算法...

該例並沒有排序。。。。

先將m個數作亂數排列，然後取前n個值：

http://caterpiliar.adsldns.org/phpBB2/viewtopic.php?t=58

然後再對這n個值作排列組合。。。。

藍色爵士貓

unread,

May 13, 2003, 9:14:02 AM5/13/03

to

※ 引述《smalltu...@redbbs.cc.ntut.edu.tw (小雞雞)》之銘言：
: 【在 Ju...@bbs.ee.ntu.edu.tw (藍色爵士貓) 的大作中提到: 】
: : http://caterpiliar.adsldns.org/phpBB2/viewtopic.php?t=96
: 謝謝這位先進... 不過小弟所想知道的是如過在沒有加入排序的情況下
: 所有組合的演算法...

該例並沒有排序。。。。

揣測您的題意，先將m個數作亂數排列，然後取前n個值：

小雞雞

unread,

May 13, 2003, 9:47:48 AM5/13/03

to

【在 Ju...@bbs.ee.ntu.edu.tw (藍色爵士貓) 的大作中提到: 】
: ※ 引述《smalltu...@redbbs.cc.ntut.edu.tw (小雞雞)》之銘言：

: : 謝謝這位先進... 不過小弟所想知道的是如過在沒有加入排序的情況下

: : 所有組合的演算法...
: 該例並沒有排序。。。。
: 揣測您的題意，先將m個數作亂數排列，然後取前n個值：
: http://caterpiliar.adsldns.org/phpBB2/viewtopic.php?t=58
: 然後再對這n個值作排列組合。。。。
: http://caterpiliar.adsldns.org/phpBB2/viewtopic.php?t=96

..好像會錯意了...

小弟的意思是如果現在有一串值 1 2 3 4 5 6 7 8
如果想取出6個值(不重複,不考慮先後問題)..
照理應該會有 (8!)/((8-6)!6!)=28個組合
如:
1 2 3 4 5 6
1 2 3 4 5 7
...

那是否有一套演算法可以跑出這28重組合呢...

藍色爵士貓

unread,

May 13, 2003, 10:38:16 AM5/13/03

to

※ 引述《smalltu...@redbbs.cc.ntut.edu.tw (小雞雞)》之銘言：
: ..好像會錯意了...

: 小弟的意思是如果現在有一串值 1 2 3 4 5 6 7 8
: 如果想取出6個值(不重複,不考慮先後問題)..
: 照理應該會有 (8!)/((8-6)!6!)=28個組合
: 如:
: 1 2 3 4 5 6
: 1 2 3 4 5 7
: ...
: 那是否有一套演算法可以跑出這28重組合呢...

這邊是有個產生所有集合的方法：
http://caterpiliar.adsldns.org/phpBB2/viewtopic.php?t=100

較符合您的題意的，我整理一下再貼出來。。。。
--
[m※ Origin: 臺大電機 Maxwell 站 ◆ From: sw59-211-103.adsl.seed.net.tw

藍色爵士貓

unread,

May 13, 2003, 11:18:48 AM5/13/03

to

※ 引述《Just (藍色爵士貓)》之銘言：
: : ...

: : 那是否有一套演算法可以跑出這28重組合呢...
: 這邊是有個產生所有集合的方法：
: http://caterpiliar.adsldns.org/phpBB2/viewtopic.php?t=100
: 較符合您的題意的，我整理一下再貼出來。。。。

這應該是您要的：
http://caterpiliar.adsldns.org/phpBB2/viewtopic.php?t=122

小雞雞

unread,

May 13, 2003, 12:41:29 PM5/13/03

to

【在 Ju...@bbs.ee.ntu.edu.tw (藍色爵士貓) 的大作中提到: 】
: ※ 引述《Just (藍色爵士貓)》之銘言：
: : 這邊是有個產生所有集合的方法：

: : http://caterpiliar.adsldns.org/phpBB2/viewtopic.php?t=100
: : 較符合您的題意的，我整理一下再貼出來。。。。
: 這應該是您要的：
: http://caterpiliar.adsldns.org/phpBB2/viewtopic.php?t=122

嗯嗯....謝謝這位先進... 同時也讓小弟看到一個這麼棒的網站.
真是謝謝呢...

因為我所要跑的值是1~4096的值取出32 and 64個值...
小弟其實有寫一個演算法了.. 但是實在是跑太久了..
所以想看一下有沒有更好的演算法..

剛剛看了一下才發現這方法跟我寫的很像.. 唉.. 看來真的得等他慢慢跑完了

追憶似水年華

unread,

May 14, 2003, 12:42:57 AM5/14/03

to

※ 引述《smalltu...@redbbs.cc.ntut.edu.tw (小雞雞)》之銘言：

> : 這應該是您要的：
> : http://caterpiliar.adsldns.org/phpBB2/viewtopic.php?t=122
> 嗯嗯....謝謝這位先進... 同時也讓小弟看到一個這麼棒的網站.
> 真是謝謝呢...
> 因為我所要跑的值是1~4096的值取出32 and 64個值...
> 小弟其實有寫一個演算法了.. 但是實在是跑太久了..
> 所以想看一下有沒有更好的演算法..
> 剛剛看了一下才發現這方法跟我寫的很像.. 唉.. 看來真的得等他慢慢跑完了

#include<cstdlib>
#include<iostream>
#include<vector>
#include<string>

using namespace std;

void comb(vector<char> mat,int start,vector<char> combine,int column,int loop)
{
int localloop=loop;
int localstart=start;
int sizec=combine.size();

if(column>(sizec-1))
{
string str;
for(int cnt=0;cnt<sizec;++cnt)
{
str+=combine[cnt];
str+=' ';
}
cout<<str<<endl;
return;
}

for(int i=0;i<=loop;++i)
{
combine[column]=mat[start+i];
++localstart;
comb(mat,localstart,combine,column+1,localloop);
--localloop;
}

return;
}
int main()
{
cout<<"Calculate C(m,n)!!"<<endl
<<"Input number of m (max to 10) :";
cin>>M;

cout<<"Input number of n (n<m) :";
cin>>N;

if(N>M)
{
cerr<<"Error: M is greater than N"<<endl;
exit(1);
}

char mat[10]={'1','2','3','4','5','6','7','8','9','0'};
vector<char> matrix(mat,mat+10);
vector<char> combine(N);

comb(matrix,0,combine,0,M-N);

system("PAUSE");
return 0;
}

--

[1;33;41m[Master Chang.]______________________________________________ [m
[1;33;44m企鵝寶寶工作隊 | http://3ybaby.v-club.net/ [m
[1;33;44m請大家幫忙翻譯KDE | http://i18n.linux.org.tw/ [m
[1;33;44m全像光學實驗室 | http://www.ccit.edu.tw/~c3hog/master.html [m
[1;33;44m_____________________________________________________________ [m
--
[1;32m※ Origin: [33mSayYA 資訊站 [37m<bbs.sayya.org> [m
[1;31m◆ From: [36mh112-213.dorm5.ccit.edu.tw [m

Palatis

unread,

May 20, 2003, 6:08:15 PM5/20/03

to

-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA1

藍色爵士貓 wrote:
> ※ 引述《smalltu...@redbbs.cc.ntut.edu.tw (小雞雞)》之銘言：
> : ..好像會錯意了...
> : 小弟的意思是如果現在有一串值 1 2 3 4 5 6 7 8
> : 如果想取出6個值(不重複,不考慮先後問題)..
> : 照理應該會有 (8!)/((8-6)!6!)=28個組合
> : 如:
> : 1 2 3 4 5 6
> : 1 2 3 4 5 7
> : ...
> : 那是否有一套演算法可以跑出這28重組合呢...
>
> 這邊是有個產生所有集合的方法：
> http://caterpiliar.adsldns.org/phpBB2/viewtopic.php?t=100
>
> 較符合您的題意的，我整理一下再貼出來。。。。
>

如果要排出所有的組合, 除了暴力法以外還有什麼辦法?

- --
最好的是男人 (man) ！
請善用 Google (http://www.google.com/) ！

-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.2.2 (GNU/Linux)

iD8DBQE+yqdS3zkHylOtwZ8RAozqAJ9JJUlPLfAndmpfy2rKCUbwimivqwCeJ+6x
BxiL5eVQ8yaFul6B3cf1qGA=
=b8O6
-----END PGP SIGNATURE-----