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

xaut3

郁闷 没人来给我加分！
假设{1,2,3}表示1,2,3三个数的全排列，那么有下面的结果：
. j- k6 n: e% i+ p. H( O　　{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]的全排列"。
! H1 Y. ]; u/ S　　令int list={1,2,3}，所以：
' J# N# E8 K* ]. ?4 b4 T5 _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}；


* S! D/ j6 X. n+ s7 M) x# j  z　　理解了这个式子之后就可以写代码了：C源码 #include <stdio.h>
typedef int ElemType;

4 j, `* r, P: Q; `+ K$ ovoid swap(ElemType *a,ElemType *b){
    //交换2个数
# E2 x# ^9 c- P; T9 g    ElemType temp=*a;
    *a=*b;
    *b=temp;
}//swap
* S* {3 b, R+ @# D+ ~0 _
void perm(ElemType list[],int begin,int end){
    int i=0;
    if(begin==end){
        for(i=0;i<=begin;i++)
            printf("%d ",list);
        printf("\n");
    }
    else
for(i=begin;i<=end;i++){
            swap(&list,&list[begin]);
: o, f  d7 e+ H* l0 L4 ]            perm(list,begin+1,end);
            swap(&list,&list[begin]);
+ d3 d' a0 ]6 y  a        }
}//perm
5 o% @0 q6 l# |2 s4 Y% H% k& A
3 o+ {( k" ?! b) }void main(){
    ElemType list[]={1,2,3};
' |7 [9 M3 L4 Z) ]. \; M    perm(list,0,2);
, b2 z9 v2 ?% u5 a7 @}

: V, P; p, q& I( I5 b
- D  _1 G" ~$ ]4 Y3 W3 J
! a6 R+ Q& k* ^4 d7 G6 L- b4 yC++代码 #include <iostream>

template <class _Ty>
void perm(_Ty list[],int begin,int end){
    //输出前缀为"list[0..begin]"后缀为"list[begin+1..end]的全排列"---这名话很重要；
    //前缀是固定的，求后缀的时候要用递归求
" i4 }7 x( b% N" i
if(begin==end){
( i+ U, }9 D% j6 V/ a2 a. c* [        //如果相等，则表明前缀为list[0..end]，后缀就没有，所以直接输出前缀
1 Q3 w( P0 `% J
for(int i=0;i<=begin;i++)
            std::cout<<list;
        std::cout<<std::endl;//输出一个之后，换行
    }
    else{
7 k3 u. L1 `; u        //如果不相等，就要循环(end-begin)次，每次前缀都不同

for(int i=begin;i<=end;i++){
            std::swap(list,list[begin]);//交换之后就可以得到前缀了
            perm(list,begin+1,end);//递归输出
) p- M; U* ~9 n) }            std::swap(list,list[begin]);//换回来
% l) u8 W9 n4 G* Z7 x- l+ G9 J9 E        }
    }
$ X$ `5 c& z& B7 L  ?6 Q# d. U( ?- q}

void main(){
6 S( J' |  m) s! b$ L    int list[]={1,2,3};
# T6 x% Q4 }/ ~    perm(list,0,2);
}


C#源码 using System;
using System.Collections.Generic;

namespace CSharpDemo
{
    class Program
4 @. ?5 R  h0 j$ x  s* c    {
        public
- M: z6 A; _( V. ?$ |static
* h' r4 Z) f( @9 Q' M' m+ c6 bvoid Swap<T>(ref T a, ref T b)
        {
; O. P: I: _2 I3 s. B            T temp = a;
* o! k! g3 ?/ U! P1 C            a = b;
6 ^/ p& I. w# w. |7 u1 P            b = a;
        }
. [; ]5 N- S0 v/ T$ v9 |
        public
( j7 c/ ?' B& X& B8 G2 ustatic
void Perm<T>(T[] list, int begin, int end)
; n6 g# s- e7 L% A0 A' z# ?        {
) ^4 z) r. H9 @7 N7 g7 v) {6 Q            if (begin == end)
" n, A7 D4 E, p, ^9 l            {
9 g( A/ n" S6 l; @$ H- `! J0 p                for (int i =
$ M2 E# |: e$ v2 F& [7 O+ }% l7 b0; i <= begin; i++)
                    Console.Write(list);
                Console.WriteLine();
            }
3 M. p" X7 i% v3 n9 D& O- m8 O            else
for (int i = begin; i <= end; i++)
$ \' }" t9 y, O) G/ N3 Q" s                {
                    Swap<T>(ref list, ref list[begin]);
                    Perm<T>(list, begin+1, end);
  D$ `1 g- J- |                    Swap<T>(ref list, ref list[begin]);
                }
        }

; p4 f1 S2 B8 ^& W6 |4 u4 s- W        static
$ @1 c/ _7 L8 V( ^# Qvoid Main(string[] args)
) D- ~5 z6 p7 Q3 n" ?        {
# a; \1 V6 O: p- a! @/ A$ o            int[] list ={ 1, 2, 3 };
' {# I# ]7 m8 r& z( P4 m: v            Perm<int>(list, 0, 2);
8 q. Y* x, Y1 b; X1 F  L5 P; J0 E' v8 p        }
    }
# Z3 e/ C" W+ C* H: P/ H4 D}

jenny820210

来学习~ 准备用matlab编~