组合算法
现在我有26个元素a...z
我想自由生成相关的组合
从一位起
a
a+b
a+b+c
a+b+c+d
......
生成所有组合对顺序没有要求,即a+b 和 b+a可以当同一条,不用重复出现
[解决办法]
有没有算过有多少个组合?生成之后需要存储吗?用什么存储?需要访问吗?怎么访问?
[解决办法]
[解决办法]
- 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;