算法問題?

巴拉克

從1-9這9個(gè)數(shù)中取3個(gè)數(shù)進(jìn)行組合，把所有可能的組合都取出來，再從這些組合中選3個(gè)組合組成1-9這九個(gè)數(shù)，要求把所有的組合全部用完，并寫出結(jié)果。請(qǐng)問有什么好的算法嗎？

w25

從1-9這9個(gè)數(shù)中取3個(gè)數(shù)進(jìn)行組合，把所有可能的組合都取出來。。意思是什么？具個(gè)例子？是不是假如取出1，2，3的話，那么組合是123，132，213。。。。六個(gè)數(shù)（3位整數(shù)）？？？
再從這些組合中選3個(gè)組合組成1-9這九個(gè)數(shù)，要求把所有的組合全部用完。。。的意思不明白，具個(gè)例子。

巴拉克

比如1 2 3 4 5 6 7 8 9中取出的組合有[1 2 3] [3 5 6] [7 8 9] [2 7 8] [1 8 9] [4 5 9] 等，共84個(gè)組合，再從這84個(gè)組合中取出3個(gè)組合組成1 2 3 4 5 6 7 8 9，比如[1 2 3] [4 5 6] [7 8 9],要求每個(gè)組合只用一次，且把所有的組合都用完，也就是組成28個(gè)1-9，把這些組合寫出來。

w25

第一問倒是很好解決，你可以用三次for循環(huán)（每層的值只能取一次）吧他們讀入整形數(shù)組（這種假設(shè)直接些，要是取單個(gè)數(shù)的話就用整數(shù)去除100，10，mod等，不然你就寫一個(gè)struct，去做純處結(jié)構(gòu)）。這樣得到84個(gè)整數(shù)。
第二問我還是沒明白，是不是從這些組合集中去找那三個(gè)組合能組成123。。。9這9個(gè)不許重復(fù)的數(shù)阿？

巴拉克

對(duì)，要求把所有組合用完，不能重復(fù)使用某個(gè)組合。

那是84個(gè)組合，不是84個(gè)整數(shù)。

w25

我只是說一種存儲(chǔ)的方法，因?yàn)槊總�(gè)組合內(nèi)的元素有一定的規(guī)律，和百位整數(shù)相像，而且也有方法分解成單個(gè)的元素，畢竟你要在機(jī)器上實(shí)現(xiàn)，所以必須選擇存儲(chǔ)結(jié)構(gòu)，你也可以自己定義struct體。但從第二問看來，還是定義結(jié)構(gòu)體為好。我寫一個(gè)思路你看看行不行，用最簡單的結(jié)構(gòu)體數(shù)組（你也可以用鏈表）我定義這個(gè)結(jié)構(gòu)體內(nèi)有四個(gè)存儲(chǔ)單元，三個(gè)用于存1。2。3這樣的元素（字符也好，整數(shù)也好），第四個(gè)存儲(chǔ)單元我定義為字符（假設(shè)為#字符），用于存儲(chǔ)判斷標(biāo)志（該標(biāo)志只是判斷當(dāng)前struct體單元是否被處理完）然后這些存儲(chǔ)單元變成一維數(shù)組（結(jié)構(gòu)體數(shù)組），共有84個(gè)，那樣的話就用檢索從頭檢到尾找出符合條件的三個(gè)結(jié)構(gòu)體（先判斷結(jié)構(gòu)體有無#號(hào)），如果符合條件后，把符合條件的結(jié)構(gòu)體標(biāo)志位置#號(hào)，一直找28次。我想能完成功能，但可能效率不高。如果要提高效率，你看看數(shù)據(jù)結(jié)構(gòu)中的排序

巴拉克

用結(jié)構(gòu)體存儲(chǔ)數(shù)據(jù)，可以實(shí)現(xiàn)，如果每次取元素都判斷，效率不高，如果我從12個(gè)數(shù)里取3個(gè)數(shù)組合，那就不是84種組合了。關(guān)鍵是如何從結(jié)構(gòu)體數(shù)組中選符合條件的元素。

BingbingNorth

我給一個(gè)程序，拋磚引玉。記得上次有一個(gè)問題，我第一個(gè)回的，結(jié)果后面回了n多算法，每個(gè)都要跟我的比較比我的好在哪里:(
我的程序的好處是n和m可以訂制，比如這個(gè)問題n=9, m=3。
另一個(gè)問題，如果要就題論題的話，也挺好解決，comb函數(shù)中每次選三個(gè)就行了，不過要改成加一個(gè)參數(shù)k使得n=m*k的情況就要麻煩一點(diǎn)。[code]#include <stdio.h>;
#include <stdlib.h>;

#define MAXN 1000

int selected[MAXN]={0};
int n;

void comb(int start , int m)
{
        int i;
       
        if(m==0)
        {
                for(i=0; i<n; i++)
                        if(selected[i])
                                printf("%d ",i+1);
                printf("\n");
        }
        else
                for(i=start; i<=n-m; i++)
                {
                        selected[i]=1;
                        comb(i+1, m-1);
                        selected[i]=0;
                }
}

/*----------------------------------

w25

你在一樓寫的意思好像和上面寫的不一樣啊，一樓寫的時(shí)候是以知有84個(gè)組合，而現(xiàn)在你的意思有多了幾個(gè)豈不成了未知組合個(gè)數(shù)，要是存儲(chǔ)達(dá)不到要求可也改變存儲(chǔ)結(jié)構(gòu)，效率不高的話，可以改進(jìn)算法。
如果是算法的問題用鏈表可以簡化一部分操作，另外在比較是若發(fā)現(xiàn)重復(fù)比較可以退出，進(jìn)行下個(gè)數(shù)據(jù)的比較但是對(duì)存儲(chǔ)空間的檢索我想一定是要進(jìn)行的，假如你取出第一個(gè)數(shù)位123，在取第二個(gè)數(shù)時(shí)所取得數(shù)就不能包括1。2。3假如取出的是567的話，在取第三個(gè)數(shù)（489這個(gè)組合時(shí)）難道你不需要檢索存儲(chǔ)單元么？所以說檢索必須要循環(huán)（從上面的思路講），只不過是檢索的次數(shù)需要加入附加的判斷來較少罷了。從而提高效率。我想你說的也是這個(gè)意思。

w25

樓上的算法不錯(cuò)，但沒有理解樓主的意思，這9個(gè)數(shù)不一定被理解成整數(shù)，應(yīng)該被正確的理解為集合中的元素，如果要是擴(kuò)充這個(gè)集合的話（比如重10個(gè)或11個(gè)元素中取，那么元素可能是1，2。。。9，a,b,c...）所以要寫這個(gè)程序必須要知道元素的類型，個(gè)數(shù)，如果未知的話寫出程序就會(huì)一個(gè)人解釋一個(gè)樣，沒有統(tǒng)一的。