問題: 如何從一堆數對中,找出哪些數對是連碰的呢? Ex:01-02 02-03 01-03 02-04 04-05 05-06 以上可辨識出01,02,03是連續碰產生的(換言之01,02,03是組合的). 請問有哪位高手有方法呢? 如果數對包含三個以上呢? 如 01-02-03 02-03-04 01-02-04 01-03-04 兩個的我是用兩個迴圈,但好像不是正解!! 能提供意見嗎?

你的意思是不是 說 因為 這些數對中 01,02,03 三取二的 組合都出現了所以 是01,02,03 連碰?

引言: 你的意思是不是 說 因為 這些數對中 01,02,03 三取二的 組合都出現了所以 是01,02,03 連碰?

是的,原本我想用列舉法將01,02,03,04,05,06,07..........N 不管是X個取Y都先產生出來,再去比對,但這樣當N越大時,要費很多時間 幾乎是2,3個小時. 所以這個方法不能用, 目前我可以做到X取2的組合在X*X-1*X-2次迴圈算出, 但X取Y 當Y>2 時就沒輒了!! 你有好方法嗎?

我對這個提問有兩個意見, 1. 對於非程式設計專業術語稍微解釋或提供相關URL: 像 我對"連碰"的認識僅止於:一種包牌的方式, 還要做一次確認. 2. 稍微解釋一下自己目前的解法: 這樣做也許大大們一下就可以找出可以改進的部份. 更表明問問題的誠意.    我的解題基調 是扣除法, 以第一個例子說明:    1. 先選出要檢查的數字組合, 以第一個例子來說就是由 01,02,03,04,05,06 選出 3 個以上來檢查連碰, 檢查時由 大到小, 並利用 Cmn 及 數對數量來排除不必的計算, 以第一個例子來說 C_6_2=15, C_5_2=10, C_4_2=6 ...而數對只有6個, 所以 6選2, 5選2 就不必算了. 由 所有的 4選2 開始 到 所有的 3選2 都比對過才停止, 要檢查的 4選2 有 C_6_4=15種,3選2 有 C_6_3=20種     2. 針對每一種 4選2 或 3選2 計算所有"組合連碰數" C_4_2=6, C_3_2=3 3. 針對每一種 4選2 或 3選2 刪除含有不屬於該種組合元素的數對, 刪完之後檢查剩餘的組合數數量, 如果等於該組合的"組合連碰數", 該組連碰就對到了.    以第一題為例,  選出 01,03,04,06; "組合連碰數"=6 數對 01-02 會被扣掉(02不在組合內), 扣掉後剩 5 對, 5<6 這組就不可能了 ... 選出 01,02,03; "組合連碰數"=3 數對 02-04,04-05,05-06 被扣掉後剩3對恰好等於"組合連碰數"3. 所以 這個連碰在數對內 如果你滿意這個答案, 可否請你將答案以 Delphi 實作出來並用你的名義發表.才符合這個論壇的範疇...... 發表人 - malanlk 於 2005/07/29 08:17:48

我覺得 [am531030] 的問題應該是要處理「資料結構」或「離散數學」中所謂路徑的問題，把[am531030]所提及的01~06六個值各視為一個城市，而各個城市間的連接路徑如下： 01-02 02-03 01-03 02-04 04-05 05-06    以上可以利用圖形表示，在圖上畫六個點代表01~06，而將上述的連接關係，將兩個點連接起來，如「01-02」就在圖上將01城市及02城市以線連結，最後會發現01,02,03三個會形成一個封閉路徑。而[iam531030]要解的應該是找出所有的封閉路徑。     發表人 - jeff377 於 2005/07/29 12:03:34

有意思, 那 3 數對就是要找出宇宙中星球形成的封閉空間哦... 所以可否提供「離散數學」上的程式解法, 讓大家分享這個有趣的議題?

引言: 問題: 如何從一堆數對中,找出哪些數對是連碰的呢? Ex:01-02 02-03 01-03 02-04 04-05 05-06 以上可辨識出01,02,03是連續碰產生的(換言之01,02,03是組合的). 請問有哪位高手有方法呢? 如果數對包含三個以上呢? 如 01-02-03 02-03-04 01-02-04 01-03-04 兩個的我是用兩個迴圈,但好像不是正解!! 能提供意見嗎?

名詞解釋: 連碰:若01,02,03,04,05連碰二星,則有C5取2共10碰 代表 01-02 01-03 01-04 01-05 02-03 02-04 02-05 03-04 03-05 04-05 共10碰 互碰:也稱柱碰,如01,03,04碰02,05則為3x2=6碰 01-02 01-05 03-02 03-05 04-02 04-05 不知道這樣解釋,有沒有清楚? 我的演算法如下:(程式還沒開始寫,Sorry),只解決取2的問題 假設:數對放在資料庫中,有四個欄位 No1 String(2)==>會比No2小 No2 String(2) IsI Boolean ==>此碰是否已被當過開始的基本碰 IsT Boolean ==>此碰是否已加入某段連碰集合中 Primary Key:No1 No2 作法: Maxno為最大數,如大樂透有49個球,則Maxno=49 For i=1 to Maxno-1 For j=i 1 to Maxno 利用IsI判斷i,j此碰可當開始的基本碰 若可以 則將i,j放入陣列Carray中 for k=j 1 to Maxno //假設加入K號碼 以K與Carray中的數,產生所有必須存在的數對 一一檢查資料庫(並檢查IST),若有一個數對不符合(不存在資料庫中),則代表K不能加入Carray中 反之若全部都有在資料庫中 則K加入Carray中==>且更新資料庫中的IST欄位 重複迴圈 這幾天會,趕快將程式寫好,Post上來, 先針對演算法說明,不知這樣大大,我的作法,是不是還不清楚,有沒有符合討論區的規定!!請各位大大指教 :)

這是之前在Programmer 深度論壇中討論的話題 提供你做參考.    其中個人是建議用 set operator來處理這個問題.    http://forum.vclxx.org/topic.php?TOPIC_ID=13388&FORUM_ID=3&CAT_ID=2&Topic_Title=%BC%D6%B3z%C0H%BE%F7%BF%EF%B8%B9%AA%BA%B0%DD%C3D&Forum_Title=Misc < >< > >< >< > 發表人 -

連碰:若01,02,03,04,05連碰二星,則有C5取2共10碰 互碰:也稱柱碰,如01,03,04碰02,05則為3x2=6碰    不就是 C3取2 與 C2取1 來組合    這樣不會很難阿？    不過什麼又是「基本碰」？為什麼要搞一堆複雜的名詞？這樣你的程式也會跟著複雜，而且大家不見得懂 問題越簡化，演算法也會越簡單 所以你到底要做什麼，要說清楚，不是在寫論文，所以不要說一大堆名詞或術語，簡單說出你的目的，這樣大家不用猜半天，你也不用費時間解釋一堆 你要的是？ 1. 49 中選 x 個號碼，並且不重複？(x 介於 1 ～ 49) 2. 數列 A 與 數列 B ， A 中取 x 個 ， B 中取 y 個，來組合？且不重複？     雖然前面你的解釋，可以瞭解 但後面你的作法就看不懂，基本碰，是什麼？如何才能當基本碰？成為基本碰後又有何影響？    >數對放在資料庫中,有四個欄位 >No1 String(2)==>會比No2小 >No2 String(2) >IsI Boolean ==>此碰是否已被當過開始的基本碰 >IsT Boolean ==>此碰是否已加入某段連碰集合中 >Primary Key:No1+No2    所以你指的是一個 Array 紀錄，包含有四個欄位，如你所說，並以 No1+No2 為索引，而 IsI 指的是，是否當成一開始就存在的部分，或是說，當成不用選取，一開始，就是開頭預設值，而之後再選取元素來加入這個集合，IsT 是指，已經成為某集合中的一個部分或片段？    >作法: 對不起，以下我就看不懂你要做什麼了，可以的話，用簡單一點的敘述 例如 49 個球，然後呢？選幾個嗎？ 覺得你將問題搞得很複雜，好像可以看得懂你要做的事，卻又無法確認你是否真的是要那樣 所以 1. 要嘛，你用文字簡單敘述你要做的事 2. 不然，你可以用虛碼 表現出你要的目標與步驟 不要又是文字又是程式碼，不要混在一起，你可以去參考許多書籍(如資料結構、演算法)，書上都很有條理的敘述，文字歸文字，盡量簡單，虛碼歸虛碼，就算註解，也是在虛碼外    >Maxno為最大數,如大樂透有49個球,則Maxno=49 >For i=1 to Maxno-1 >For j=i+1 to Maxno >利用IsI判斷i,j此碰可當開始的基本碰 IsI 預設值？ >若可以 >則將i,j放入陣列Carray中 i , j ? 指的是號碼？還是前述陣列的索引？ >for k=j+1 to Maxno //假設加入K號碼 這樣才知道這個 for 在不在 上面的 for 回圈內，而上面的兩個回圈是否獨立，還是有相關，就你的變數來推論 應該是這樣吧

for i = .... do
 begin
  for j := .....do
   begin
    for k := ..... do
     begin         end
   end
 end 

>以K與Carray中的數,產生所有必須存在的數對 >一一檢查資料庫(並檢查IST),若有一個數對不符合(不存在資料庫中),則代表K不能加入Carray中 >反之若全部都有在資料庫中 >則K加入Carray中==>且更新資料庫中的IST欄位 >重複迴圈

unit Unit1;    interface    uses
  Windows, Messages, SysUtils, Variants, Classes, Graphics, Controls, Forms, Dialogs, StdCtrls;    type
  TLotto = 1..49;        //宣告元素範圍
  TLottoSet = set of TLotto;  //宣告TLotto元素之集合([]~[1..49])
                                   //SizeOf(TLottoSet) = 7;
                                   //(固定長度利於記憶體配置與存檔)      TLottos = array of TLotto; //TLotto 元素陣列(nil~([1],[2]..[49])      TArrayOfLottoSet = array of TLottoSet;      TForm1 = class(TForm)
    Button1: TButton;
    Label1: TLabel;
    ListBox1: TListBox;
    Button2: TButton;
    Button3: TButton;
    procedure Button1Click(Sender: TObject);
    procedure Button2Click(Sender: TObject);
    procedure Button3Click(Sender: TObject);
  private
  public
    function Random: TLotto; overload;//亂數產生一個TLotto
    function Random(ElementCount: Integer): TLottoSet; overload;//亂數產生一組TLottoSet
    function CountOf(LottoSet: TLottoSet): Integer; overload; //TLottoSet中之元素個數
    function CountOf(M, N: Integer): Int64; overload;                                  //C_M_N 之子集合個數
    function LottoSet_TO_Lottos(LottoSet: TLottoSet): TLottos;        //將TLottoSet轉換成TLottos元素陣列        function ExpandLottoSet(LottoSet: TLottoSet;
            ElementCount: Integer): TArrayOfLottoSet;//展開C_M_N 之所有子集合        function LottoSetToStr(LottoSet: TLottoSet): string;                        //顯示TLottoSet的字串形式
    
  end;    var
  Form1: TForm1;    implementation    {$R *.dfm}    { TForm1 }    function TForm1.Random: TLotto;
begin
  Result := System.Random(High(TLotto)) 1;
end;    function TForm1.CountOf(LottoSet: TLottoSet): Integer;
var
  L: TLotto;
begin
  Result := 0;
  for L := Low(TLotto) to High(TLotto) do
  begin
    if LottoSet = [] then Break
    else if L in LottoSet then
    begin
      Inc(Result);
      LottoSet := LottoSet - [L];
    end;
  end;
end;    function TForm1.Random(ElementCount: Integer): TLottoSet;
begin
  Result := [];
  ElementCount := ElementCount mod (High(TLotto) 1); //限定ElementCount = 0~49
  while CountOf(Result) < ElementCount do
    Result := Result   [Random];
end;    function TForm1.LottoSet_TO_Lottos(LottoSet: TLottoSet): TLottos;
var
  L: TLotto;
  I, Len: Integer;
begin
  Result := nil;
  Len := CountOf(LottoSet);
  if Len > 0 then
  begin
    SetLength(Result, Len);
    I := 0;
    for L := Low(TLotto) to High(TLotto) do
    begin
      if L in LottoSet then
      begin
        Result[I] := L;
        Inc(I);
      end;
      if I = Len then Break;
    end;
  end;
end;    function TForm1.CountOf(M, N: Integer): Int64;
var
  V: Double;
  I, J: Integer;
begin
  Result := 0;
  M := M mod (High(TLotto) 1);//M = 0 ~ 49;
  N := N mod (High(TLotto) 1);//N = 0 ~ 49;
  if (M>0) and (M >= N) then
  begin
    V := 1;
    for J := M downto M-N 1 do V := V * J;
    for I := 1 to N do V := V / I;
    Result := Round(V);
  end;
end;    function TForm1.ExpandLottoSet(LottoSet: TLottoSet; ElementCount: Integer): TArrayOfLottoSet;
var
  LS: TLottoSet;
  Lottos: TLottos;
  TotalElementCount, Len, Index: Integer;      procedure DO_ExpandLottoSet(Layer: Integer;
    P: Integer; var LS: TLottoSet; var Index: Integer);
  var
    I: Integer;
  begin
    for I := P to TotalElementCount-ElementCount Layer do
    begin
      LS := LS   [Lottos[I]];
      if CountOf(LS) = ElementCount then
      begin
        Result[Index] := LS;
        Inc(Index);
      end
      else DO_ExpandLottoSet(Layer 1, I 1, LS, Index);
      LS := LS - [Lottos[I]];
    end;
  end;
  
begin
  Result := nil;
  TotalElementCount := CountOf(LottoSet);
  Len := CountOf(TotalElementCount, ElementCount);
  if Len > 0 then
  begin
    SetLength(Result, Len);
    Lottos := LottoSet_To_Lottos(LottoSet);
    LS := [];
    Index := 0;
    DO_ExpandLottoSet(0, 0, LS, Index);
  end;
end;    function TForm1.LottoSetToStr(LottoSet: TLottoSet): string;
var
  L: TLotto;
begin
  Result := '';
  for L := Low(L) to High(L) do
    if L in LottoSet then
    begin
      if Result = '' then
        Result := Format('%2.2d', [L])
      else Result :=
        Result   ', '   Format('%2.2d', [L]);
      LottoSet := LottoSet - [L];
      if LottoSet = [] then Break;
    end;
  Result := '['   Result   ']';
end;    //TEST
procedure TForm1.Button1Click(Sender: TObject);
var
  A: TArrayOfLottoSet;
  I: Integer;
begin
  SetLength(A, 100);//動態產生100組TLottoSet
  try
    ListBox1.Clear;
    for I := 0 to Length(A)-1 do
    A[I] := Random(6);        //元素個數=6
    for I := 0 to Length(A)-1 do        //顯示
      ListBox1.Items.Add(LottoSetToStr(A[I]));
  finally
    A := nil;
  end;
end;    //TEST
procedure TForm1.Button2Click(Sender: TObject);
var
  LS: TLottoSet;
  A: TArrayOfLottoSet;
  I: Integer;
begin
  LS := Random(10);//[1..10];
  A := ExpandLottoSet(LS, 6);//展開子集合(C_10_6)
  try
    ListBox1.Clear;
    for I := 0 to Length(A)-1 do//顯示
      ListBox1.Items.Add(LottoSetToStr(A[I]));
    Label1.Caption := IntToStr(ListBox1.Count);
  finally
    A := nil;
  end;
end;    //TEST
procedure TForm1.Button3Click(Sender: TObject);
var
  LS: TLottoSet;
  A: TArrayOfLottoSet;
  I: Integer;
begin
  LS := [1..6];
  A := ExpandLottoSet(LS, 2);//C_6_2之子集合
  try
    ListBox1.Clear;
    for I := 0 to Length(A)-1 do
      if A[I] * [1..3,6] = A[I] then //只含元素[1..3, 6]之子集合
        ListBox1.Items.Add(LottoSetToStr(A[I]));
    Label1.Caption := IntToStr(ListBox1.Count);
  finally
    A := nil;
  end;
end;    end.