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

xaut3

郁闷 没人来给我加分！
3 h- p0 G6 x) D% G& D: X假设{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]的全排列"。
- d# {8 Q' W4 K0 D　　令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}；


3 N4 R1 N' Z5 A4 l0 z/ ?0 {- P　　理解了这个式子之后就可以写代码了：C源码 #include <stdio.h>
2 F! {# X/ ~, M: t' l) h- A2 A, S0 x8 ytypedef int ElemType;
6 |7 d: l- c; h0 ?' B" `
9 m7 ^' s# Z! @% L: Y2 Q3 Fvoid swap(ElemType *a,ElemType *b){
    //交换2个数
    ElemType temp=*a;
  r: |6 N" d- O$ S: ]    *a=*b;
    *b=temp;
2 s/ i2 v+ h5 c( s7 N$ Q}//swap

void perm(ElemType list[],int begin,int end){
    int i=0;
    if(begin==end){
" N% @, y: j- v) s        for(i=0;i<=begin;i++)
' o6 C8 g4 j; Q: i0 _: Z3 \            printf("%d ",list);
        printf("\n");
. w) T: d( b, A: K% ]/ R* n    }
8 k- g# t0 Q3 q2 n+ i7 `5 B    else
% h" B+ ^6 t& j$ T; e* P$ C! ?for(i=begin;i<=end;i++){
            swap(&list,&list[begin]);
7 v4 ]' p3 U' ?* C  o: w            perm(list,begin+1,end);
1 M6 _% w1 d( k            swap(&list,&list[begin]);
, |( p7 D# u6 ?  x        }
! D! G7 k5 S4 A+ X* P! A& |}//perm
5 I, i/ x* j6 n
void main(){
    ElemType list[]={1,2,3};
- w  L; c9 G. O( Z1 U% f9 r2 P* X    perm(list,0,2);
}

0 D& |7 O" @2 g! }" F

+ C( U5 d6 d$ i: g: \C++代码 #include <iostream>
1 o+ S- C9 w' l) r4 W
template <class _Ty>
void perm(_Ty list[],int begin,int end){
5 @+ s9 P" [- C2 ?' A; _    //输出前缀为"list[0..begin]"后缀为"list[begin+1..end]的全排列"---这名话很重要；
: s6 d7 |& e& |1 B    //前缀是固定的，求后缀的时候要用递归求
) ?9 `( b1 X7 S( |
if(begin==end){
; o0 {, n/ N3 _# H2 j6 F& a        //如果相等，则表明前缀为list[0..end]，后缀就没有，所以直接输出前缀
: }- ?2 O/ R! [& T' x
for(int i=0;i<=begin;i++)
9 S+ w% }3 P& U. M2 W$ i( ^- j            std::cout<<list;
        std::cout<<std::endl;//输出一个之后，换行
* v1 h8 _& ?; p; m* G) M* Q    }
    else{
9 ^6 j0 v4 D/ Q& Y% t* E7 D' |* X        //如果不相等，就要循环(end-begin)次，每次前缀都不同

for(int i=begin;i<=end;i++){
4 D7 T8 q: c3 n6 d            std::swap(list,list[begin]);//交换之后就可以得到前缀了
- `( ^" w, C4 L: s  ]- L& k+ p/ w            perm(list,begin+1,end);//递归输出
            std::swap(list,list[begin]);//换回来
        }
    }
2 u0 _- s! ?  F& y}

void main(){
    int list[]={1,2,3};
    perm(list,0,2);
}
- H- [) E9 F* G4 E. c/ F' n

C#源码 using System;
4 F7 w! L4 Z, c1 u; Z3 Rusing System.Collections.Generic;
+ j' t5 z1 Q' L1 }1 \* p
namespace CSharpDemo
5 ?4 ?# W& d- s) P1 e{
    class Program
    {
        public
static
% h; Z6 k+ K- W7 D) Mvoid Swap<T>(ref T a, ref T b)
        {
            T temp = a;
5 P6 _. f+ Z% w! T# ~$ B- I, I            a = b;
6 u8 A% m  D4 m! w& z. G7 r            b = a;
4 D+ K! D2 K2 i        }

; C) Z' h" T1 u% ^  V. K; ~! S. X; b+ O        public
static
void Perm<T>(T[] list, int begin, int end)
        {
2 V. r; D# R! P& {) [/ m; d            if (begin == end)
! I% b4 r% ^& g7 a) J: v% \1 ~, N            {
5 A% a4 \9 p) q# h                for (int i =
0 K1 V* V6 I, m; A0; i <= begin; i++)
                    Console.Write(list);
                Console.WriteLine();
            }
' ^4 z. i( [$ P) i; e            else
3 j  ^% P: \# U$ _for (int i = begin; i <= end; i++)
; H- V( V1 F" J6 o                {
                    Swap<T>(ref list, ref list[begin]);
$ W8 P0 A* _3 u$ d$ V; P                    Perm<T>(list, begin+1, end);
4 j3 g2 f* @( |. R! N                    Swap<T>(ref list, ref list[begin]);
/ F& Y8 y+ W! N" A: q( B( \( U                }
        }

0 ]  a. b2 F0 n* _/ v        static
void Main(string[] args)
& a7 @$ v  A. b: k/ n0 ]# G        {
  T; J8 x* ~: o: L            int[] list ={ 1, 2, 3 };
            Perm<int>(list, 0, 2);
/ {" X; H' J- A* r        }
1 B+ E* g; Q% Q& C: M, i. @    }
}
: ]2 K0 B9 H+ M3 Y

jenny820210

来学习~ 准备用matlab编~