20多年前，在进行计算机PASCAL语言教学时，让学生编写递归程序。改程序是输入数N，输出1到N的全排列。
这是一个普通题，但是有个学生写了一个程序，读不懂也不对，然后问他“这一句干什么，那一句干什么”，好像回答都没用，就直接删除。结果递归过程中就剩一句（没有分号），竟然程序正确。2004年给公司的技术高手说了这个故事，他满怀信心说可以重新编写出来，结果三个月后，他承认没有编写出来，并断言不可能。但是一周后，他自己编写出来并调试成功。
我这两次的程序都没有保留，看看还有没有高手能够解决。

什么叫全排列？举个例子？

对，举个例子

书上都有

例如

输入3  输出  123  132  213 231 312 321
输入4 输出   1234  1243  1324 1342  1423  1432
                    2134  2143  2314 2341  2413  2431
                    3124  3142.。。

很有难度啊

我刚开始学数据结构和算法方面的东西。用的是java来写的。这是我写的一个类，估计能满足你的需求。
  这个类就是要把的求组合的东西的排列输出来。你的要求的话么。基本上能满足了吧。只要再写一个类。输入的时候做个从1开始的循环就好了。如果要出来的是结构是数字，就改一下output的取值就可以了。
  不过楼主这种东西估计也就刚开始学的时候能够做一下。
public class teams {
    String[] a;                                   //the things to be put in the package.
    int nItems;                                   //how many things
    int max;                                      //the length of the array.
    public teams(int len){
            a = new String[len];
            nItems=0;
            max=len;
    }
    public void insert(String Item){
            if(max==nItems){
                    System.out.print("the array is full");
            }
            else{
                    a[nItems++]=Item;
            }
    }
    public int showteamchoice(int n,int y){
           int temp;
           if(y==1){
                   temp = n;
           }
           else if(n==y){
                   temp = 1;
           }
           else{
                   temp=showteamchoice(n-1,y-1);
                   temp=temp+showteamchoice(n-1,y);
           }
           return temp;
   }
    public void showteam(int n,int k,int index,String output){
            if(k==0){                                   //one kind of the combine
                    System.out.println(output);
                    return;
            }
            else if(index==nItems&&k!=0){               //not enough items for the combine
                    return;
            }
            else {                                          
                    int temp=k;
                String stemp=output;
                    while(index<=nItems-1){                //the loop is to decide the first items of the combine.
                            temp=k;
                            stemp=output;
                            stemp=stemp+","+a[index];
                            this.showteam(n-1, temp-1, index+1, stemp);
                            index=index+1;
                    }
            }
    }
}

[ 本帖最后由 Marshall605 于 2008-7-20 21:13 编辑 ]

谢谢，我不会JAVA，不知你的程序是否经过调试，结果是否正确，
但是普通读你的程序可能不符合我的要求，你的递归主程序可能是


    public int showteamchoice(int n,int y){
           int temp;
           if(y==1){
                   temp = n;
           }
           else if(n==y){
                   temp = 1;
           }
           else{
                   temp=showteamchoice(n-1,y-1);
                   temp=temp+showteamchoice(n-1,y);
           }
           return temp;
   }

有多个分号


    public void showteam(int n,int k,int index,String output){
            if(k==0){                                   //one kind of the combine
                    System.out.println(output);
                    return;
            }
            else if(index==nItems&&k!=0){               //not enough items for the combine
                    return;
            }
            else {                                          
                    int temp=k;
                String stemp=output;
                    while(index<=nItems-1){                //the loop is to decide the first items of the combine.
                            temp=k;
                            stemp=output;
                            stemp=stemp+","+a[index];
                            this.showteam(n-1, temp-1, index+1, stemp);
                            index=index+1;
                    }
            }
    }
}
也有多个分号


应该是
    public void showteam(int n,int k,int index,String output){
       if(k==0){System.out.println(output)}
            else if(index==nItems&&k!=0){return}
            else {                                          
                   WHile(index<=nItems-1){this.showteam(n-1, temp-1, index+1, stemp)}
            }；
    }
这样的结构，才叫递归过程中没有分号；
再一次谢谢你

有用的只是showteam，showteamchoice估计是我的开始写的时候，思路比较乱时候的方法。毕竟刚刚开始学么，请见谅。
    其次，仔细看了你的要求，发觉不完全符合你的要求。因为我123，和321算一个的。
    不过关于你的问题，我只有个解决思路。基本上来说就是建一个类。基本和我一样，保留成员和insert方法。showteam做以下改变
    参数改为n 项目总共排序的个数。k 要取得数。
    index做大修改。因为要写一个类。这个类基本就是一个数组或者链表，建议用链表。然后除了insert方法之外，还有一个check方法，判断参数是否为链表当中的值，和display方法。（学了java之后觉得类真的很好用，就什么都往能用类上面靠。嘿嘿)
       然后就是showteam这个方法了。这个方法做两件事，就是当参数k=0的时候，调用index的display方法，然后返回。
     如果说k<>0，就做一个循环，在n里取一个数判断是不是在index这个了链表里面，如果不在，把这个数写入index，调用自己，参数为n，k-1，和改变了只偶的index。如果在，就countiue一下，下一个。
     至于你要的实例的话么。因为我是一个不是计算机专业，现在参加一个sap的abap的产前培训，觉得数据结构对提高代码效率和逻辑很有用。所以自学的。我只会vb和java。如果要例子的话么。我周末可以写利用excel中的vba写一个给你看。

[ 本帖最后由 Marshall605 于 2008-7-21 18:56 编辑 ]

来学习一下了，较怕递归的问题

递归的本质是循环（个数可以不定），全排列的本质是两维循环。用一个递归解决两维循环很难。
编程的基本要求：
  1问：递归程序与非递归程序在编译成目标代码时有没有不同，回答没有，但不知道道理-----刚学编程
2问:递归程序与非递归程序在编译成目标代码时有没有不同，回答有，但不知道道理-----学了一年编程
3问：递归程序与非递归程序在编译成目标代码时有没有不同，回答没有，能知道为什么-----可以试试本题目