求程序

aero

schreibe eine C-programm, das ein beliebige Zeichenfolge z einliest und alle permutationen л(z)={z1,....,zn},n=|z|! deiser Zeichenfolge ausgibt, d.h. etwa z=TOR =>л(z)={TOR,TRO,OTR,ORT,RTO,ROT}.Wenn zusaetzlich eine nichtleer Zeichenfolge s eingegeben wird, dann sind nur dir Permutation auszugeben, die diese Zeichenfolge enthalten.(Beispiel: s=RO =>:ausgabe: TRO, ROT)

babyfacekiller

并不简单啊！
全排列
    所谓全排列，就是对n个对象，列出其所有可能的排列顺序。这个问题相对来说要简单一点。让我们先从最简单的情况着手，如果我们只有一个对象，该如何实现其全排列呢？答案很简单，现在我们只有一种排列。OK，现着我们试着引入第二个对象，首先我们需要知道，现在增加了几种全排列的可能，我们可以这么看，第n个对象的引入，对于n-1个对象的全排列的影响就是在原先的每一个全排列中的任一位置插入第n个对象，也就是说，listcount(n)=listcount(n-1)*n；而按照这个思路，对于任意n个对象的全排列，我们都可以从最简单的一个对象的全排列开始直到生成全部n个对象的全排列。

babyfacekiller

组合，就是从n个对象中取出任意m个对象的全部可能。这个问题可能要复杂一点。对于组合来说，对象的顺序是没有意义的，1、2、3和3、2、1是同一种可能。那么我们有必要人为地制定一个规则，我们可以设想给每一个对象编上连续的序号，而在我们的组合中对象必须是按其序号的顺序排列，这样我们就能有效地避免排列顺序对我们的影响。假定我们现在有六个对象，其序号是1、2、3、4、5、6。那么我们的第一种组合是1、2、3，而最后一种组合则是4、5、6。在此之间，我们经历了其它有可能出现的18种情况，对于这种算法我们很自然地会想到使用递归函数。首先我们先在我们的结果集中定义第一种可能是1、2、3，然后我们把当前位置定为最后一位，只要有可能，对于最后一位来说，它的最大值只能是6，在未到6之前，每增加一次就增加一种新的组合，如果最后一位已经是6，则我们将当前位置转入前一位，前一位的最大值是5，如果前一位还没到5，则将前一位加一，然后当前位置再度转入最后一位，现在最后一位的最小值是4，从4开始直到6，又形成了我们新的组合，这样，直到我们最终出现4、5、6这个组合时，函数退出。

babyfacekiller

public class mytest
{String[] mychar=new String[50];
int charcount;
int charlist;
public void SetMyTest()
//初始化
{charcount=0;
charlist=1;
}
public void insertChar(String thischar)
//增加新的字符串
{charcount++;
mychar[charcount]=thischar;
charlist*=charcount;
}
public String listAllChar()
//列出全排列
{String[][] allchar=new String[charlist+1][charcount+1];
int i;
int j;
int z=1;
for (i=1;i<=charcount;i++)
{myCopy(addCharList(i,allchar,z),allchar,charlist,charcount);
z*=i;
}
String listallchar=new String("");
for (i=1;i<=charlist;i++)
{for (j=1;j<=charcount;j++)
listallchar+=allchar[j]+" ";
listallchar=listallchar+"
";
}
return listallchar;
}
public String[][] addCharList(int i,String[][] allchar,int z)
//在i-1个对象的全排列中引入第i个对象
{int j;
int h=1;
int k;
String[][] tempallchar=new String[charlist+1][charcount+1];
for (k=1;k<=z;k++)
{for (j=1;j<=i;j++)
{myCopy(tempchar(j,allchar[k],mychar),tempallchar[h],charcount);
h++;
}
}
return tempallchar;
}
public String[] tempchar(int i,String[] beginchar,String thischar)
//将新对象插入指定位置
{int j;
String[] tempbeginchar=new String[charcount+1];
myCopy(beginchar,tempbeginchar,charcount);
for (j=charcount;j>i;j--) tempbeginchar[j]=tempbeginchar[j-1];
tempbeginchar=thischar;
return tempbeginchar;
}
public String selectSomeChar(int select)
//列出其中取出select个对象的全部组合
{int selectcount=1;
int i;
for (i=select+1;i<=charcount;i++) selectcount=selectcount*i/(i-select);
String[][] selectchar=new String[selectcount+1][select+1];
int[][] selectint=new int[selectcount+1][select+1];
for (i=1;i<=select;i++)
{selectchar[1]=mychar;
selectint[1]=i;
}
int z=1;
addSelect(selectchar,selectint,1,select,select);
int j;
String selectsomechar=new String("");
for (i=1;i<=selectcount;i++)
{for (j=1;j<=select;j++)
selectsomechar+=selectchar[j]+" ";
selectsomechar=selectsomechar+"
";
}
return selectsomechar;
}
public void addSelect(String[][] selectchar,int[][] selectint,int z,int position,int select)
//增加新的组合
{int i;
if (position==select)
{if (selectint[z][position] {z++;
myCopy(selectint[z-1],selectint[z],select);
selectint[z][select]++;
for (i=1;i<=select;i++) selectchar[z]=mychar[selectint[z]];
addSelect(selectchar,selectint,z,position,select);
}
else
{position--;
addSelect(selectchar,selectint,z,position,select);
}
}
else
{if (selectint[z][position] {selectint[z][position]++;
selectint[z][position+1]=selectint[z][position]+1;
position++;
addSelect(selectchar,selectint,z,position,select);
}
else
{if (position==1)
{return;
}
else
{position--;
addSelect(selectchar,selectint,z,position,select);
}
}
}
}
public void myCopy(String[][] Str1,String[][] Str2,int i,int j)
{int h;
int k;
for (h=1;h<=i;h++) for (k=1;k<=j;k++) Str2[h][k]=Str1[h][k];
}
public void myCopy(String[] Str1,String[] Str2,int i)
{int h;
for (h=1;h<=i;h++) Str2[h]=Str1[h];
}
public void myCopy(int[] Str1,int[] Str2,int i)
{int h;
for (h=1;h<=i;h++) Str2[h]=Str1[h];
}
}

babyfacekiller

你不是想上网玩足球彩票吧，用这个来预测:D

aero

谢谢 babyfacekiller
果然有高手的素质，不象有些人，认为简单就不屑一姑，很可能其实自己都不会
再次感谢你， babyfacekiller

aero

更谢谢你的解释，望刚开始学编程，以后可能还要麻烦你。。。。。

aero

最初发表由 babyfacekiller
[B]你不是想上网玩足球彩票吧，用这个来预测:D [/B]

是一道作业题，可能教授想玩？？
你的程序好长啊，又编译不出来，我争取今天晚上把它读懂！

babyfacekiller

也许是教授想玩吧，刚刚开始就来全排列，狠！！
我上面只是给出了一个类，里面包含的每个成员函数都有解释。我记得今年第四期的<<程序员>>上有用c语言写的数组的全排列，是根据离散数学教材上给出的算法，很经典，回来帮你找找。