设为首页收藏本站|繁體中文 快速切换版块

 找回密码
 立即加入
搜索
查看: 1019|回复: 1

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

[复制链接]
  • TA的每日心情
    慵懒
    2016-4-21 12:07
  • 签到天数: 3 天

    连续签到: 1 天

    [LV.2]偶尔看看I

    累计签到:3 天
    连续签到:1 天
    发表于 2010-5-4 10:16:03 | 显示全部楼层 |阅读模式

    马上加入,结交更多好友,共享更多资料,让你轻松玩转电力研学社区!

    您需要 登录 才可以下载或查看,没有账号?立即加入

    ×
    郁闷 没人来给我加分!
    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]的全排列"。3 |8 T# x8 ?2 s/ R5 Z
      令int list={1,2,3},所以:$ e1 i$ V, ^, l7 M
      perm({1,2,3},0,2)=perm({1,2,3},1,2},perm({2,1,3},1,2},perm({3,2,1},1,3};+ U8 Z7 j# H, o

    # 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;* u. t# i* s  m- Z" B+ w$ ^8 q
    ; |1 ^- K" m0 O! w% |4 c# {5 O
    void swap(ElemType *a,ElemType *b){$ [. j% l% n4 w
       
    //交换2个数% X6 W; S! u: O
        ElemType temp=*a;
    " C( ^$ X( a1 ]3 e# m: T6 v+ B   
    *a=*b;+ B2 O' K* `* b. L" l: Q. i+ M6 H
       
    *b=temp;  ~  m$ F" \! m
    }//swap
    ( k5 ?# U7 r, l# J/ c" k
    0 _* G% C8 V- G& k4 O. mvoid perm(ElemType list[],int begin,int end){, w$ i$ u4 f# e# ?2 i" q* v1 p8 N, }
       
    int i=0;
    * ]8 c# r0 ~5 f3 b8 x" j! g   
    if(begin==end){+ ^, n4 I8 \6 T7 o' ]9 W* v
            
    for(i=0;i<=begin;i++)1 @( N$ z( Y* X0 G
                printf("%d ",list);6 B- \7 j5 n: L4 P
            printf("\n");
    3 j% }( k" Z3 y9 ]0 r4 Q
        }: Q, S* o* e% ?
       
    else
    : q6 T2 y' Z, z# _for(i=begin;i<=end;i++){6 w; ]# ^: ?9 d% H' f
                swap(&list,&list[begin]);
    : `  t8 I  Q5 z. Z$ T
                perm(list,begin+1,end);( T) x5 r% K* I! w1 b
                swap(&list,&list[begin]);
    7 q6 I0 r4 P1 |7 a- P
            }" g' L$ C4 A+ {1 y
    }//perm
    ; o# m* S! S8 F; R/ L; ]* M5 X1 [+ M7 ^0 @' c: x7 ~
    void main(){& K) G9 {- M& {" ]& ^
        ElemType list[]={1,2,3};
    ; b: ~$ ~( ^) r6 ~" j
        perm(list,0,2);2 _& b. S0 T0 n2 T
    }
    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>! X4 B: J- ]7 ]8 f7 ^7 W7 S

    . 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){+ o: z7 w7 n3 Z# B
            
    //如果相等,则表明前缀为list[0..end],后缀就没有,所以直接输出前缀5 y) A0 `0 P0 u+ k* s3 P; a6 A
    ; D! h6 N: P$ t
    for(int i=0;i<=begin;i++)8 v: f5 O1 |, C5 A. }  y  K: U
                std::cout
    <<list;
    ( d, }" I# C* O* j) @  k# d$ |        std::cout
    <<std::endl;//输出一个之后,换行
      M5 X  s) U1 l1 _" y' S    }' q) m3 N6 C5 G" U6 i- b( q% `
       
    else{5 g2 K+ r6 s% @9 g) N% E- M2 d
            
    //如果不相等,就要循环(end-begin)次,每次前缀都不同" u' I$ b: B! E- i8 r6 X
    8 [, u4 {% q9 m& C! O
    for(int i=begin;i<=end;i++){* Z& z' I/ x" p, }+ k- A" L1 M0 h
                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]);//换回来: F% L# c' d  \" k/ h9 H4 Z' _
            }8 K; @) `8 c8 y& \' o+ ~4 y  E
        }
    5 ^/ x( L7 h; T# L1 Q}- C- |( k8 K  R# R. m- M" z

    3 t2 r7 H0 e4 l/ x/ _! X
    void main(){
    ( y% Y  u& E/ A. Q2 \+ z; W2 d   
    int list[]={1,2,3};) Y( f& D  X' K6 p, B, ]
        perm(list,
    0,2);1 @' b% u) d2 B1 V! _; O* W) B$ b* q
    }

    # {  W+ I9 c8 e
      r8 M) b2 m( O8 @. |0 j$ X) r, z1 G0 o) L' T
    ContractedBlock.gif ExpandedBlockStart.gif C#源码 using System;
    - `! k, E0 m3 ~( u" l" A
    using System.Collections.Generic;
    7 Q0 X9 K7 A/ ~2 B/ ~" i0 F- g6 S, d9 b1 d! @
    namespace CSharpDemo0 R' E& T* |3 B; r% a% x# j, ~$ G
    {
    + j( E$ Y% @8 A, T   
    class Program
    2 }( R* q: B! N% T/ l- Q    {7 ^, A6 i2 L+ Z4 K" D
            
    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;; H# \+ p) x. s' v
                b
    = a;8 `5 v6 r" Z  U/ ?
            }
    ) u8 e  i$ d+ N: A1 Z
    % p5 |) c6 b9 K0 \$ V  V        
    public( }0 w6 M( C  V- F+ \/ Z
    static' E3 S" z# H0 o/ {/ {: Q' V
    void Perm<T>(T[] list, int begin, int end)
    , F6 `- c$ _1 J        {: n. ^1 r# B4 B( p
                
    if (begin == end)
    : k+ Z, L. _1 R! J            {1 z5 @# r1 s7 E& p3 g2 F0 O
                   
    for (int i =4 W1 z8 R) c; m* l
    0; i <= begin; i++)
    ( _4 |" N, P0 I5 Q                    Console.Write(list);. n& f) f& h6 {! g& H, v
                    Console.WriteLine();
    ; d, h3 S# P" O            }
    : Q% @' c' B7 Y& O" C- j4 @% I) B6 H            
    else/ A  b, D) y6 Q* @
    for (int i = begin; i <= end; i++): o& `8 d7 k5 j4 k
                    {
    ) 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]);% t# H2 L2 f' x7 E
                    }8 x8 V6 f+ X* H* z
            }; H, M5 V# a5 |/ A# f; x3 W, v

    * }; K  Q1 R% h, c        
    static
    1 q2 u4 f9 k6 K+ {$ ~void Main(string[] args)5 Q" Q5 m2 T) y, Q5 C
            {; C; M( L- N* Y8 |" {1 C9 {7 n
                
    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        }  Q3 E2 H. u$ X( S% j4 C1 m$ u
        }
    + X/ X0 c. d& P/ ]* G* i}
    / D, V# C' k1 n, N# ~/ ]$ `

    评分

    参与人数 1威望 +1 学分 +1 收起 理由
    zxygedi + 1 + 1 谢谢分享

    查看全部评分

    "真诚赞赏,手留余香"
    还没有人打赏,支持一下
    楼主热帖
    帖文化:【文明发帖 和谐互动】 社区精神:【创新、交流、互助、共享】

    该用户从未签到

    尚未签到

    发表于 2011-4-13 09:20:19 | 显示全部楼层
    来学习~ 准备用matlab编~
    "真诚赞赏,手留余香"
    还没有人打赏,支持一下
    帖文化:【文明发帖 和谐互动】 社区精神:【创新、交流、互助、共享】
    您需要登录后才可以回帖 登录 | 立即加入

    本版积分规则

    招聘斑竹

    小黑屋|手机版|APP下载(beta)|Archiver|电力研学网 ( 赣ICP备12000811号-1|赣公网安备36040302000210号 )|网站地图

    GMT+8, 2026-3-19 19:25

    Powered by Discuz! X3.5 Licensed

    © 2001-2025 Discuz! Team.

    快速回复 返回顶部 返回列表