A New Method for Generating Permutations in Lexicographic Order

一個依字母大小序產生排列的新方法

郭定(Ting Kuo)

《科學與工程技術期刊》 5卷4期 (2009/12) Pp. 21-29

https://doi.org/10.7117/JSET.200912.0021

摘要

首先，我們爲排列問題定義一個順序表示法。第二，我們設計一個定序演算法，它可以根據一個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.

並列關鍵字

lexicographic order ； ordinal representation ； permutation ； ranking ； unranking