算法问题?

巴拉克

从1-9这9个数中取3个数进行组合，把所有可能的组合都取出来，再从这些组合中选3个组合组成1-9这九个数，要求把所有的组合全部用完，并写出结果。请问有什么好的算法吗？

w25

从1-9这9个数中取3个数进行组合，把所有可能的组合都取出来。。意思是什么？具个例子？是不是假如取出1，2，3的话，那么组合是123，132，213。。。。六个数（3位整数）？？？
再从这些组合中选3个组合组成1-9这九个数，要求把所有的组合全部用完。。。的意思不明白，具个例子。

巴拉克

比如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个组合，再从这84个组合中取出3个组合组成1 2 3 4 5 6 7 8 9，比如[1 2 3] [4 5 6] [7 8 9],要求每个组合只用一次，且把所有的组合都用完，也就是组成28个1-9，把这些组合写出来。

w25

第一问倒是很好解决，你可以用三次for循环（每层的值只能取一次）吧他们读入整形数组（这种假设直接些，要是取单个数的话就用整数去除100，10，mod等，不然你就写一个struct，去做纯处结构）。这样得到84个整数。
第二问我还是没明白，是不是从这些组合集中去找那三个组合能组成123。。。9这9个不许重复的数阿？

巴拉克

对，要求把所有组合用完，不能重复使用某个组合。

那是84个组合，不是84个整数。

w25

我只是说一种存储的方法，因为每个组合内的元素有一定的规律，和百位整数相像，而且也有方法分解成单个的元素，毕竟你要在机器上实现，所以必须选择存储结构，你也可以自己定义struct体。但从第二问看来，还是定义结构体为好。我写一个思路你看看行不行，用最简单的结构体数组（你也可以用链表）我定义这个结构体内有四个存储单元，三个用于存1。2。3这样的元素（字符也好，整数也好），第四个存储单元我定义为字符（假设为#字符），用于存储判断标志（该标志只是判断当前struct体单元是否被处理完）然后这些存储单元变成一维数组（结构体数组），共有84个，那样的话就用检索从头检到尾找出符合条件的三个结构体（先判断结构体有无#号），如果符合条件后，把符合条件的结构体标志位置#号，一直找28次。我想能完成功能，但可能效率不高。如果要提高效率，你看看数据结构中的排序

巴拉克

用结构体存储数据，可以实现，如果每次取元素都判断，效率不高，如果我从12个数里取3个数组合，那就不是84种组合了。关键是如何从结构体数组中选符合条件的元素。

BingbingNorth

我给一个程序，抛砖引玉。记得上次有一个问题，我第一个回的，结果后面回了n多算法，每个都要跟我的比较比我的好在哪里:(
我的程序的好处是n和m可以订制，比如这个问题n=9, m=3。
另一个问题，如果要就题论题的话，也挺好解决，comb函数中每次选三个就行了，不过要改成加一个参数k使得n=m*k的情况就要麻烦一点。[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

你在一楼写的意思好像和上面写的不一样啊，一楼写的时候是以知有84个组合，而现在你的意思有多了几个岂不成了未知组合个数，要是存储达不到要求可也改变存储结构，效率不高的话，可以改进算法。
如果是算法的问题用链表可以简化一部分操作，另外在比较是若发现重复比较可以退出，进行下个数据的比较但是对存储空间的检索我想一定是要进行的，假如你取出第一个数位123，在取第二个数时所取得数就不能包括1。2。3假如取出的是567的话，在取第三个数（489这个组合时）难道你不需要检索存储单元么？所以说检索必须要循环（从上面的思路讲），只不过是检索的次数需要加入附加的判断来较少罢了。从而提高效率。我想你说的也是这个意思。

w25

楼上的算法不错，但没有理解楼主的意思，这9个数不一定被理解成整数，应该被正确的理解为集合中的元素，如果要是扩充这个集合的话（比如重10个或11个元素中取，那么元素可能是1，2。。。9，a,b,c...）所以要写这个程序必须要知道元素的类型，个数，如果未知的话写出程序就会一个人解释一个样，没有统一的。