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

xaut3

郁闷 没人来给我加分！
( F/ T* y" u, g2 s- s1 @3 m9 V假设{1,2,3}表示1,2,3三个数的全排列，那么有下面的结果：
! o5 S5 H5 s% Z3 x# d; }% ~: F; N　　{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}，所以：
　　perm({1,2,3},0,2)=perm({1,2,3},1,2}，perm({2,1,3},1,2}，perm({3,2,1},1,3}；
2 ~% P. O+ o/ |+ `6 F- P- Y
* P, L0 ?0 y% Q: n. N
& v9 B) L0 ~6 ^" d. E4 F* O2 i% L( z　　理解了这个式子之后就可以写代码了：C源码 #include <stdio.h>
typedef int ElemType;
( i2 x3 a& B: _: }- ?/ A/ R
* T0 Q# I1 F1 K1 g7 Wvoid swap(ElemType *a,ElemType *b){
    //交换2个数
    ElemType temp=*a;
: {5 B) d/ J$ z" X, |    *a=*b;
    *b=temp;
. {. E/ e, C9 @5 p2 r}//swap

void perm(ElemType list[],int begin,int end){
, S1 O, N: c6 g3 T: e    int i=0;
    if(begin==end){
4 `2 H) l5 W6 {6 T( q8 V        for(i=0;i<=begin;i++)
+ C/ C4 O6 J/ q. |; r1 V/ y            printf("%d ",list);
        printf("\n");
* u9 B" e# M( U4 z- ?    }
( F+ _" d* [/ O/ s/ @    else
for(i=begin;i<=end;i++){
0 N( C0 S" _% ]3 o/ O( W            swap(&list,&list[begin]);
            perm(list,begin+1,end);
            swap(&list,&list[begin]);
# C+ \6 S4 d4 z" r/ M        }
}//perm
6 f) m! H: A6 \/ E& y* l1 k9 Y
void main(){
    ElemType list[]={1,2,3};
    perm(list,0,2);
}


' _  j$ @: e4 L, K3 W5 C8 j
; a* s% E# d5 b' |/ ?6 YC++代码 #include <iostream>

template <class _Ty>
void perm(_Ty list[],int begin,int end){
3 l% D+ W3 k) L! |    //输出前缀为"list[0..begin]"后缀为"list[begin+1..end]的全排列"---这名话很重要；
( G- l) M5 t; t7 [6 O$ C5 A    //前缀是固定的，求后缀的时候要用递归求
; V, I" P/ M1 G% A$ b7 m5 \
if(begin==end){
        //如果相等，则表明前缀为list[0..end]，后缀就没有，所以直接输出前缀

7 }9 S6 I& T/ I3 c" P, Sfor(int i=0;i<=begin;i++)
( Q1 z' s8 r2 i! p# k. Q  t3 Z            std::cout<<list;
/ f( o. U& L4 O) L$ I, P        std::cout<<std::endl;//输出一个之后，换行
    }
$ A6 w. w8 Q5 f" R2 Z' M2 V    else{
        //如果不相等，就要循环(end-begin)次，每次前缀都不同

7 L' V! r, A7 q5 X9 r6 j8 hfor(int i=begin;i<=end;i++){
3 y7 ?  b8 C; ^2 ~3 Y* G) ?! ~            std::swap(list,list[begin]);//交换之后就可以得到前缀了
+ w7 ^# w, c9 s$ H% L            perm(list,begin+1,end);//递归输出
            std::swap(list,list[begin]);//换回来
        }
2 y3 ~0 O" b. u' F! Y+ H0 f    }
}
# f$ f( h0 Y7 v8 Q
void main(){
    int list[]={1,2,3};
; p, B# W9 S) `4 O0 Z) P/ M    perm(list,0,2);
: v  K4 u7 L  X6 c! F. T/ m1 @}

  }3 o/ \! v. U) ^: `, v
C#源码 using System;
using System.Collections.Generic;
. f7 p% S- |' J- r$ e
namespace CSharpDemo
{
    class Program
    {
4 K. ^" N0 F- Q6 s4 z        public
static
- p8 ^# E; A( R# G/ j8 q- cvoid Swap<T>(ref T a, ref T b)
        {
            T temp = a;
* N2 g  r' @# f! c# y            a = b;
            b = a;
2 B7 M& `6 H9 {$ v) r        }

        public
4 j' ]2 R) ^+ [8 U( s1 b. |static
void Perm<T>(T[] list, int begin, int end)
        {
            if (begin == end)
7 o. V$ t* c( m) `! K' \5 @# K4 Z' ^            {
- B7 w" ^: i3 H8 e+ }. a8 n                for (int i =
; b- G/ _4 ~/ t! T; `0; i <= begin; i++)
                    Console.Write(list);
* j1 I% R( ^# \                Console.WriteLine();
            }
0 f8 R% }! P7 M7 ~. G' B/ P            else
for (int i = begin; i <= end; i++)
: F2 L1 M. @  M3 w                {
                    Swap<T>(ref list, ref list[begin]);
                    Perm<T>(list, begin+1, end);
) y# r/ t( O% R: g$ p2 C+ {                    Swap<T>(ref list, ref list[begin]);
' v1 M: l! ]8 I/ ~                }
6 f# e# b. m6 ~. a        }

        static
void Main(string[] args)
        {
            int[] list ={ 1, 2, 3 };
            Perm<int>(list, 0, 2);
0 e. a( A! s; l" y2 P; O        }
    }
$ |5 g! ]6 V2 j% P* y* i. V9 n}
9 k( I4 K& u2 O, t% F  m0 R7 f3 O, ~3 P

jenny820210

来学习~ 准备用matlab编~