求解组合序列-白红宇

求解组合序列

阅读量：4494 次

发布时间：2019-06-08

本文共 1717 字，大约阅读时间需要 5 分钟。

今天用到了求解组合序列的算法，并用C++和OCaml做了实现。

问题描述：有数组（链表等）a，长度len，从里面取出n个元素，给出所有的取出序列。

这是排列组合问题，共有C(len,n)个序列，高中学过的。实现的流程其实比较简单，如下：

设当前位置s，则可以先取a[s]，然后从余下的元素中取出n-1个元素，一起组成一个序列；

或不取a[s]，从余下的元素中取出n个元素作为一个序列

迭代该过程

C++代码

#include
     
      #include
      
       using namespace std;vector
       
        
          > pick(int l[],int s,int e,int n){	vector
         
          
            > v; if(e-s+1>=n&&n>0) { vector
           
            
              > res1 = pick(l,s+1,e,n-1); int size=res1.size(); if(size>0) { for(int i=0;i

tmp; tmp.push_back(l[s]); res1.push_back(tmp); } vector

> res2 = pick(l,s+1,e,n); size=res2.size(); for(int i=0;i

> res = pick(coe,0,4,3); int size=res.size(); for (int i=0;i

v=res[i]; int len=v.size(); for (int j=0;j

运行结果

OCaml代码

1 let rec pick a s e len =  2     let v = ref [] in  3     if e-s+1>=len&&len>0 then  4     begin  5         let len0 = len in  6         let res1 = pick a (s+1) e (len-1) in  7         let len = List.length !res1 in  8         let ele = List.nth a s in  9         if len>0 then 10         begin 11             List.iter(fun r-> 12                 r := ele::!r; 13             )!res1; 14         end else 15         begin 16             res1 := [ref [ele]]; 17         end; 18         19         let res2 = pick a (s+1) e len0 in 20         List.iter(fun r-> 21             res1 := r::!res1; 22         )!res2; 23             24         v := !res1; 25     end; 26         27     v 28 in 29     30 let a = [1;2;3;4;5] in 31 let res = pick a 0 4 3 in 32 33 List.iter(fun r-> 34     List.iter(fun r1-> 35         Printf.printf "%d," r1; 36     )!r; 37     Printf.printf "\n"; 38 )!res;

运行结果

转载于:https://www.cnblogs.com/njucslzh/archive/2012/03/26/2418763.html