求一函数,急~~~!!!!在线等

黄昏

从排列组合得观念中，我们知道，若N个字母要排列，可能的情形有N!（N * (N-1)         * (N-2) .....* 2 * 1 ）个
        例如：a,b,c,d 个数排列可能有 4! = 4*3*2*1 = 24个
        所有可能的情形是：
        a,b,c,d                b,a,c,d                c,a,b,d                d,a,b,c
        a,b,d,c                b,a,d,c                ....                        ....
        a,d,b,c                b,d,a,c                ....                        ....
        a,d,c,b                b,d,c,a                ....                        ....
        a,c,b,d                ....                        ....                        ....
        a,c,d,b                ....                        ....                        ....
       
        这里介绍一种演算法
        如果有两个数（1, 2）要排序，结果是：
        [1, 2] => (1,2) , (2,1)

        当第三个数(3)加进来后。
        只要在原有的所有可能排序（前，中，.....后)都插入新的数字，
        即可找出其所有可能行。结果是：
        [1,2,3] =>         (1,2) + 3 => (3,1,2) , (1,3,2), (1,2,3)
                          (2,1) + 3 => (3,2,1), (2,3,1), (2,1,3)

        问题是：
        请用你最熟悉的程式语言写一个函数 arrayInsert()
        传入一个一维的阵列与一个字元，会将这个字元插入一维的阵列中的所有可能性传出
                例如： 传入一维的阵列arr（arr = { “1”,”2'”}） 与 字元 'X'
                会传出二维的阵列 ：
                        {
                                {“X”, “1”, “2”} ,
                                {“1”, “X”, “2”} ,
                                {“1”, “2”, “X”}
                        }

jeffwang8001

以前看数据结构的时候，有这样一个题目，好像它是用递归来做的

yovn

不考虑重复元素的话，就是个全排列的问题。

传入一维的阵列arr（arr = { “1”,”2'”}） 与 字元 'X'

其实就是，{1,2,X}的全排列

给定一个一维数组 A1,A2....AN，求出所有的可能排列:
1）当N=1
就直接返回{{A1}}
2）当N>1时，取出 A1
剩下的元素作一个全排列，返回全部可能的数组排列（二维数组）假如为RET[j][k]
那么，对其中每一个数组
RET[j]={ r1,r2,r3,r4....rm }
插入A1 到这个数组(RET[j])的每一个可能位置(可能位置为数组长度加1)
这样得到二维数组RET[j*(k+1)][k+1]就是所求的全排列


Java实现：

1. 
   
2. public class Test {
   
3. 
   
4.         /**
   
5.          * @param args
   
6.          *
   
7.          */
   
8.         public static void main(String[] args) throws Exception {
   
9.                 int testa[]={1,2,3,4};
   
10.                 int[][] ret=align(testa,0,4);
    
11.                 printTDArray(ret);
    
12.                
    
13.         }
    
14.                
    
15.         private static void printTDArray(int[][] a)
    
16.         {
    
17.                 StringBuffer buffer=new StringBuffer("{\n");
    
18.                 for(int j=0;j<a.length;j++)
    
19.                 {
    
20.                         buffer.append("{");
    
21.                         for(int k=0;k<a[j].length;k++)
    
22.                         {
    
23.                                 buffer.append(a[j][k]);
    
24.                                 if(k<a[j].length-1)
    
25.                                 {
    
26.                                         buffer.append(",");
    
27.                                 }
    
28.                         }
    
29.                         buffer.append("}\n");
    
30.                 }
    
31.                 buffer.append("}");
    
32.                 System.out.println(buffer.toString());
    
33.                
    
34.         }
    
35.                
    
36.         public static int[][] arrayAlignInsert(int a[],int x)
    
37.         {
    
38.                 int[][] ret=align(a,0,a.length);
    
39.                 ret=arrayInsert(ret,x);
    
40.                 return ret;
    
41.                
    
42.         }
    
43.        
    
44.         public static int[][] align(int[] a,int off,int len)
    
45.         {
    
46.                 if(len==0)
    
47.                 {
    
48.                         throw new IllegalArgumentException();
    
49.                 }
    
50.                 if(len==1)
    
51.                 {
    
52.                         int[][] ret=new int[1][1];
    
53.                         ret[0]=new int[1];
    
54.                         ret[0][0]=a[off];
    
55.                         return ret;
    
56.                 }
    
57.                 int[][] preRet=align(a,off+1,len-1);
    
58.                 return arrayInsert(preRet,a[off]);
    
59.                        
    
60.         }
    
61.         private static int[][] arrayInsert(int[][] preRet,int toInsert)
    
62.         {
    
63.                 int[][] toRet=new int[preRet.length*(preRet[0].length+1)][preRet[0].length+1];
    
64.                 for(int k=0;k<preRet.length;k++)
    
65.                 {
    
66.                         for(int j=0;j<=preRet[0].length;j++)
    
67.                         {
    
68.                                 toRet[k*(preRet[0].length+1)+j]=inertOneAtPos(preRet[k],j,toInsert);
    
69.                         }
    
70.                 }
    
71.                 return toRet;
    
72.         }
    
73.        
    
74.         private static int[] inertOneAtPos(int[] arr,int pos,int toInsert)
    
75.         {
    
76.                 int ret[]=new int[arr.length+1];
    
77.                 if(pos>0)
    
78.                 {
    
79.                         System.arraycopy(arr, 0, ret, 0, pos);
    
80.                 }
    
81.                 ret[pos]=toInsert;
    
82.                 if(pos<arr.length)
    
83.                 {
    
84.                         System.arraycopy(arr, pos, ret, pos+1, arr.length-pos);
    
85.                 }
    
86.                 return ret;
    
87.                
    
88.         }
    
89. 
    
90. }
    

复制代码

输出：

1. 
   
2. {
   
3. {1,2,3,4}
   
4. {2,1,3,4}
   
5. {2,3,1,4}
   
6. {2,3,4,1}
   
7. {1,3,2,4}
   
8. {3,1,2,4}
   
9. {3,2,1,4}
   
10. {3,2,4,1}
    
11. {1,3,4,2}
    
12. {3,1,4,2}
    
13. {3,4,1,2}
    
14. {3,4,2,1}
    
15. {1,2,4,3}
    
16. {2,1,4,3}
    
17. {2,4,1,3}
    
18. {2,4,3,1}
    
19. {1,4,2,3}
    
20. {4,1,2,3}
    
21. {4,2,1,3}
    
22. {4,2,3,1}
    
23. {1,4,3,2}
    
24. {4,1,3,2}
    
25. {4,3,1,2}
    
26. {4,3,2,1}
    
27. }
    

复制代码

[ 本帖最后由 yovn 于 2007-1-26 18:08 编辑 ]

javacodefan

我来写一个C++版的，同样功能！

1. 
   
2. #include <iostream>
   
3. using namespace std;
   
4. const int len = 4;
   
5. 
   
6. void fun(int *array,int high)
   
7. {
   
8.         if(high==len-1)
   
9.         {
   
10.                 for(int i=0;i<len;i++)
    
11.                 cout<<array[i]<<"  ";
    
12.                 cout<<endl;
    
13.         }       
    
14.        
    
15.         for(int i=high;i<len;i++)
    
16.         {               
    
17.                 int temp=array[high];
    
18.                 array[high]=array[i];
    
19.                 array[i]=temp;
    
20.                 fun(array,high+1);
    
21.                 temp=array[high];
    
22.                 array[high]=array[i];
    
23.                 array[i]=temp;
    
24.         }
    
25. }
    
26. 
    
27. void main()
    
28. {
    
29.         int array[len]={1,2,3,4};
    
30.         fun(array,0);       
    
31. }
    
32. 
    
33. /*结果
    
34. 
    
35. 1  2  3  4  
    
36. 1  2  4  3  
    
37. 1  3  2  4  
    
38. 1  3  4  2  
    
39. 1  4  3  2  
    
40. 1  4  2  3  
    
41. 2  1  3  4  
    
42. 2  1  4  3  
    
43. 2  3  1  4  
    
44. 2  3  4  1  
    
45. 2  4  3  1  
    
46. 2  4  1  3  
    
47. 3  2  1  4  
    
48. 3  2  4  1  
    
49. 3  1  2  4  
    
50. 3  1  4  2  
    
51. 3  4  1  2  
    
52. 3  4  2  1  
    
53. 4  2  3  1  
    
54. 4  2  1  3  
    
55. 4  3  2  1  
    
56. 4  3  1  2  
    
57. 4  1  3  2  
    
58. 4  1  2  3  
    
59. */
    

复制代码

原帖由 yovn 于 2007-1-26 17:58 发表
不考虑重复元素的话，就是个全排列的问题。


其实就是，{1,2,X}的全排列

给定一个一维数组 A1,A2....AN，求出所有的可能排列:
1）当N=1
就直接返回{{A1}}
2）当N>1时，取出 A1
剩下的元素作一个全 ...

[ 本帖最后由 javacodefan 于 2007-1-27 00:37 编辑 ]

javacodefan

看来C/C++比Java要简洁一些，呵呵！
个人之见！！

yovn

原帖由 javacodefan 于 2007-1-27 01:01 发表
看来C/C++比Java要简洁一些，呵呵！
个人之见！！

这个算法是经典的解法，没有语言之分。也没有返回结果，而只是在算法的运算中直接打印出来。

这个算法描述应该是这样的：
1）固定前K个元素
2）如果K为数组的长度减一，那么显然剩下的一个元素只有一个可能。于是可以打印出来
3）要不然可以让第K个元素跟K与末尾元素间的每个元素交换，这样固定前K+1个元素，然后递归求解。

算法的开始时，任何元素都没有固定，也就是传的参数为0。