字符串组合问题（100分求答）(100分)

字符串S1='ABCDEFGHIJ',S2='0123456789',现将字符串S1、S2组合成一个字符串S，字符串S必须符合诸如:
S='AB01CDEF2G34567HIJ89'
......................
......................
......................
'0123AB4CDEFG56789HIJ'
......................
......................
......................

即新的字符串S中，应保持ABCDEFGHIJ和0123456789这样总的顺序不便原则才识符合的，而像ABC54FD123EGHIJ67890这样无序的排列是不符合的，请列出所有符合题意的字符串S。

用三个指针一个循环就可以解决这个问题，pchar : p1　指向S1[1],pchar 2 指向S2[1], pchar 指向S[1]

1、如果p^ = p1^ ，inc(p1)然后执行3，否则执行2

2、如果p^ = p2^ ，inc(p2)然后执行3，否则执行,4

3、p如果指向S中的最后一个字符，执行5；否则inc(p)然后执行1

4、S条件不符合，结束

5、S条件符合，结束
========================
代码应该不多，自己写体会一下吧。

楼上正解.........

2楼的是正解吗？没看出来。　

我看到的只是检查已知字符串是否符合要求的算法。楼主要求的是生成所有符合的字符串。

刚想了一个算法，供大家讨论，没写代码，不一定正确，仅供楼主参考。
1、S1与S2组合后生成的S字符串长度，肯定是Len(S1)+Len(S2),这个结论成立吧，即
Len(S)=Len(S1)+Len(S2),
2、组合后产生的S要占用Len(s)个位置,其中的Len(S1)个位置将被S1所占据，同理余下的len(S2)将被S2占据，这个理论也对吧？
对于楼主的实际情况，就是S长度20，组合后生成的S1与S2分别占用10个位置。
如 AB01CDEF2G34567HIJ89
3、由于S1与S2在S中的顺序是固定的，所以对于S1与S2来说，分别各只有1种序列，也即只有一种状态，对于S来说，只有两种状态。这个怎么理解呢？理论上我们只需要把S中的空位置分成两组，只要符合第一组位置的长度等于Len(s1),而第二组的位置长度等于Lne(s2)，那么这样的位置组合，肯定能组成符合题意的字符串S，假设我们用1与0分别代码第一组与第二组的状态，那么像以下的组合状态，都能够组成符合题意的结果，即序列中1的个数等于Len(s1), 0的个数等于Len(s2)
11111111110000000000
10101010101010101010
11000111001011001100
............

假设我们在上述状态序列中的1位置依次填入 0123456789, 0位置依次填入ABCDEFGHIJ,上述串转换后的得到的结果就是
0123456789ABCDEFGHIJ
0A1B2C3D4E5F6G7H8I9J
01ABC234DE5F67GH89IJ
....
均符合题意

4、得到了这个想法后，剩下的工作就简单了？对了，0、1两个状态，自然的就想到了二进制，只要把从2^Len(s1) 到2^Len(s1+s2)-2^len(s1)中的所有数中符合二进制中1的个数等于 Len(s1)的数找出来，然后分别替换入S1与S2，就得到结果

即将 00000000001111111111 到 11111111110000000000 (即 十进制1023 到 1047552 ) 中所有符合　10个1与10个0的数找出来。

当然你也可以将循环从0开始到2^20为止，但理论上在2^10以内，与2^20-2^10之外，不可能组成10个0与10个1的数，所以可以减少循环，加快速度。

To:[levi]
可以说说你的算法吗？谢谢！[]

刚才没写完就按了回复，呵呵，不知道楼主能看懂不。

呵呵，看错误，levi方法我没细看，但就算是可行代码写起来也不好写，其实还用更简单的方法。

冒泡排序大家应该清楚，这问题也可以来冒冒泡

函数工作内容：把某个字符移动目标位置

0(1，2)代表 S1，a(b,A)代表S2。注：1代表目标位置,2代表递归调用的目标位置，A当前函数移动的字符，b代表递归调用时要移动的字符。
初始状态 aaaaaaabA000000001 (A的初始位置是10，最终目标是20)
移动一位 aaaaaaab2A00000001 (开始冒泡，第一个结果出来了，递归调的目标位置也出来了)
A完成后状态 aaaaaaab000000002A (A到达最终目标是20)

但是这样并不能得到全部结果，想只得到结果其实很简单，递归调用这个函数就得到结果了。
在移动后进行递归调用
新初始状态 aaaaaabA1a000000000 (移动的字符转变了，A的初始位置是1，最终目标是10)
(因为移动方法与上面相同，这里就不再描述了。。。)

============================================================
代码：
procedure TForm1.FinishYourTargetBoy(World:string; me:integer;myTarget:integer);
var
tempChar:char;
myNewSituation:integer; //新的位置
myOldSituation:integer; //原位置

child:integer;
childTarget:integer;

newWorld:string;

isHaveChild:bool;
isImFinish:bool;
begin
newWorld :=World;

if me <> myTarget then
begin
isImFinish := false;
myNewSituation := me;
end
else isImFinish:= true;

if me > 1 then
begin
isHaveChild :=true;
child := me-1;
end
else
begin
isHaveChild :=false;

end;

while not(isImFinish) do
begin

myOldSituation := myNewSituation;
inc(myNewSituation);

//创建新世界
tempChar := newWorld[myOldSituation] ;
newWorld[myOldSituation] := newWorld[myNewSituation];
newWorld[myNewSituation] := tempChar;

if myNewSituation = myTarget then
begin
isImFinish :=true;
end;

if isHaveChild then
begin
//向孩子描述新的世界
childTarget:= myOldSituation;
FinishYourTargetBoy(newWorld,child ,childTarget);
end;


//newWrold 就是你要的结果，想怎么做在这里写代码。
Memo1.Lines.Add(newWorld) ;
////////////////////////////////////////////////
end;
end;

procedure TForm1.Button1Click(Sender: TObject);
var
world:string; //世界
child:integer; //孩子
childTarget:integer;// 孩子目标
begin
memo1.Lines.BeginUpdate ;
//初始化世界
world := 'ABCDEFGHIJ0123456789' ;
child := 10;//设置要移动的字符位置
childTarget := 20; //设置目标
FinishYourTargetBoy ( world ,child ,childTarget);
memo1.Lines.EndUpdate;
end;

var
s1,s2: string;
lens1,lens2,i,j: Integer;
begin
mmo1.Clear;
s1 := 'ABC'; -->替换
s2 := '123'; -->替换
lens1 := Length(s1);
lens2 := Length(s2);
for i := 1 to lens1 do
for j := 1 to lens2 do
begin
mmo1.Lines.add(copy(s1,1,i) + copy(s2,1,j) + copy(s1,i + 1,lens1) + copy(s2,j+1,lens2));
if i = lens1 then break;
end;
分析结果楼主也该看出算法的思想,这里只获得了一半的组合，把s2,s1交换可得另外一半
A1BC23
A12BC3
A123BC
AB1C23
AB12C3
AB123C
ABC123

楼上，我怎么没看到A1B2C3呢？你说的另外一半应该没有1A2B3C吧，这两个应该符合楼主的题目意思

To: qqjm (不是针对你哦，只是讨论问题)

老实说，楼主的问题，理论上看是可以用冒泡法，但采用冒泡法的话，太复杂。依照你上面的算法，要么得到的结果只是整个结果集中一部分（算法过于保守），要么得到的有些是非目标结果（过于开放），原因就在于楼主要求的结果是S1可以同时移动1-10个到S2中，而且多于1个时，可以连续或者分段的分别放入S2中。

To hanpengshan_00

zhengrong117说的对，你的算法，实际上丢了3个结果（总共丢了6个）
实际上从 000111 到100000 (后面部分不列了，是可以通过取反得到)
有10个结果，分别是
000111 ABC123
001011 AB1C23
001101 AB12C3
001110 AB123C
010011 A1BC23
010101 A1B2C3 (这个你没有)
010110 A1B23C (这个你没有)
011001 A12BC3
011010 A12B3C (这个你没有)
011100 A123BC

To : levi
　　　请赐教代码。（希望不要太长，我人太笨，代码长了看不明白）

qqjm 别生气哦，我一不跟你争分，也不否认大家劳动。理论上说，无论何种算法都可以解决相同的问题，只是难易程序不同而已。我讲的算法肯定不是最优，只是凑巧能够完成楼主的要求而已。代码应该不难,既然有要求，我就试试看吧。（便宜楼主了，)

在Form 上放一个memo, 名字为 Memo1,将下面的代码贴到一个按钮的Click事件中
(在头单元引用 Math)

//十进制转换成二进制字符串
function IntToBin(Value: cardinal; Digit:Integer): string;
var
i: Integer;
begin
SetLength(result, 32);
for i := 1 to 32 do
begin
if ((Value shl (i - 1)) shr 31) = 0 then
result := '0'
else
result := '1';
end;
//由于cardinal 能表达最大2^32的数，但我们只需要后20位，所以要处理一下
Result := Trim(Copy(Result, Length(Result) - digit + 1 , digit));
end;

//判断字符串是否符合要求
Function StrAvail(Value:String; Len:Integer):Boolean;
var Count, i:Integer;

begin
Result := False;
Count := 0;
if Trim(Value) = '' then
Exit;
for i := 1 to Length(Value) do
if Value = '1' then
Inc(Count);
Result := Count = len;
end;

//将S1/S2填充到目标位置中
Function FillStr(S, S1, S2:String):String;
var j, i, x, y: Integer;
begin
i := 1; //S位置
x := 1; //s1位置
y := 1; //s2位置
SetLength(Result, Length(S));
for j := 1 to Length(S) do
if s[j] = '1' then
begin
Result[j] := s1[x];
Inc(x)
end
else
begin
Result[j] := s2[y];
Inc
end;
end;

Const S1='123';
S2='ABC';
var i:Integer;
LpL, lpH:Integer;
tpStr:String;
begin
Memo1.Lines.Clear;
LpL := Round(Power(2,Length(s1))) - 1;
LpH := Round(Power(2,Length(s1+s2)))- lpL + 1;
for i :=LpL to LpH do
begin
tpstr := IntToBin(i, Length(s1) + Length(s2));
if Length(tpStr) = Length(s1) + Length(s2) then
if StrAvail(tpStr, length(S1)) then
begin
tpStr := FillStr(tpStr, S1, S2);
memo1.Lines.Add(tpStr);
end;
end;
end;

上述代码在 D7 中测试通过，得到结果如下
ABC123
AB1C23
AB12C3
AB123C
A1BC23
A1B2C3
A1B23C
A12BC3
A12B3C
A123BC
1ABC23
1AB2C3
1AB23C
1A2BC3
1A2B3C
1A23BC
12ABC3
12AB3C
12A3BC
123ABC
共20个
把S1 与 S2　的内容改一下，就可以得到不同的组合。

ABCDEFGHIJ0123456789
ABCDEFGHI0J123456789
ABCDEFGHI01J23456789
ABCDEFGHI012J3456789
ABCDEFGHI0123J456789
ABCDEFGHI01234J56789
ABCDEFGHI012345J6789
ABCDEFGHI0123456J789
ABCDEFGHI01234567J89
ABCDEFGHI012345678J9
ABCDEFGHI0123456789J
.....
012345678ABCDEFGHI9J
012345678ABCDEFGH9IJ
012345678ABCDEFG9HIJ
012345678ABCDEF9GHIJ
012345678ABCDE9FGHIJ
012345678ABCD9EFGHIJ
012345678ABC9DEFGHIJ
012345678AB9CDEFGHIJ
012345678A9BCDEFGHIJ
0123456789ABCDEFGHIJ
共计 184756 个结果

谢谢[levi], [qqjm]。。。诸位富翁
验证通过的话，就请2位接分吧[]

多测试几次就知道是否正确了吧

多人接受答案了。