算法问题

Question

我想做一个函数，参数为字符串和维数，从该字符串中取出给定维数的组合，例如：该字符串为“a,b,c,d”，维数为2，则返回的结果为 ："ab,ac,ad,bc,bd"，如维数为3，则结果为“abc,bcd”

Answer 1

lovvver(春晖) ，“全排列实现”是什么意思？能否多说几句？

Answer 2

给你一个简单的描述int combine(int a[],int sub){
//a[1..?]表示候选集,sub表示一个排列(组合)的元素个数
{
   int total=sizeof(a);
   int order[sub+1];
   int count=0;//符合条件的排列(组合)的个数
   order[0]=-1;
   for(int i=1;i<=sub;i++)
      order[i]=i;
   int k=sub;
   bool flag=true;
   while(order[0]!=-1){
      if(flag){
         for(i=1;i<=sub;i++)//输出符合要求的组合
            printf("%d ",a[order[i]]);
         printf("\n");
         count++;
         flag=false;
      }
      order[k]++;
      if(order[k]==total+1){
         order[k--]=0;
         continue;
      }   
　　　...
      //在此加入order[k]的限制条件
      //如果条件满足,则往下执行
      //否则continue;
      if(k<sub){
         order[++k]=order[k-1];
         continue;
      }
      if(k==sub)
         flag=true;
   }
   return count;
}

Answer 3

jackymi(完美刺客) :你这段程序有个严重的bug: order[0]=-1;根本就进不了循环，是不是粘代码时粘错了？哪位大侠再给点建议

Answer 4

声明 程序我没有测试过 可以用下边的阶乘公式来做
C(n,r)=n!/(r!*(n-r)!)

Answer 5

问题描述的不够清楚，或者是我没看明白吧：
例如：该字符串为“a,b,c,d”，维数为2，则返回的结果为 ："ab,ac,ad,bc,bd"，那么"cd"是不是也在返回结果之列？
如维数为3，则结果为“abc,bcd”那么“abd,acd”也是返回结果之列？

Answer 6

抱歉，我写漏了，应该是ab,ac,ad,bc,bd,cd

Answer 7

public ArrayList GetArray(string sTxt,int iWs)
{

ArrayList myAr=new ArrayList();
int iMax=0;
string sTmp="",sTmp2="";
string[] a=sTxt.Split(new Char [] {','});//取得最原始的元素
for (int i=0;i<a.Length;i++)//建立最初的组合
{
myAr.Add(a[i]);
}
for (int i=2;i<=iWs;i++) //依次在各组合上加元素，直道长度达到指定长度为止
{
iMax=myAr.Count;
for (int j=0;j<iMax;j++){
sTmp=myAr[j].ToString();
sTmp2=sTmp.Substring(sTmp.Length-1,1);
                        
for (int k=0;k<a.Length;k++){//这个循环可以优化
if (String.Compare(a[k],sTmp2)>0){
 myAr.Add(sTmp+a[k]);
}
}
myAr.RemoveAt(j);
j--;
iMax--;
}
}
return myAr;
}
说明 最里面的那个循环可以优化，可以使用快速查找，或者保存检索位置什么的方法优化

Answer 8

用递归可简单的实现如下：
void f(string src, int pos, int n)
{
if(n = 0)
{
return;
}
for(int i = pos; i < str.Length - n; i++)
{
if(n = 1)
{
将src + str[i]写进数组；
}
else
{
f(src + str[i], i + 1, n -1);
}
}
}调用方式：f("", 0, n)，n换成相应的维数即可;
str是原来的字符串，你只要把这个函数封装在类中，简单调整一下应该就可以了；