Re: [問題] 環狀排列演算法
※ 引述《EdisonX (閉上眼的魚)》之銘言：
: 目的是要窮舉所有可能之環狀排列，
: 一般排列 P(n,m)，可用遞迴或旋轉法完成，
: 但若只需環狀排列時，個數是 P(n,m)/n，
: 目前小弟之作法為過程中先紀錄結果至一集合
: 再針對產生之排列去檢查集合是否重覆，
: 如此不但速度慢，又吃記憶體，
: 不知這問題目前是否已有演算法可產生所有環狀排列之可能？
: 感謝各位！
1234這一列數字有六個間隔,如果視為環狀則有五個間隔.
加入一個數字5,則在視為環狀時, 51234 與 12345 是同一組環狀排列.
所以,在1234加入5應該產生 15234, 12534, 12354, 12345.
1只有一種環狀排列. 1,加入2,也只有一種環狀排列,由只將2放到1後面產生.
12,加入3,則是 132, 123.
產生1234的環狀排列,是在123環狀排列{123,132}中加入4.
123加入4產生 1423, 1243, 1234; 132加入4產生 1432, 1342, 1324.
所以1234的環狀排列是{1423,1243,1234,1432,1342,1324}.
這樣應該可以處理掉這個問題吧.
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 61.231.65.98
推
01/23 20:55, , 1F
01/23 20:55, 1F
→
01/23 21:23, , 2F
01/23 21:23, 2F
※ 編輯: yauhh 來自: 61.231.65.98 (01/23 21:38)
→
01/24 08:37, , 3F
01/24 08:37, 3F
討論串 (同標題文章)