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

xaut3

郁闷 没人来给我加分！
假设{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]的全排列"。
9 ^  n6 ^/ D# @1 q　　令int list={1,2,3}，所以：
$ q7 j; l) D3 k+ w' h) c- o5 K: Y　　perm({1,2,3},0,2)=perm({1,2,3},1,2}，perm({2,1,3},1,2}，perm({3,2,1},1,3}；
! j# I: \0 t8 [" a

+ B! Q: N9 ^# _7 D% ~& g4 m; R　　理解了这个式子之后就可以写代码了：C源码 #include <stdio.h>
typedef int ElemType;
+ J  C2 p5 B" V7 K2 D/ |
void swap(ElemType *a,ElemType *b){
7 f' ~* i) y9 K    //交换2个数
( u/ C8 _/ P+ h4 g/ Q, i    ElemType temp=*a;
    *a=*b;
8 \$ J9 z$ y7 F: z# a3 ~; I6 Z& f    *b=temp;
0 M# G/ L7 w) O: i& [1 f}//swap
+ V& x( j; V5 t3 T8 l5 a2 {
void perm(ElemType list[],int begin,int end){
    int i=0;
    if(begin==end){
3 h' L& K) R; J# L        for(i=0;i<=begin;i++)
4 M+ ?1 z/ E9 \2 M* x' r            printf("%d ",list);
( f+ Z. c! r8 W, S        printf("\n");
5 W: q5 _5 v* o    }
$ _  w7 O/ u. J0 x  g& @0 [    else
for(i=begin;i<=end;i++){
            swap(&list,&list[begin]);
0 B9 i, Y8 o; t0 b            perm(list,begin+1,end);
% F) Q* |0 L% f* \2 I) p            swap(&list,&list[begin]);
        }
4 x" v' w6 H- S: I( d  V}//perm
3 ]8 h5 o" i6 Y8 @$ O- H6 r
4 ^' r6 J- z! p  p2 @/ k( p: qvoid main(){
    ElemType list[]={1,2,3};
    perm(list,0,2);
2 _2 n) ?8 L7 d9 ^4 T& _}
; D& N$ G, E9 k$ W4 ^* P
$ U) P( z: |! a2 X4 l

# `$ x5 w! i7 ~# kC++代码 #include <iostream>
, i, o# K. |, s4 b0 V4 r8 t* P
template <class _Ty>
. O/ V7 ]1 B7 b: qvoid perm(_Ty list[],int begin,int end){
    //输出前缀为"list[0..begin]"后缀为"list[begin+1..end]的全排列"---这名话很重要；
    //前缀是固定的，求后缀的时候要用递归求

! Q) h5 e" }; F5 dif(begin==end){
' x% g4 c0 `6 X2 R8 \        //如果相等，则表明前缀为list[0..end]，后缀就没有，所以直接输出前缀

for(int i=0;i<=begin;i++)
9 \- ~. x. m7 v6 X6 t# o' m# h            std::cout<<list;
4 O+ P( k& A4 b- R- V+ S        std::cout<<std::endl;//输出一个之后，换行
# v4 e  a2 M$ O( @  y# `. L    }
" v$ s# K$ ~. g- W6 C4 P- ?, M" H    else{
        //如果不相等，就要循环(end-begin)次，每次前缀都不同

for(int i=begin;i<=end;i++){
# X3 @- C- W; _3 O1 J" H! Q            std::swap(list,list[begin]);//交换之后就可以得到前缀了
            perm(list,begin+1,end);//递归输出
            std::swap(list,list[begin]);//换回来
        }
    }
* N. N5 H+ V! D( T}
% D+ q, C# c# g/ V; t7 y& f2 X( C
* U4 T2 @2 I- A, b1 yvoid main(){
    int list[]={1,2,3};
: S7 V% d" {8 X/ m/ b    perm(list,0,2);
$ c- Z8 X' c/ [# q+ s! E( a* A9 K+ x}


! J$ C1 P* z, p8 ?: G! Z C#源码 using System;
: W1 T4 f+ G& j' Husing System.Collections.Generic;

namespace CSharpDemo
{
    class Program
    {
        public
% q, x* }7 F- \$ \static
void Swap<T>(ref T a, ref T b)
0 d9 v1 j# R( A# k        {
+ y0 R) [: G4 I8 M5 C6 b            T temp = a;
6 Y; G& L/ U/ k/ m            a = b;
            b = a;
        }

        public
static
void Perm<T>(T[] list, int begin, int end)
        {
( r) Y# q! E7 ?+ d' d            if (begin == end)
+ B7 E2 X4 M4 H. O- A5 b            {
. j# f, Q2 v: W' r                for (int i =
: a  ?( J% ^% f: h. b- y0; i <= begin; i++)
                    Console.Write(list);
  c; g. `$ y4 ]                Console.WriteLine();
            }
            else
" V+ S9 h. a% s" l/ gfor (int i = begin; i <= end; i++)
& T, h% `- I6 @1 z+ f                {
                    Swap<T>(ref list, ref list[begin]);
                    Perm<T>(list, begin+1, end);
5 f- I7 ~( E& p: }  e                    Swap<T>(ref list, ref list[begin]);
5 K( _% p  M5 P+ g9 _                }
1 ]4 z6 d& p8 T- F' H' i        }

2 h7 f6 r- e& {4 c        static
void Main(string[] args)
        {
, ^8 b2 ^, W2 R0 S6 T            int[] list ={ 1, 2, 3 };
" I! X2 T4 ~( Z/ V' z8 V1 p            Perm<int>(list, 0, 2);
/ `/ N+ K% R) \0 r& K( _        }
    }
}

jenny820210

来学习~ 准备用matlab编~