PTT數位生活區 / Prob_Solve (計算數學 Problem Solving)

Re: [問題] 環狀排列演算法

看板Prob_Solve (計算數學 Problem Solving)作者EdisonX (閉上眼的魚)時間13年前 (2012/01/24 09:23)推噓0(0推 0噓 0→)

留言0則, 0人參與討論串3/3 (看更多)

※ 引述《EdisonX (閉上眼的魚)》之銘言： : 目的是要窮舉所有可能之環狀排列， : 一般排列 P(n,m)，可用遞迴或旋轉法完成， : 但若只需環狀排列時，個數是 P(n,m)/n， : 目前小弟之作法為過程中先紀錄結果至一集合 : 再針對產生之排列去檢查集合是否重覆， : 如此不但速度慢，又吃記憶體， : 不知這問題目前是否已有演算法可產生所有環狀排列之可能？ : 感謝各位！謝謝 LPH66 與 yauhh 大之指導，目前環狀排列應無大礙，以 LPH66 之演算法有個細節確認一下假設 CirclePermutation(arr, n=7,m=3)，其中 arr 已事先由小至大排序過，以 LPH66 之方式 (先固定最小元素，再對其它 n-1 個元素做 Permutation 即可) 應只需選到 arr 前 m-1 小的，做 Permutation 即可？ ---- 另想進一步請教以下問題是否為「無解」問題？ (有點無厘頭的問法，因只要知道結果是否無解，或解法，不重證明 XD) 若將 1 2 3 4 視為一環狀排列，( 2 3 4 1 / 3 4 1 2 / 4 1 2 3 為同組)，是否有另一演算法，除了環狀排列外，也將 (順時針/逆時針) 也視為同一組？即 1 1 2 4 (逆時針) 4 2 (順時針) 3 3 也視為同一組，如此一來窮舉次數便從 P(n,m)/n 又降為了 P(n,m)/(2n)，但不確定目前此法是否只剩筆對一法？目前看來，似乎和「反序」有點淵源， 1 2 5 (1 2 3 4 5/2 3 4 5 1/3 4 5 1 2/4 5 1 2 3/ 5 1 2 3 4) 3 4 ---> 固定 1 對其它四個元素做反序得 1 5 2 (1 5 4 3 2/5 4 3 2 1/4 3 2 1 5/3 2 1 5 4/2 1 5 4 3) 4 3 再次感謝各位不吝賜教！小弟感激不盡!! -- If there is no tomorrow, I want to see u last time. -- ※ 發信站: 批踢踢實業坊(ptt.cc) ◆ From: 180.177.69.239