中文摘要 |
首先,我們為排列問題定義一個順序表示法。第二,我們設計一個定序演算法,它可以根據一個n 項目的順序表示產生其對應的排列。藉由此演算法,我們可以依字母大小序地系統化產生所有的n 項目排列。第三,我們設計一個解序演算法,它可以根據一個n 項目的排列產生其對應的順序表示。藉由此兩個演算法,我們可以產生離一個n 項目的排列任意距離,依字母大小序而言,的另一個排列;此特點是我們的方法與其它研究最不同的地方。我們的方法還有另三項優點如下:第一,它不限制於必須是1 至n 的連續數目,甚至於可以無需藉由轉換而直接處理非數字的排列。第二,它也很適合用在其它的排列問題上,例如產生交替排列與錯位排列。第三,它也可擴展至針對含有重複元素的集合之排列問題上。
First, an ordinal representation scheme for permutations is defined. Next, an “unranking” algorithm that can generate a permutation of n items according to its ordinal representation is designed. By using this algorithm, all permutations can be systematically generated in lexicographic order. Finally, a “ranking” algorithm that can convert a permutation to its ordinal representation is designed. By using these “ranking” and “unranking” algorithms, any permutation that is positioned in lexicographic order, away from a given permutation by any specific distance, can be generated. This significant benefit is the main difference between the proposed method and previously published alternatives. Three other advantages are as follows: First, not being restricted to sequentially numbering the n items from one to n, this method can even handle items with non-numeral marks without the aid of mapping. Second, this approach is well suited to a wide variety of permutation generations such as alternating permutations and derangements. Third, the proposed method can also be extended to a multiset. |