一个简单的算法问题，求一个已知字符串的所有子集 (100分)

G

guchenyi

Unregistered / Unconfirmed

GUEST, unregistred user!

• 2003-01-29

• #21

呵呵，我的算法土了点，不过绝对是按照原理来的。。。不会错哦。。。[]
印度人的做法阿，楼上典型中国人做法哦：）

 

L

LiChaoHui

Unregistered / Unconfirmed

GUEST, unregistred user!

• 2003-01-29

• #22

数学上的验证
对于abcde的个数：C5^1 + C5^2 +C5^3 + C5^4 + C5^5 = 5 + 10 + 10 + 5 + 1 = 31
对于lmnopqrstuvw的个数
C12^1 = 12
C12^2 = 66
C12^3 = 220
C12^4 = 12!/8!/4! = 495
C12^5 = 12!/7!/5! = 792
C12^6 = 12!/6!/6! = 924
C12^7 = 12!/5!/7! = C12^5 = 792
C12^8 = 12!/4!/8! = C12^4 = 495
C12^9 = 12!/3!/9! = ... = 220
C12^10 = 12!/2!/10! = ... 66
C12^11 = 12!/1!/11! = 12
C12^12 = 12!/1/12! = 1

总和为：4095

 

G

guchenyi

Unregistered / Unconfirmed

GUEST, unregistred user!

• 2003-01-29

• #23

阿，那我没分了，我那个肯定对的哦。呵呵。。。
我觉得验证的关键是从数学上定义集合的概念来验证算法比较对哦。不是一串数字哦：）

 

L

LiChaoHui

Unregistered / Unconfirmed

GUEST, unregistred user!

• 2003-01-29

• #24

to guchenyi
仔细地看了一下，你的方法思路简单，利用集合的方法
比我的方法好多了，
好，我弃权，不要分了

 

H

hi_zhb

Unregistered / Unconfirmed

GUEST, unregistred user!

• 2003-01-29

• #25

看了题目，写了算法，才发现与guchenyi的一样。这样写比较简练。不过如果字符串一长，
可能会溢出。

 

火

火龙真人

Unregistered / Unconfirmed

GUEST, unregistred user!

• 2003-01-29

• #26

这不排列组合么，穷举。
算法懒得写，应该简单

 

L

LiChaoHui

Unregistered / Unconfirmed

GUEST, unregistred user!

• 2003-01-29

• #27

改来该去，怎么后来加的东西都没有了，也懒得加了

 

Y

Yves

Unregistered / Unconfirmed

GUEST, unregistred user!

• 2003-01-29

• #28

这个问题 我没看明白
是不是求 一个集合的幂集？
是不是 要把所要处理的对象 作为一个集合对待（元素无序，元素互异）
如果是 那么答案 楼上诸位已经 给出了
如不是 那么还需考虑

 

L

ligia

Unregistered / Unconfirmed

GUEST, unregistred user!

• 2003-01-29

• #29

FUNCTION FkCombinAllListGet(vStr:STRING):TStringList;
//[SUB]---------------------------------------
FUNCTION FkCombinListGet(vStr:STRING;vNum:INT64):TStringList;
VAR aSign:array of INTEGER;
sOut:STRING;
iNumber:INT64;i,j,iLength:INTEGER;
BEGIN
Result:=TStringList.Create;
iLength:=Length(vStr);
IF vNum=1 THEN BEGIN FOR i:=1 TO Length(vStr) DO Result.Add(vStr)
Exit
END;
SetLength(aSign,vNum);
FOR i:=0 TO vNum-1 DO aSign:=i;
aSign[vNum-1]:=aSign[vNum-2]
iNumber:=0;
WHILE TRUE DO
BEGIN
INC(aSign[vNum-1])
sOut:='';
FOR i:=0 TO vNum-1 DO sOut:=sOut+vStr[aSign+1];
INC(iNumber)
Result.add(sOut);
IF aSign[0]=(iLength-vNum) THEN break;
FOR i:=1 TO vNum-1 DO
BEGIN
IF aSign=iLength-(vNum-i) then
BEGIN
aSign[i-1] := aSign[i-1]+1;
FOR j:=i TO vNum-2 DO aSign[j] := aSign[j-1]+1;
aSign[vNum-1]:=aSign[vNum-2]
break;
END;
END;
END;
END;
//[END SUB]
VAR k,iLen:INTEGER;
BEGIN
iLen:=Length(vStr);
Result:=TStringList.Create;
FOR k:=1 TO iLen DO Result.AddStrings(FkCombinListGet(vStr,k));
END;

不要告诉我不行

 

L

liuyan

Unregistered / Unconfirmed

GUEST, unregistred user!

• 2003-01-31

• #30

Thanks for all of you guys, sorry I can not input Chinese right now, I have no
time to check all the code now, after I check the code I will give you the FEN.
BTW, I have write some code to implement this function, I paste it here, may be
we can dicuss it.

var
Form1: TForm1;
strtmp: string;
implementation
{$R *.dfm}
function TForm1.Sub(str: String
N: integer): string;
var
strl: string;
i: integer;
begin
strl:='';
if N = 0 then
begin
for i:= 1 to length(strtmp) do
if strtmp<>'&amp;' then
strl:= strl+strtmp;
Memo1.Lines.Add(strl);
end
else begin
strtmp[N] := str[N];
Sub(str, N-1);
strtmp[N] := '&amp;';
Sub(str, N-1);
end;
end;
procedure TForm1.btnPrintClick(Sender: TObject);
var
strText: string;
begin
strtmp := StringOfChar(#0, 50);
strText:= edtString.Text;
Sub(strText, length(strText));
end;

 

L

lxv

Unregistered / Unconfirmed

GUEST, unregistred user!

• 2003-01-30

• #31

例如，abcd，用四位二进制数表示可以得到
0000
0001
0010
0011
……
1111
，
用这样的方法，第一位对应a，第二位对应b，第三位对应c，第四位对应d，然后1就保留，0就不要算了，这样就能得到所有的了.

 

L

liuyan

Unregistered / Unconfirmed

GUEST, unregistred user!

• 2003-01-31

• #32

多人接受答案了。