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

xaut3

郁闷 没人来给我加分！
, ]: P3 B- o* [6 J3 \1 }) ^假设{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]的全排列"。
5 \  ?: d/ k8 Y, |( G8 \$ N+ g　　令int list={1,2,3}，所以：
/ Q/ p- c8 H5 s8 b! d- X/ j4 k　　perm({1,2,3},0,2)=perm({1,2,3},1,2}，perm({2,1,3},1,2}，perm({3,2,1},1,3}；
- k, f0 ?/ R7 S; x1 ^
' K6 Q7 Z% G. l; K& S
; r, }2 \3 R" R/ r. J* p* S" ?　　理解了这个式子之后就可以写代码了：C源码 #include <stdio.h>
typedef int ElemType;

3 C% B* z3 }4 J& k+ P2 {void swap(ElemType *a,ElemType *b){
    //交换2个数
* r2 f% Y% A6 u9 j6 t) g    ElemType temp=*a;
    *a=*b;
& ^4 ^. i9 V' f4 o1 t2 `' ]( F- z    *b=temp;
; u3 ^4 b+ m* W! M* R& d}//swap

6 O0 X6 g$ h2 P- }void perm(ElemType list[],int begin,int end){
    int i=0;
6 ?! V) R0 s) V    if(begin==end){
        for(i=0;i<=begin;i++)
4 V3 H7 N+ P" r( Z            printf("%d ",list);
        printf("\n");
    }
    else
for(i=begin;i<=end;i++){
            swap(&list,&list[begin]);
            perm(list,begin+1,end);
            swap(&list,&list[begin]);
2 u5 m: X) ~$ ?% W4 {        }
}//perm
7 L# R8 h( }* C3 W. v; \
9 k1 H' a( D! |8 nvoid main(){
    ElemType list[]={1,2,3};
    perm(list,0,2);
* f; j4 F2 o, X+ n4 I; a}
  |+ v8 z9 c$ m7 n

, r4 g$ v' M+ z! I8 i! m
7 X1 x3 H$ I' R; _9 iC++代码 #include <iostream>

; l# H9 h: s  Ftemplate <class _Ty>
% \  w- e1 i* }/ c9 Mvoid perm(_Ty list[],int begin,int end){
. K, N$ r0 e  E" ]% t* ]    //输出前缀为"list[0..begin]"后缀为"list[begin+1..end]的全排列"---这名话很重要；
    //前缀是固定的，求后缀的时候要用递归求

if(begin==end){
        //如果相等，则表明前缀为list[0..end]，后缀就没有，所以直接输出前缀
) p, G  f2 p  N, O3 W, T1 ^! _% ~$ @
1 ]; R! u4 P. K- y, Ifor(int i=0;i<=begin;i++)
% J0 u9 \4 h' C, ^3 x- c2 k            std::cout<<list;
3 l6 M5 V: R0 A% C        std::cout<<std::endl;//输出一个之后，换行
    }
  d1 T3 ^/ Z5 q9 L5 Z    else{
        //如果不相等，就要循环(end-begin)次，每次前缀都不同

for(int i=begin;i<=end;i++){
9 T) D# f% n, ]% g; B            std::swap(list,list[begin]);//交换之后就可以得到前缀了
            perm(list,begin+1,end);//递归输出
1 k1 l$ B- T( l7 O            std::swap(list,list[begin]);//换回来
        }
    }
}
' }. l: P; y" Y+ i" p: ?, {% v1 y- V
+ z. k. n6 T) t+ {" d7 K1 ~% g& svoid main(){
$ A' f6 ~8 y! `0 b3 D' _# f- M    int list[]={1,2,3};
    perm(list,0,2);
  t  m& m6 h9 W1 `; K}
1 }/ ]' k, d# w* ~& d! Q
" {6 t$ P# }6 @2 Z; [/ S  F+ Q+ H+ o
C#源码 using System;
using System.Collections.Generic;
! K1 |  x$ ^  Q, p2 `
' o: P0 v8 U. ]3 @9 K7 V# enamespace CSharpDemo
{
+ r+ s3 x& P' s* Q/ X+ q4 x    class Program
    {
' j( |( y1 U# @4 {6 @        public
2 y% [5 R5 Y; ~% i( S, cstatic
void Swap<T>(ref T a, ref T b)
        {
8 `8 V' U3 y" M( A" ]; B3 ]; |            T temp = a;
4 \0 v, @6 }+ a+ _            a = b;
            b = a;
. }$ k8 X1 W- b* r        }
* s- m8 P2 C2 N5 ^2 i2 F
* M% F% X( P! _, T8 X* ]        public
static
void Perm<T>(T[] list, int begin, int end)
6 J; Q' ~- ^9 O        {
            if (begin == end)
            {
, Z. X: ~/ `! ?% d! _                for (int i =
0; i <= begin; i++)
                    Console.Write(list);
                Console.WriteLine();
            }
# O" o) i" G( L1 I, Z, \; f7 @7 c$ z            else
for (int i = begin; i <= end; i++)
                {
2 A" j% Q) r% d                    Swap<T>(ref list, ref list[begin]);
                    Perm<T>(list, begin+1, end);
( d; N5 [4 p0 b( Y' W                    Swap<T>(ref list, ref list[begin]);
& m) a. m+ L6 T. c                }
* J5 s* {; g& Y6 k6 F, u6 f  B        }
7 P+ h1 R1 W# I- }  n3 f9 f4 M
        static
void Main(string[] args)
        {
- K! ]; L0 U8 B# w4 l: v* Q            int[] list ={ 1, 2, 3 };
            Perm<int>(list, 0, 2);
        }
3 F* v, u8 J8 t3 }# H    }
}

jenny820210

来学习~ 准备用matlab编~