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

L

liuyan

Unregistered / Unconfirmed

GUEST, unregistred user!

• 2003-01-25

• #1

举例如下：
字符串：　ab
子集：　a, b, ab

字符串：　abc
子集： a, b, ab, ac, bc, abc, c

要求：
写一个通用的Ｆｕｎｃｔｉｏｎ或Ｐｒｏｃｅｄｕｒｅ
Ｓｕｂ（str：string)
在屏幕上打印出所有子集。
打印的次序不限，只要可以打印出所有子集即可

 

B

bxqxb

Unregistered / Unconfirmed

GUEST, unregistred user!

• 2003-01-25

• #2

此是一个算法问题,关注!帮你提前

 

C

chenxz

Unregistered / Unconfirmed

GUEST, unregistred user!

• 2003-01-25

• #3

应该先把字符分开为单字符，然后自由组合就可以了。

 

L

leejames

Unregistered / Unconfirmed

GUEST, unregistred user!

• 2003-01-25

• #4

:{

 

L

leejames

Unregistered / Unconfirmed

GUEST, unregistred user!

• 2003-01-25

• #5

提法有问题，如果你要的是子串的集合，ac 当然不是 abc的子串
如果要所有字符的组合， ab串还应有 ba的组合。
你给的条件不太够吧，两个例子也不完整。
不知你到底想要怎样的结果。

 

L

liuyan

Unregistered / Unconfirmed

GUEST, unregistred user!

• 2003-01-25

• #6

to leejames:
所谓组合就是指　ab 与 ba 相同，可以再加一个例子：
字符串：abcd
子集：
abcd
bcd
acd
cd
abd
bd
ad
d
abc
bc
ac
c
ab
b
a

 

S

swordkillers

Unregistered / Unconfirmed

GUEST, unregistred user!

• 2003-01-25

• #7

这个应该不会太难吧，我还想问的详细一下，如果字符串为 abbcd，你要的他的子集和
字符串 abcd 的子集一样吗？

 

太

太阳火

Unregistered / Unconfirmed

GUEST, unregistred user!

• 2003-01-25

• #8

Strlist:=TStringlist.create;
Len:=Length(S);
for i:=1 to Len do
for j:=1 to Len-i+1 do
Strlist.add(copy(S,i,j));
这样,Strlist里的内容就是所有子串

 

L

liuyan

Unregistered / Unconfirmed

GUEST, unregistred user!

• 2003-01-26

• #9

To swordkillers:
我的意思里 “abcd”和“abbcd”不一样，我这样的提法是为了简单起见，实际中不一定
是个字符串，可能是一个链表或是一个数组

 

L

liuyan

Unregistered / Unconfirmed

GUEST, unregistred user!

• 2003-01-26

• #10

To 太阳火：
你的方法不能完成我的要求，当字符串为“abc”时，你方法只能打印出：
a
ab
abc
b
bc
c
而实际应该是：
abc
bc
ac
c
ab
b
a
少了一个 "ac"

 

太

太阳火

Unregistered / Unconfirmed

GUEST, unregistred user!

• 2003-01-26

• #11

看看是否用set可解决(不过set不允许有重复得相同元素,那么如何区分abcd, abbcd?)

 

L

lldhz

Unregistered / Unconfirmed

GUEST, unregistred user!

• 2003-01-27

• #12

我用递归试试。
Working................

 

L

liuyan

Unregistered / Unconfirmed

GUEST, unregistred user!

• 2003-01-28

• #13

to lldh:
我也觉得该用递归，怎么样，有什么结果吗？

 

L

liuyan

Unregistered / Unconfirmed

GUEST, unregistred user!

• 2003-01-29

• #14

都3天了，还没人会做吗？

 

L

LiChaoHui

Unregistered / Unconfirmed

GUEST, unregistred user!

• 2003-01-29

• #15

一个简单的循环就可以做了,请看后面的解答！！

 

Y

YoungSun

Unregistered / Unconfirmed

GUEST, unregistred user!

• 2003-01-29

• #16

得到字符串的个数:nMax=string[0];
得到对1..nMax的自然数的所有组合,
如12,13,123...(呵呵,不能直接生成整数哦,最好保存到一个TList中)
查表把数字组合替换成字符串.
求组合的算法吗,i can't tell you because i don't know.

 

G

goddy

Unregistered / Unconfirmed

GUEST, unregistred user!

• 2003-01-29

• #17

好

 

G

guchenyi

Unregistered / Unconfirmed

GUEST, unregistred user!

• 2003-01-29

• #18

好了，搞定：）。肯定满足要求，只要顺序不同不视做不同就可以
procedure GetSet(Source:string);
var
iListCount,itemp:integer

iLen,iNum:integer;
stemp,sleft:string;
begin
Mylist.Clear;
iLen:=length(source);
sLeft:=Source;
iNum:=1;
while (iNum<=iLen) do
begin
stemp:=Copy(sleft,1,1);
sLeft:=copy(sleft,2,iLen-1);
itemp:=MyList.Count-1;
Mylist.Add(stemp);
for iListCount:=0 to itemp do
begin
Mylist.Add(Mylist.strings[iListCount]+stemp);
end;
iNum:=iNum+1;
end;
end;

 

G

guchenyi

Unregistered / Unconfirmed

GUEST, unregistred user!

• 2003-01-29

• #19

如果觉得不美观，再排序一下：），成梯字就好看了。hehe
这是我又改了排序的测试结果
a
b
c
d
ab
ac
bc
ad
bd
cd
abc
abd
acd
bcd
abcd

 

L

LiChaoHui

Unregistered / Unconfirmed

GUEST, unregistred user!

• 2003-01-29

• #20

我的一个“简单”的循环方法如下：
附简单的测试结果：

procedure TForm1.Button1Click(Sender: TObject);
var
ts: TStrings;
ct: Integer;
begin
ts := TStringList.Create;
ct := GetAllSubSet(Edit1.Text, ts);
ts.Insert(0, 'Count: ' + IntToStr(ct));
ts.Insert(0, '');
Clipboard.AsText := ts.Text;
ShowMessage(ts.Text);
ts.Free;
end;

function TForm1.GetAllSubSet(S: String
StrLst: TStrings): Integer;
var
m: array[1..500] of Integer;
ts: String;
ns: String;
i, len: Integer;
begin
Result := 0;
if Length(S) = 0 then Exit;
//此处应检测字符串中的重复字符并进行删除
//可以采用集合进行运算
ts := S;
len := Length(ts);
ns := StringOfChar(#0, 500);
i := 1;
m := 1;
while (i > 1) or (m <= len) do
begin
ns := ts[m];
ns[i+1] := #0;
StrLst.Add(PChar(ns));
if m < len then
begin
i := i + 1;
m := m[i-1]+1;
end
else
begin
i := i - 1;
m := m + 1;
end;
end;
Result := StrLst.Count;
end;

部分测试结果：
abc --->>
Count: 7
a
ab
abc
ac
b
bc

abcd --->>

Count: 15
a
ab
abc
abcd
abd
ac
acd
ad
b
bc
bcd
bd
c
cd

abcde --->>

Count: 31
a
ab
abc
abcd
abcde
abce
abd
abde
abe
ac
acd
acde
ace
ad
ade
ae
b
bc
bcd
bcde
bce
bd
bde
be
c
cd
cde
ce
d
de

lmnopqrstuvw --->>
呵呵，出错了！！