C\C++\C#实现求全排列

xaut3

郁闷 没人来给我加分！
! R* Q9 n  }* B6 M6 `- e* h假设{1,2,3}表示1,2,3三个数的全排列，那么有下面的结果：
　　{1,2,3}=1{2,3}，2{1,3}，3{1,2} 也就是说求1,2,3有全排列由三个部分组成了分别为1{2,3}，2{1,3}，3{1,2}，大括号前面的称为前缀。一直递归下去就可求出结果。所以假设perm(int list[],int begin,int end)表示输出前缀为"list[0,begin]"后缀为"list[begin+1,end]的全排列"。
　　令int list={1,2,3}，所以：
* @! Y- @& X4 R) u" a6 R　　perm({1,2,3},0,2)=perm({1,2,3},1,2}，perm({2,1,3},1,2}，perm({3,2,1},1,3}；


　　理解了这个式子之后就可以写代码了：C源码 #include <stdio.h>
: \+ Q% A5 }1 {6 t9 X* vtypedef int ElemType;
1 w0 q3 |* j. r
, e4 k9 c. _4 cvoid swap(ElemType *a,ElemType *b){
( A6 [/ @, w* m6 Q  Y. _+ B    //交换2个数
7 H- @- y1 l# @. M    ElemType temp=*a;
    *a=*b;
    *b=temp;
}//swap
- R( [0 [5 c( {1 x4 o3 ~
6 O7 W0 I9 S) ]( g: W* Fvoid perm(ElemType list[],int begin,int end){
    int i=0;
    if(begin==end){
        for(i=0;i<=begin;i++)
            printf("%d ",list);
7 U% J* T2 l1 j2 P3 E( H        printf("\n");
. I2 D7 E0 D( T. B. Q* o- O    }
9 a, E/ m, a0 `) J    else
for(i=begin;i<=end;i++){
            swap(&list,&list[begin]);
2 P8 d8 J5 l3 N1 b            perm(list,begin+1,end);
$ q4 X0 L4 X& h            swap(&list,&list[begin]);
        }
}//perm
& u- v' @' L( ~+ d% v& W  }
void main(){
* c0 A- K4 W. I    ElemType list[]={1,2,3};
6 X* O/ [+ K9 Q/ H    perm(list,0,2);
& ?$ V3 d9 K/ l1 ]7 H0 t1 t}
  l, f- r: ]% D, Q+ v; S, W5 t7 I
4 g( N8 q, F% e- k. h6 w& i$ X

0 d& B& L' w. EC++代码 #include <iostream>
8 m  T# f  L/ ]; R' S2 ]
8 s, _. E) |. `6 b4 N. ctemplate <class _Ty>
1 L& g1 S' r1 e3 c" ^6 pvoid perm(_Ty list[],int begin,int end){
( e5 f- X3 F: Z" V! E4 V    //输出前缀为"list[0..begin]"后缀为"list[begin+1..end]的全排列"---这名话很重要；
6 b' a+ k9 C( W# G, [. c5 c    //前缀是固定的，求后缀的时候要用递归求

if(begin==end){
        //如果相等，则表明前缀为list[0..end]，后缀就没有，所以直接输出前缀

for(int i=0;i<=begin;i++)
# K! M% \. G% t' ^8 Q            std::cout<<list;
6 B  [, ]2 i( M) h        std::cout<<std::endl;//输出一个之后，换行
    }
7 j6 q- Q4 _6 c# U    else{
        //如果不相等，就要循环(end-begin)次，每次前缀都不同

for(int i=begin;i<=end;i++){
- ?' f% R* G0 j! E            std::swap(list,list[begin]);//交换之后就可以得到前缀了
/ i, _9 S4 P5 t! q% M& b/ w8 o* l            perm(list,begin+1,end);//递归输出
            std::swap(list,list[begin]);//换回来
        }
    }
; o5 s9 F. K- u}
! r+ P; g5 i; L5 i' t/ a/ k9 l
$ ^  g, O8 f, S2 J4 }void main(){
    int list[]={1,2,3};
5 Q/ e) w" z% y    perm(list,0,2);
4 h  ?* ?$ c0 J* \5 @}

6 c, M, X% Q9 ~* t9 _
" d* ^) D0 ?! q6 g C#源码 using System;
' g$ f4 |8 s' T2 l/ V  B+ X9 ~! _using System.Collections.Generic;

9 O  S7 B; h- ~, s: Enamespace CSharpDemo
/ V( l' X0 W* c/ c3 a4 g{
* L  A6 _$ S- `0 R5 K    class Program
4 s9 u3 P. w" c& e1 |# L1 V    {
        public
- p0 e+ ^  a6 K, S7 S/ ]% {static
void Swap<T>(ref T a, ref T b)
        {
            T temp = a;
/ @- H0 Z5 p  q3 Y  d, F9 }- `5 Z7 @4 d            a = b;
6 ?4 ^( x3 @$ ]; v( N& s1 D/ T+ p            b = a;
        }

        public
static
' g% o8 q2 C3 G: `4 m( ivoid Perm<T>(T[] list, int begin, int end)
        {
. u. I, @7 i8 a1 S: E            if (begin == end)
            {
                for (int i =
0; i <= begin; i++)
6 @# n6 Q' u) D) B8 X! R5 M& s                    Console.Write(list);
                Console.WriteLine();
  ?7 D3 p- n- j4 X            }
            else
for (int i = begin; i <= end; i++)
/ r7 t- _. G9 w) X) k3 s                {
                    Swap<T>(ref list, ref list[begin]);
                    Perm<T>(list, begin+1, end);
$ `* K3 G/ f. e7 P% Y                    Swap<T>(ref list, ref list[begin]);
5 B# ]* u1 D5 e7 |& ^9 C: V: s6 X                }
9 j' z8 o, ]4 v+ Q# j6 v. V        }

        static
void Main(string[] args)
0 r/ t0 v/ ]+ O0 ~/ P        {
            int[] list ={ 1, 2, 3 };
            Perm<int>(list, 0, 2);
& u. o3 ~+ F2 s' |' [% \6 w5 B        }
    }
}

jenny820210

来学习~ 准备用matlab编~