求一个数组元素的排列函数(排列组合问题)(100分)

  • 主题发起人 主题发起人 iknowabc
  • 开始时间 开始时间
I

iknowabc

Unregistered / Unconfirmed
GUEST, unregistred user!
求一个数组元素的排列函数(排列组合问题)
已知全局数组DataBuf
DataBuf:array[1..Bufsize] of char;
首先题目保证DataBuf中的各个char元素不重复
要求写一个函数
function RangeList(m,n):string;
要求列出所有P(m,n)的结果,P这里就是排列。m=n时，就是全排列。
比如:DataBuf:={'1','2','3','4','5'} ,P(2,5)就有20种
输出string应该以类似情况:'12','13','14','15','21','23','24','25','31','32'...
感觉应该不是很复杂的，但是一下子又不知道怎么写，请教各位朋友。
 
function RangeList(const m: Integer): TStringList;
type
TNode = record
d: Integer;
Used: array [1..BufSize] of Boolean;
end;
var
Stack: array [1..BufSize] of TNode;
Top: Integer;
i: Integer;
s: string;
begin
if m>BufSize then
Exit;
Result:=TStringList.Create;
Top:=1;
Stack[1].d:=0;
FillChar(Stack, SizeOf(Stack), 0);
while Top>0do
begin
while Stack[Top].d<BufSizedo
begin
Inc(Stack[Top].d);
if not Stack[Top].Used[Stack[Top].d] then
if Top=m then
begin
s:='';
for i:=1 to Topdo
s:=s+DataBuf[Stack.d];
Result.Append(s)
end
else
begin
Inc(Top);
Stack[Top].d:=0;
Stack[Top].Used:=Stack[Top-1].Used;
Stack[Top].Used[Stack[Top-1].d]:=True
end
end;
Dec(Top)
end
end;
 
to LeeChange:
首先，谢谢你的回答。但是我问的是一般的排列组合问题，而你回答的全排列。
呵呵，题目要求输入两个参数，p(m,n)，比如求P(2,5)之类，而你的程序只能求P(5,5)这类全排列。
函数应该类似
function RangeList(m,n:integer):string;
还是要非常感谢你！
 
呵呵，我的理解没有错.
我的m就是你的m,你的n就是BufSize吧.
其实算法跟你上次那个求所有路径的一模一样.
抽象的东西就是好,随便怎么换个马甲,就面目全非了,呵呵，看起来毫不相干的东西竟能用一个算法.
 
你用Memo1.Lines.AddStrings(RangeList(1));
试一下就知道了.
 
to LeeChange:
呵呵，原来如此，是我没有看懂。
对了，还是想麻烦一下你，给我讲讲这个程序。那个Stack的应用是怎么回事，呵呵，咋个就
遍历出所有的结果了呢？
讲讲你的思路，行吗？
再次感谢！
 
呵呵，我喜欢用一个栈来模拟递归过程,仅仅是个人习惯,好处是不需要手工去设堆栈的大小.
换成递归你就好理解了.
function RangeList(const m: Integer): TStringList;
type
TUsed = array [1..BufSize] of Boolean;
TArr = array [1..BufSize] of Integer;
var
Used: TUsed;
a: TArr;
procedure TryIt(Step: Integer;
a: TArr;
Used: TUsed);
var
d, i: Integer;
s: string;
begin
for d:=1 to BufSizedo
if not Used[d] then
begin
if Step=m then
begin
s:='';
for i:=1 to Step-1do
s:=s+DataBuf[a];
s:=s+DataBuf[d];
Result.Append(s)
end
else
begin
a[Step]:=d;
Used[d]:=True;
TryIt(Step+1, a, Used);
Used[d]:=False
end
end
end;
begin
Result:=TStringList.Create;
FillChar(Used, SizeOf(Used), 0);
FillChar(a, SizeOf(a), 0);
TryIt(1, a, Used)
end;
 
to LeeChange:
谢谢你回答我的问题。(呵呵，你帮了我几次了，感谢的话就不多说了)
关于排列的那个程序，我将你的程序改了一下，但是出了些问题
比如求P(2,5), 12,13,14,15之后接着就是23，就是没有21，
测试函数:
DataBuf:array[0..MAXSize-1] of char;
for i:=0 to 9do
DataBuf:=Char(i+48);
Memo1.Lines.AddStrings(RangeList(2,5));
原函数:
function RangeList(const m,n: Integer): TStringList;
type
TNode = record
d: Integer;
Used: array of Boolean;
end;
var
Stack: array of TNode;
Top: Integer;
i,j: Integer;
s: string;
begin
if m>n then
Exit;
SetLength(stack,n);
for i:=1 to ndo
SetLength(stack[i-1].Used,n);
//setlength(a,n)；a下标应该从0..n-1
ZeroMemory(Stack,sizeof(Stack));
Result:=TStringList.Create;
Top:=0;
Stack[0].d:=-1;
while Top>=0do
begin
while Stack[Top].d<n-1do

begin
Inc(Stack[Top].d);
if not Stack[Top].Used[Stack[Top].d] then
if Top=m-1 then
begin
s:='';
for i:=0 to Topdo
s:=s+DataBuf[Stack.d];
Result.Append(s)
end
else
begin
Inc(Top);
Stack[Top].d:=-1;
Stack[Top].Used:=Stack[Top-1].Used;
Stack[Top].Used[Stack[Top-1].d]:=True;//#1
end
end;
Dec(Top);
end
end;
我跟踪了一下，就是在#1处出了问题，执行了#1这句之后，
Stack[Top-1].Used[Stack[Top-1].d]也变成了true???!!!
呵呵，还是要请教一下LeeChange!
 
function RangeList(const m,n: Integer): TStringList;
type
TNode = record
d: Integer;
Used: array of Boolean;
end;
var
Stack: array of TNode;
Top: Integer;
i,j: Integer;
s: string;
begin
if m>n then
Exit;
SetLength(stack,m);
for i:=1 to mdo
SetLength(stack[i-1].Used,n);
//setlength(a,n)；a下标应该从0..n-1
ZeroMemory(Stack,sizeof(Stack));
Result:=TStringList.Create;
Top:=0;
Stack[0].d:=-1;
while Top>=0do
begin
while Stack[Top].d<n-1do

begin
Inc(Stack[Top].d);
if not Stack[Top].Used[Stack[Top].d] then
if Top=m-1 then
begin
s:='';
for i:=0 to Topdo
s:=s+DataBuf[Stack.d];
Result.Append(s)
end
else
begin
Inc(Top);
Stack[Top].d:=-1;
for i:=0 to n-1do
Stack[Top].Used:=Stack[Top-1].Used;
Stack[Top].Used[Stack[Top-1].d]:=True;//#1
end
end;
Dec(Top);
end
end;
 
to LeeChange:
谢谢你的指教，程序终于正确了。但是还是要问一下
for i:=0 to n-1do
Stack[Top].Used:=Stack[Top-1].Used;
与原来的
Stack[Top].Used:=Stack[Top-1].Used;
有什么不同?数组可以逐个赋值，应该也可以直接赋值呀!??
 
动态数组名其实是地址.
Stack[Top].Used:=Stack[Top-1].Used;
以后,对Stack[top].Used和Stack[Top-1].Used的任何一个的改动都会影响另一个.
 
to LeeChange:
静态数组 Used: arrray[0..bufsize] of char就可以直接以数组名赋值的
Used:array of integer就象一个指针吗，那么Used[1]不是就是Used[0]+sizeof(integer)
呵呵，这与C中的数组与指针的关系不是很象？
还要请教LeeChange!
 
procedure TForm1.Button1Click(Sender: TObject);
var
a, b: array of Integer;
p: PInteger;
i: Integer;
begin
SetLength(a, 10);
SetLength(b, 10);
for i:=0 to 9do
a:=i;
b:=a;
{这个循环证明a与b指向同一块内存}
for i:=0 to 9do
if a<>b then
ShowMessage('Unmatch');
Integer(p):=Integer(a);
{这个循环证明a本质上就是个指针}
for i:=0 to 9do
begin
ShowMessage(IntToStr(p^));
Inc(p)
end
end;
 
谢谢leechange详尽的回答。
我仔细地看了你以上几个程序，对“栈来模拟递归过程”很感兴趣，这里顺便问问你，
栈来模拟递归过程需要经过哪些步骤，需要注意些什么？
呵呵，能再给我介绍一下这种思想吗？
 
1.把递归函数中的所有要递归的参数一起组成一个记录TNode.
2.按递归最大深度声明栈stack: array [1..MaxDeep] of TNode;
3.将初始状态放到Stack[1]里
4.套用以下伪码
while Top>0do
begin
while Stack[Top].d<Maxddo
begin
Inc(Stack[Top].d);
按d的方向生成新状态Node;
if Node=目标 then
//处理输出
else
begin
Inc(Top);
Stack[Top]:=Node;
Stack[Top].d:=0
end
end
Dec(Top)
end
 
弓虽
谢谢！收藏！：）
 
非常感谢LeeChange的帮助。
 
您必须登录或注册才可回复。

Similar threads

S
[原]详解Variant 的相关函数
回复
0
查看
1K
SUNSTONE的Delphi笔记
S
S
[原]详解Variant 的相关函数
回复
0
查看
900
SUNSTONE的Delphi笔记
S
J
DELPHI中不同类型的动态数组变量共享内存
回复
0
查看
637
Jack
J
S
[转]ClientDataSet加上TDataSetProvider的数据保存问题
回复
0
查看
3K
SUNSTONE的Delphi笔记
S
S
[转]ClientDataSet加上TDataSetProvider的数据保存问题
回复
0
查看
2K
SUNSTONE的Delphi笔记
S
后退
顶部