吵吵   2012-11-13  阅读:3,326

这是一个常见的问题,也是程序员面试时候容易考的一个问题,对于一个有限的集合,如{1,2,3},输出它所有的子集。明显的它的子集就是{1},{2},{3},{1,2},{1,3},{2,3},{1,2,3}如果还包含它的空集的话一共就是2的n次方,这里2的3次方就是8个。

一开始我碰到的问题是,在LIS中,我们对于一个标本会有很多的检测项目,这样子负责某个项目的人就不得不一个个标本去翻查看有没有它的项目,一方面这个工作浪费时间,二则需要集中注意力,否则非常容易抄错。并且对于常见的ELISA项目来说,还有多个组合,4个项目就有16-1种组合,将这些标本的号按照组合来输出就显得尤为重要。

原本我的想法是4个项目的组合应该是一个高中数学里面的组合问题,但是后来网上找了半天也没找到,于是计算了一下到底有多少个组合,才发现这其实是一个求子集的问题。

递归法求子集的思路
网上有很多求子集的方法,如递归法、二进制法,但是如果你明白了下面这张图就会明白其本质是一样的,因为对于集合中的每一个元素来说,只有纳入和不纳入两种状态!这和二进制原本就很像,无非每个元素就是0和1两种状态罢了。

其实你没有看错,上面这个二叉树图也反映了这样的结构,对a来说只有b和c两种状态,对于下一个元素来说也只有两种状态,即我们的元素纳入还是不纳入。好了我们来看我用delphi写的一个求子集的类:

unit Subset;

interface

uses
  SysUtils, Classes;
type//子集的结构体,num是这个子集中元素个数,mysubset是元素的数组
 subrecord = record
   num  : integer;
   mysubset : array[0..10] of integer;
end;
type
  TSubset= class
  subsetcount:integer;
  subset:array of subrecord;
  procedure initial(num:integer);
  procedure calculate();
  procedure trial(str:array of integer;start:integer;n:integer) ;
  procedure popRange();

end;

var
  inputnum,add:integer;
  a:array of integer;//用来记录元素纳入与否状态,赋值为0或者1
  b:array of integer;


implementation
procedure tsubset.initial(num:integer);
var
i:integer;
sum:integer;
begin
  inputnum:=num;
  sum:=1;
  for i := 0 to num-1 do
  begin
    sum:=sum*2
  end;
  subsetcount:=sum;//子集的个数
  setlength(subset,subsetcount);
  setlength(a,num);
  setlength(b,num);
  for i := 0 to num-1 do
  begin
      a[i]:=0;
      b[i]:=i+1;
  end;
end;
procedure TSubset.trial(str:array of integer;start:integer;n:integer) ;
var
i:integer;
begin
  if start < n then
  begin
    trial(str,start+1,n) ;//集合的元素没有到底,start即代表的第几个元素,加一后继续递归。
    a[start]:=1-a[start];//如果这个元素是纳入的即为0,我们则将其变为不纳入的,即为1,下一句继续加一递归。
    trial(str,start+1,n) ;
  end
  else
  begin
    subset[add].num:=0;
    for i := 0 to n-1 do//所有的元素都遍历过了我们就根据a数组中代表的纳入与否的状态进行输出
    begin
      if a[i]=0 then
      begin
        subset[add].mysubset[subset[add].num]:=b[i];
        subset[add].num:=subset[add].num+1;
      end;


    end;
    add:=add+1;
  end;
end;
procedure TSubset.calculate();
begin
  add:=0;
  trial(b,0, inputnum);
  popRange;
end;


procedure Tsubset.popRange();//对子集进行冒泡排序
var
  i,j,B:integer;
  tempsub:subrecord;
begin
  for i := 0 to subsetcount-1 do
  begin
    for j := 0 TO subsetcount-1-I do
    begin
      if subset[J].num<subset[j+1].num then
      begin
        tempsub:=subset[J];
        subset[J]:=subset[J+1];
        subset[j+1]:=tempsub;




      end;
    end;

  end;
end;
end.



冒泡排序的方法我在上一篇博文中有说到,其实就是遍历一遍元素,将元素一个个往后拉就是了,可以参考:

鸡尾酒排序算法Java实现

吵吵微信朋友圈,请付款实名加入:

吵吵 吵吵

2条回应:“输出一个集合的子集算法和冒泡排序算法”

  1. 支持一下。

  2. 都是代码哦,看不懂哦!

发表评论

电子邮件地址不会被公开。 必填项已用*标注