读书人

结合算法

发布时间: 2012-09-14 23:00:49 作者: rapoo

组合算法
现在我有26个元素a...z
我想自由生成相关的组合
从一位起
a
a+b
a+b+c
a+b+c+d
......
生成所有组合对顺序没有要求,即a+b 和 b+a可以当同一条,不用重复出现

[解决办法]
有没有算过有多少个组合?生成之后需要存储吗?用什么存储?需要访问吗?怎么访问?
[解决办法]

探讨

26,又不规定组合的个数,那不知道有多少亿亿亿个组合了...

[解决办法]
Delphi(Pascal) code
program Project1;{$APPTYPE CONSOLE}var  a:array [0..26] of char;  s:set of char;  j:integer;procedure print(n:integer);//打印过程var  i:integer;begin  for i:=1 to n-1 do write(a[i],'+');  writeln(a[n]);end;procedure Search(num:Integer;t:integer);//回溯过程var  ch:char;begin  if t>num then  begin    print(num);    exit;  end;  for ch:=a[t-1] to 'z' do    if ch in s then    begin      s:=s-[ch];      a[t]:=ch;      search(num,t+1);      s:=s+[ch];    end;end;begin  assign(output,'output.out');rewrite(output);  //初始化数据  a[0]:='a';  s:=['a'..'z'];  for j:=1 to 26 do search(j,1);//主过程,j越大会越久,因为是递归调用  close(output);end.
[解决办法]
这类问题,直接用位不就搞定了?才26位,不足一个正整数的大小,不过这方法结果不是
A,AB,ABC这样的顺序,而是A,B,AB,AC

Delphi(Pascal) code
var  aLineBuffer : Array [0..26-1 + 2] of AnsiChar;  hFile : THandle;  sBuf : AnsiString;  iBufSize : integer;  iBufUseSize : integer;//返回位数,字符串保存于aLineBuffer中,返回位数中包含回车换行符Function  IndexToBuffer(Index : DWORD) : integer;asm      XOR     ECX , ECX      LEA     EDX , aLineBuffer@@Loop:      BTR     EAX , ECX      JNC     @@Next      MOV     [EDX] , CL      ADD     [EDX] , 'A'      INC     EDX@@Next:      TEST    EAX , EAX      JZ      @@Break      INC     ECX      CMP     ECX , 26      JNZ     @@Loop@@Break:      MOV     [EDX].WORD , $0A0D      LEA     EAX , aLineBuffer      SUB     EDX , EAX      LEA     EAX , [EDX+2]end;//初始化文件Function InitSaveFile(Const FileName : AnsiString) : Boolean;begin  hFile := CreateFile(PAnsiChar(FileName),GENERIC_READ or GENERIC_WRITE,                      FILE_SHARE_READ or FILE_SHARE_WRITE,                      nil, CREATE_ALWAYS,                      FILE_ATTRIBUTE_NORMAL , 0);  Result := hFile<>INVALID_HANDLE_VALUE;end;//写入缓冲区到硬盘procedure SaveToFile;var  D : DWORD;begin  WriteFile(hFile , Pointer(sBuf)^ ,  iBufUseSize , D , NIL);  iBufUseSize := 0;end;//把当前行增加到缓冲区中procedure AppendToBuf(LineSize : integer);begin  if LineSize+iBufUseSize>iBufSize then SaveToFile;  Move(aLineBuffer , Ptr(Integer(sBuf) + iBufUseSize)^ , LineSize);  iBufUseSize := iBufUseSize + LineSize;end;procedure TForm1.Button1Click(Sender: TObject);var  Index , n , nCount , nTime : DWORD;begin  if not InitSaveFile('E:\dd.dat') then exit;  iBufSize := 20 * 1024 * 1024;     //缓冲区 20M  iBufUseSize := 0;  SetLength(sBuf , iBufSize);  nTime := GetTickCount();  nCount := 0;  Index := 1;  while True do begin    n := IndexToBuffer(Index);    Inc(nCount , n);    AppendToBuf(n);    if n=28 then Break;    Inc(Index);  end;  nTime := GetTickCount() - nTime;  Caption := '总字节数:' + IntToStr(nCount) + '  耗时:' + IntToStr(nTime) + '豪秒';  if iBufUseSize<>0 then SaveToFile;  SetLength(sBuf , 0);  CloseHandle(hFile);end; 

读书人网 >.NET

热点推荐