高分求助快速组合算法

Question

设有以下数据组
 1  2 12 14 20 
 1  3  8 10 15 
 1 11 14 15 20 
 4  5 10 13 21 
 6 10 11 12 19 
 3  5  7 13 15 
12 17 18 20 21 
10 12 14 19 22 
 5 11 14 20 22 
 6 14 17 19 20 
 5  8 14 17 22 
 6  7  8 12 17 
 3  4  9 14 22 
11 12 15 16 21 
 4  6  9 16 18 
 4  7 11 17 20 
 6  8  9 13 18 
 2  3  4 07 20 
 2  8  9 17 20 
 1  8 12 13 17 
 2  9 14 20 22 
 5  6 15 21 22 
从每一组中取出一个数按组数顺序组合成一新数组，新数组中不能有重复的数，求出全部的组合数组，将其打印出来，并得出每一新数组的长度。
如：1 3 11 4 6 5 12 10 14 17 8 7 9 15 16 20 13 2 这一组新数组是从前18组数据中每组提出一个数组合成的，第19组数据2 8 9 17 20中的每一个数已经出现在这组新数组中了，那么就打印出这一数组并得出其长度为18。
求各位达人们能给出一个快速的组合算法，能够解决，另开贴再给分，谢谢~

Answer 1

先扔块砖头：这里假定数组从1开始。以下为一些思路。
//主程序类似
var
  result: array of array of number;
for i:=1 to n
begin
  result := get_all_arraies(...,i); //获得指定长度的数组
  if result.length<>0 then
    输出 result.
end;然后get_all_arraies(aNumber[][],length)用来从2维数组aNumber中获得长度为length的数组
begin
  if length = 1
    return distinct aNumber[1][i]...  result1 := get_all_arraies(aNumber, length-1); //先获得比它长度少1的结果集合，存放在2维数组result1中。
  for i:=1  to result1.length-1 //检查aNumber[length]是否出现在数组result1[i]中
  begin
    for j:= 1 to 5
    begin
      if (aNumber[length][j] not in result1[i])
        result.add(result1[i], aNumber[j]);
    end
  end
end
然后再优化优化，例如将中间结果Result1保存下来等等。

Answer 2

有个思路看看行不行，
var
buf:array of array of byte;
二维数组剪枝
for i:=0 to x-1 do
begin
//如果buf[i+1][0]:=buf[i][0] then //这里可以用一个新的array of byte 存储数据，方便
                                  //下次对比
  buf[i+1][0]:=buf[i+1][4] ;//剪掉一个
  setlength(buf[I+1],4);//重新设定长度。
end;
//得到例如
// 1  2 12 14 20 
//  3  8 10 15 
//  11 
// 4  5  13 21 
//然后对数组排列
排序剪枝
如果
if length(buf)>0 then //还没剪枝完毕
 begin
for i:=0 to length(buf)
 for j:=0 to length(buf[i])
 setlength(resultbuf,length(resultbuf)+1);
  resultbuf[length-1]:=buf[i][j];
   //buf[i][j]:=buf[i][length]//把buf[i][j]付给resultbuf[length-1]然后剪枝...
end;匆忙的写了些，其实最主要的思想还是剪枝了，效果很好的
希望对你有用

Answer 3

回溯算法，太久不接触都忘了，刚刚写的.
const
    ARRAYROW            =           22;
    ARRAYCOL            =           5;    iSource:array[0..ARRAYROW-1,0..ARRAYCOL-1] of integer=(
    (1 , 2, 12 ,14 ,20),
    (1 , 3 , 8 ,10 ,15),
    (1 ,11 ,14 ,15 ,20),
    (4 , 5 ,10 ,13 ,21),
    (6 ,10 ,11 ,12 ,19),
    (3 , 5 , 7 ,13 ,15),
    (12 ,17, 18 ,20, 21),
    (10 ,12, 14 ,19, 22),
    (5 ,11 ,14 ,20 ,22),
    (6 ,14 ,17 ,19 ,20),
    (5 , 8 ,14 ,17 ,22),
    (6 , 7  ,8 ,12 ,17),
    (3 , 4 , 9 ,14 ,22),
    (11, 12 ,15 ,16, 21),
    (4 , 6  ,9 ,16 ,18),
    (4 , 7 ,11 ,17 ,20),
    (6 , 8 , 9 ,13 ,18),
    (2 , 3 , 4 ,07 ,20),
    (2 , 8 , 9 ,17 ,20),
    (1 , 8 ,12 ,13 ,17),
    (2 , 9 ,14 ,20 ,22),
    (5 , 6 ,15 ,21 ,22));function IfGoodValue(iResult:array of integer;iCnt:integer;iValue:integer):boolean;
var
    bFind:boolean;
    i:integer;
begin
    bfind:=false;
    for i:=0 to iCnt-1 do
    begin
        if iResult[i]=iValue then
            bFind:=true;
    end;
    Result:=not bFind;
end;function TForm1.GetNextValue(var iResult:array of integer;iCnt:integer):integer;
var
    i:integer;
    bAll:boolean;
    strTemp:string;
begin
    bAll:=true;
    if iCnt>=ARRAYROW then
    begin
        for i:=0 to iCnt-1 do
            strTemp:=strTemp+' '+IntToStr(iResult[i]);
        strTemp:=strTemp+' : '+IntToStr(iCnt);
        Memo2.Lines.Add(strTemp);
        exit;
    end;
        
    for i:=0 to ARRAYCOL-1 do
        if IfGoodValue(iResult,iCnt,iSource[iCnt,i]) then
        begin
            iResult[iCnt]:=iSource[iCnt,i];
            GetNextValue(iResult,iCnt+1);
            bAll:=false;
        end;    if bAll then
    begin
        for i:=0 to iCnt-1 do
            strTemp:=strTemp+' '+IntToStr(iResult[i]);
        strTemp:=strTemp+' : '+IntToStr(iCnt);
        Memo2.Lines.Add(strTemp);
    end;
end;procedure TForm1.Button2Click(Sender: TObject);
var
    iResult:array[0..ARRAYROW-1] of integer;
    i,j:integer;
    iCnt:integer;
begin
    for i:=0 to ARRAYCOL-1 do
    begin
        for j:=0 to ARRAYROW-1 do
            iResult[j]:=0;
        iCnt:=1;
        iResult[0]:=iSource[0,i];
        GetNextValue(iResult,iCnt);
    end;
end;

Answer 4

呵呵楼上的，你所提出的剪枝法是否想将各个数组之间相同的数字都压缩成一个？
如果是的话，那么下面的数组
a1= {1,2,3}
a2= {1,2,3}
是不是会被压缩成
a1= {1,2,3}
a2= {}
导致出来的结果长度只能是1?
实际上，结果可以是{1,2},{2,3},{3,1}...长度是可以达到2的。
有一阵没编程了，不知道说得对不对。

Answer 5

这样的想法怎么样？
对于2D序列组A[i,j] (i=1..n, j=1..5)
想像有这样一个树，根节点即第0级节点为空，然后...
第1级节点为A[1,1]... A[1,5],
A[1,1]下的2级节点为 A[2,1]... A[2,5]中不等于A[1,1]的数字,
...
A[i,j]下的节点为A[i+1,1]...A[i+1, 5]中没有出现在路径A[i,j]->根节点中的节点。
这样本题的答案就是查找这个树的最高层次并返回最长的路径。等会儿我再想想怎样估算这种算法的时间复杂度

Answer 6

火山的这个想法不错，但越往下，其节点数就会大量的增加。比如A[1,j](j=1..5)={1 2 12 14 20},相对于A[1,1]的下节点为{3 8 10 15}，A[1,2]、A[1,3]、A[1,4]、A[1,5]的下节点为{1 3 8 10 15}…………每往下一级，节点数就成倍数增加（在最坏的情况下）。而且，这个题的答案是要找出所有的数列并求出每个数列的长度。