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

xaut3

郁闷 没人来给我加分！
4 l: N( ~# Z' e4 r假设{1,2,3}表示1,2,3三个数的全排列，那么有下面的结果：
! k. L) T3 J* A0 n1 d2 F' K* U; 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}；

# U6 y0 Y+ l# e0 I# F& }
& p8 O7 t- O7 ?　　理解了这个式子之后就可以写代码了：C源码 #include <stdio.h>
1 R: c) r, B6 j; D" Stypedef int ElemType;

void swap(ElemType *a,ElemType *b){
    //交换2个数
    ElemType temp=*a;
" C( ^$ X( a1 ]3 e# m: T6 v+ B    *a=*b;
    *b=temp;
}//swap
( k5 ?# U7 r, l# J/ c" k
0 _* G% C8 V- G& k4 O. mvoid perm(ElemType list[],int begin,int end){
    int i=0;
* ]8 c# r0 ~5 f3 b8 x" j! g    if(begin==end){
        for(i=0;i<=begin;i++)
            printf("%d ",list);
        printf("\n");
3 j% }( k" Z3 y9 ]0 r4 Q    }
    else
: q6 T2 y' Z, z# _for(i=begin;i<=end;i++){
            swap(&list,&list[begin]);
: `  t8 I  Q5 z. Z$ T            perm(list,begin+1,end);
            swap(&list,&list[begin]);
7 q6 I0 r4 P1 |7 a- P        }
}//perm
; o# m* S! S8 F; R/ L; ]* M5 X
void main(){
    ElemType list[]={1,2,3};
; b: ~$ ~( ^) r6 ~" j    perm(list,0,2);
}
2 t% @/ p" [. R. _
* t$ f3 |& T/ l) O$ T  q" V6 n9 e1 {
) r7 x+ a. C7 o  ]$ o
& L( w" i$ a, U3 e! ]' p5 }% |" I8 ]C++代码 #include <iostream>

. T  y- ~' @* n/ Dtemplate <class _Ty>
  O5 \( N' f" vvoid perm(_Ty list[],int begin,int end){
7 g( }' W  v  [  f0 ^$ ]    //输出前缀为"list[0..begin]"后缀为"list[begin+1..end]的全排列"---这名话很重要；
  V1 }/ Y* H0 T, V2 h    //前缀是固定的，求后缀的时候要用递归求
5 ^1 Y- \/ f4 V" o+ ?6 h
5 V) X5 k; t$ K/ z7 W  q* q6 A+ {if(begin==end){
        //如果相等，则表明前缀为list[0..end]，后缀就没有，所以直接输出前缀

for(int i=0;i<=begin;i++)
            std::cout<<list;
( d, }" I# C* O* j) @  k# d$ |        std::cout<<std::endl;//输出一个之后，换行
  M5 X  s) U1 l1 _" y' S    }
    else{
        //如果不相等，就要循环(end-begin)次，每次前缀都不同

for(int i=begin;i<=end;i++){
            std::swap(list,list[begin]);//交换之后就可以得到前缀了
$ p: I* O, |' r  J+ u8 l6 Y            perm(list,begin+1,end);//递归输出
* o( }4 d! L* v4 d/ R7 n            std::swap(list,list[begin]);//换回来
        }
    }
5 ^/ x( L7 h; T# L1 Q}

3 t2 r7 H0 e4 l/ x/ _! Xvoid main(){
( y% Y  u& E/ A. Q2 \+ z; W2 d    int list[]={1,2,3};
    perm(list,0,2);
}
# {  W+ I9 c8 e
  r8 M) b2 m( O8 @. |0 j$ X
C#源码 using System;
- `! k, E0 m3 ~( u" l" Ausing System.Collections.Generic;
7 Q0 X9 K7 A/ ~2 B/ ~" i
namespace CSharpDemo
{
+ j( E$ Y% @8 A, T    class Program
2 }( R* q: B! N% T/ l- Q    {
        public
% x$ _. _$ s) ?4 ?$ p; C( pstatic
, N. {8 o( H$ `) @6 lvoid Swap<T>(ref T a, ref T b)
+ N. Z  l8 `5 u5 o. X        {
8 \  a" K* _5 Q8 A( `! |9 d            T temp = a;
4 i+ A6 ~" X2 k5 K% y- a0 Y            a = b;
            b = a;
        }
) u8 e  i$ d+ N: A1 Z
% p5 |) c6 b9 K0 \$ V  V        public
static
void Perm<T>(T[] list, int begin, int end)
, F6 `- c$ _1 J        {
            if (begin == end)
: k+ Z, L. _1 R! J            {
                for (int i =
0; i <= begin; i++)
( _4 |" N, P0 I5 Q                    Console.Write(list);
                Console.WriteLine();
; d, h3 S# P" O            }
: Q% @' c' B7 Y& O" C- j4 @% I) B6 H            else
for (int i = begin; i <= end; i++)
                {
) f2 k8 o: s9 `2 Y" [+ Z                    Swap<T>(ref list, ref list[begin]);
: m9 V" \' b) Q8 T; l                    Perm<T>(list, begin+1, end);
& |3 g+ h7 Q$ g: h                    Swap<T>(ref list, ref list[begin]);
                }
        }

* }; K  Q1 R% h, c        static
1 q2 u4 f9 k6 K+ {$ ~void Main(string[] args)
        {
            int[] list ={ 1, 2, 3 };
3 a& U9 k) i9 v! @' H            Perm<int>(list, 0, 2);
# j7 b9 `9 G7 o) v* d: m4 n, j        }
    }
+ X/ X0 c. d& P/ ]* G* i}
/ D, V# C' k1 n, N# ~/ ]$ `

jenny820210

来学习~ 准备用matlab编~