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

xaut3

郁闷 没人来给我加分！
4 E8 x7 f  l8 A) P1 u+ W9 A; f6 u假设{1,2,3}表示1,2,3三个数的全排列，那么有下面的结果：
, |  J% B* W3 [3 i! E/ e4 `　　{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]的全排列"。
" e7 B. {, m2 Q2 Z# X  u% k; \6 W　　令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}；

  ?$ U2 Y7 C, w6 G# K  l
: h6 A) e* y6 H- ?! t　　理解了这个式子之后就可以写代码了：C源码 #include <stdio.h>
$ q* r6 n& G5 X4 Q! c2 ltypedef int ElemType;
/ Y& w( O; y3 s; t- ]
; T& Q! q* @& A, }# V9 a2 l! yvoid swap(ElemType *a,ElemType *b){
1 S% i+ H( ^) j0 q    //交换2个数
    ElemType temp=*a;
    *a=*b;
- L% Q+ w# m9 p" c* b; |. [    *b=temp;
}//swap

void perm(ElemType list[],int begin,int end){
    int i=0;
    if(begin==end){
        for(i=0;i<=begin;i++)
+ `: S# b4 k/ C            printf("%d ",list);
        printf("\n");
    }
    else
0 K# h4 }$ l/ o. B- i4 q6 D) u, {for(i=begin;i<=end;i++){
/ n8 b/ C4 g# Q5 \            swap(&list,&list[begin]);
) x% L5 @7 v- ]9 a  q( \            perm(list,begin+1,end);
            swap(&list,&list[begin]);
        }
2 {  O1 |) @: T$ e# ~}//perm
# T2 O( \% ^3 A8 F
8 M' G$ N1 @" Wvoid main(){
    ElemType list[]={1,2,3};
    perm(list,0,2);
+ y6 _4 F/ ?5 `! _9 N9 m5 j  q}
: Y6 @: L4 r0 F8 l* i: ?

2 a# C) W2 D1 W; f/ K- I
3 \  E6 w6 t: ], _C++代码 #include <iostream>

template <class _Ty>
void perm(_Ty list[],int begin,int end){
    //输出前缀为"list[0..begin]"后缀为"list[begin+1..end]的全排列"---这名话很重要；
/ `! O. F, }+ m' Z$ M/ }+ E5 o    //前缀是固定的，求后缀的时候要用递归求

if(begin==end){
# \) G, j; e; k6 ?        //如果相等，则表明前缀为list[0..end]，后缀就没有，所以直接输出前缀
; X( o0 n1 H: P* ~
for(int i=0;i<=begin;i++)
            std::cout<<list;
        std::cout<<std::endl;//输出一个之后，换行
) _( D, C! E7 b" h; X  s, ]+ Y2 r0 q    }
    else{
8 }+ u/ ~" c* S  ^        //如果不相等，就要循环(end-begin)次，每次前缀都不同
2 p  A) R1 l5 }- b
for(int i=begin;i<=end;i++){
; _# E9 b8 ^+ r6 @' D6 p) p            std::swap(list,list[begin]);//交换之后就可以得到前缀了
# a- n- F/ b: r4 w  X9 ~& d- d            perm(list,begin+1,end);//递归输出
            std::swap(list,list[begin]);//换回来
; O6 f. a. w( V# w$ n# e        }
    }
2 m* Z2 j! D# @! E: W8 z' U}
1 m8 x2 v7 N" a" f* [
9 l  E( D) |2 u" G. avoid main(){
; p% M9 i6 I. S' o% C- n    int list[]={1,2,3};
    perm(list,0,2);
. F! C1 V: @9 `}


C#源码 using System;
/ _5 {- t7 [3 g, z4 Rusing System.Collections.Generic;
' {; r9 n- K: q
& {* o2 x# t4 [7 u% qnamespace CSharpDemo
1 q7 c; z" A/ D. l+ J{
" s6 m6 |* q2 b2 d7 K    class Program
    {
, l/ g- o* d4 k+ X        public
$ @2 G, j' L$ M$ b1 Nstatic
( e: B0 o/ L  X2 c" t6 b3 I' q6 ]2 pvoid Swap<T>(ref T a, ref T b)
0 n# g0 z2 X; J/ ~+ b$ V* L: ?- z        {
5 u  \0 K% p! d1 ?, G            T temp = a;
% E8 f4 H+ b. y+ L: _            a = b;
) _+ k6 @  q" q6 [5 G4 q$ t/ c            b = a;
        }

6 L+ b  Y, l* B7 e        public
- P8 W$ B0 q% u3 S( O7 G2 b, Xstatic
$ w5 U5 Q4 ~! `$ m& _void Perm<T>(T[] list, int begin, int end)
& O, B& N6 u' f2 Q& W        {
            if (begin == end)
3 K) `! x4 V* a. `# M; [! T+ F/ B            {
                for (int i =
0; i <= begin; i++)
! z, W. T! a6 v' m* O7 e                    Console.Write(list);
                Console.WriteLine();
  Y  s& e; y' w! H            }
            else
8 K5 F# t8 G: H- H3 Mfor (int i = begin; i <= end; i++)
) N- h# p; `* k5 R: [" ]                {
, X  v' X1 I/ ]& _6 T, d2 K2 s                    Swap<T>(ref list, ref list[begin]);
2 f. F3 e6 r5 o0 B) U                    Perm<T>(list, begin+1, end);
                    Swap<T>(ref list, ref list[begin]);
                }
( S7 b, b; g7 A# j' n% C1 l        }
0 u; J8 w7 a; W$ ?0 |: v
        static
1 \6 z) O/ t6 ?9 Ivoid Main(string[] args)
( r! V. m2 T7 y: G9 s        {
( c4 U$ P1 i$ K( T# m  N- ~2 d            int[] list ={ 1, 2, 3 };
+ I7 p) c4 D& c' i9 f            Perm<int>(list, 0, 2);
        }
    }
}
3 B/ M( h2 ?. L/ U) q) Y/ ^! u

jenny820210

来学习~ 准备用matlab编~