Ranking and Unranking Restricted Permutations

2025-04-22 0 0 270.84KB 26 页 10玖币

侵权投诉

arXiv:2210.17021v2 [math.CO] 9 Nov 2023

Peter Kagey

November 10, 2023

Abstract

We discuss eﬃcient methods for unranking derangements and m´enage

permutations. That is, we will provide an algorithm to eﬃciently extract

the k-th earliest such permutation under the lexicographic ordering. We

will show that this problem can be reduced to the problem of computing

the number of restricted permutations with a given preﬁx, and then we

will use rook theory to solve this counting problem. This has applications

to combinatorics, probability, statistics, and modeling.

1 Overview and preliminaries

In 2020, Richard Arratia announced two $100 prizes with a similar ﬂavor, both

about unranking problems: given a strict total order on a ﬁnite set, when is it

possible to directly compute the i-th element with respect to the total order?

Problem 1 ($100 question).For n= 20 there are

895 014 631 192 902 121 >8.9·1017

elements of the set

{π∈Sn|π(i)6=i∀1≤i≤n},

which are called derangements.1Determine the 5×1017-th such permutation

when listed in lexicographic order.

Answer 1. The derangement in S20 with rank 5×1017 is

12 14 2 9 13 20 6 3 1 17 5 11 19 15 10 18 8 7 4 16.

The algorithm for computing this permutation will be described in Section 4.

Problem 2 ($100 question).For n= 20 there are

312 400 218 671 253 762 >3.1·1017

elements of the set

{π∈Sn|π(i)6∈ {i−1, i}(mod n)∀1≤i≤n},

which are called m´enage permutations.2Determine the 1017-th such permutation

1This function is described by sequence A000166 in the On-Line Encyclopedia of Integer

Sequences (OEIS) [4].

2This function is described by sequence A000179 in the OEIS [4].

when listed in lexicographic order.

Answer 2. The m´enage permutation in S20 with rank 1017 is

7 16 19 12 2 8 15 1 18 14 3 9 20 10 5 17 13 4 11 6.

The algorithm for computing this value will be described in Section 5.

Example 3. The 44 derangements in S5, ordered lexicographically are.

π1= 21453

π2= 21534

π3= 23154

π4= 23451

π5= 23514

π6= 24153

π7= 24513

π8= 24531

π9= 25134

π10 = 25413

π11 = 25431

π12 = 31254

π13 = 31452

π14 = 31524

π15 = 34152

π16 = 34251

π17 = 34512

π18 = 34521

π19 = 35124

π20 = 35214

π21 = 35412

π22 = 35421

π23 = 41253

π24 = 41523

π25 = 41532

π26 = 43152

π27 = 43251

π28 = 43512

π29 = 43521

π30 = 45123

π31 = 45132

π32 = 45213

π33 = 45231

π34 = 51234

π35 = 51423

π36 = 51432

π37 = 53124

π38 = 53214

π39 = 53412

π40 = 53421

π41 = 54123

π42 = 54132

π43 = 54213

π44 = 54231

In particular, unranking the 19th derangement in S5gives 35214; alterna-

tively, ranking the derangement 43251 gives 26.

To be explicit about what we wish to compute eﬃciently, we deﬁne the

notion of a unranking.

Deﬁnition 4. Let Cbe a ﬁnite set with a strict total order, and let {ci}|C|

i=1 be

the unique sequence of elements in Csuch that ci< ci+1 for all 1≤i < |C|.

Then a unranking is a map

unrankC:{1,2,...,|C|} → C

that sends i7→ ci.

An eﬃcient algorithm to unrank a collection of objects implies an eﬃcient

algorithm for sampling from the collection uniformly at random by sampling

the indices uniformly at random. This can be of use in the case of Monte Carlo

simulations and other instances where it is useful to be able to sample uniformly

from a collection of combinatorial objects.

As the name suggests, every unranking problem comes with a dual problem

called the “ranking problem.”

Deﬁnition 5. Aranking of a ﬁnite set Cwith a strict total order is a map

rankC:C→ {1,2,...,|C|}

that sends ci7→ i.

The existence of both eﬃcient ranking and unranking maps implies the ex-

istence of an eﬃcient encoding for these objects, which may be of interest to

computer scientists. The encoding works by ranking an object to get its index,

which then can be stored in as a positive integer and unranked on retrieval to

recover the original object.

In the remaining sections, we will show how we resolved both of the above

problems in order to claim Richard Arratia’s two $100 prizes. In particular, we

will construct an algorithm for ranking and unranking both derangements and

m´enage permutations under the lexicographic ordering. We will show that the

existence of an eﬃcient way to count the number of such permutations with a

given preﬁx implies that there is an eﬃcient way to compute the ranking and

unranking maps. Then we will develop some ideas from rook theory and apply

them to the context of derangements and m´enage permutations.

2 Preﬁx counting and word ranking

In both the case of unranking derangements and menage permutations (and in

many other applications) our combinatorial objects are words in lexicographic

order, which is a generalization of alphabetical order.

We begin by developing a general theory for unranking collections of words

in lexicographic order by counting the number of words with a given preﬁx.

2.1 Words with a given preﬁx

We will start by introducing some basic deﬁnitions about words and preﬁxes,

and to formalize the notion of lexicographic order.

Deﬁnition 6. A ﬁnite word wover an alphabet Ais a ﬁnite sequence {wi∈

A}N

i=1.

The collection of ﬁnite words over the alphabet Ais denoted by WA, or just

Wwhen the alphabet is implicit from context.

Deﬁnition 7. A word w={wi∈A}N

i=1 is said to begin with a preﬁx αof

length Mif M≤N,α={αi∈A}M

i=1, and wi=αifor all i≤M.

Deﬁnition 8. A word wis said to be before w′in lexicographic order if

either wis a proper preﬁx of w′, or if at the ﬁrst position, i, where wand w′

diﬀer, wi< w′

With these deﬁnitions established, we can turn the problem of unranking

words into a problem about counting words with speciﬁed preﬁxes.

Theorem 9. For k > 0, let Wbe a set of nonempty words on the alphabet

[n] = {1,2,...,n}, and let C(Wbe a ﬁnite subset of words on this alphabet,

with a total order given by its lexicographic order.

Let #preﬁxC:W→Cbe the function that counts the number of words in

Cthat begin with a given preﬁx.

Then the unranking function can be computed recursively by

unrankC(i) = fC

i((1),0) (1)

where

i(α, j) =











i(α′, j + #preﬁxC(α)) i > j + #preﬁxC(α) (2a)

i(α′′, j)α6∈ Cand i≤j+ #preﬁxC(α) (2b)

i(α′′, j + 1) α∈C,i≤j+ #preﬁxC(α),

and i6=j+ 1 (2c)

α α ∈Cand i=j+ 1,(2d)

where

α= (α1, α2,...,αℓ),

α′= (α1, α2,...,αℓ−1,1 + αℓ),

α′′ = (α1, α2,...,αℓ,1),

and jdenotes the number of words in Cthat occur strictly before α.

Proof. We make three claims that we will prove using induction on the recursive

applications of fC

i(α, j): (1) that jis the number of words in Cthat occur

strictly before α, (2) that α≤wi, and (3) that the sequence of αs is strictly

increasing.

This ﬁnal claim (the sequence of αs is strictly increasing) follows from the

observation that α < α′′ < α′in lexicographic order.

Because each iteration increases either jor ℓ(the number of letters in α) or

both, the number of recursive applications of fC

irequired to determine wiis at

most i+ maxw∈W|w|, which is ﬁnite because Wonly contains of ﬁnite words.

The base case is clear: We start with fC

i((1),0) because (1) is the lexico-

graphically earliest word, so 0 nonempty words strictly precede it, and (1) ≤wi.

We will repeatedly use the observation that if jwords precede α, then a

word has preﬁx αif and only if its index is in (j, j + #preﬁxC(α)]. Note that

this range is empty whenever there are no words preﬁxed by α.

Case (2a).Because j+#preﬁxC(α) is the index of the last word that begins

with α, if i > j + #preﬁxC(α), then wimust begin with a length-ℓpreﬁx that

is lexicographically later than α.

By construction, α′is the lexicographically earliest word of length ℓthat

comes after α, therefore α′≤wi. As such, the number of words that strictly

precede α′is j+ #preﬁxC(α), which is the sum of the number of words that

occur strictly before αand the number of words that have preﬁx α.

Case (2b).If α6∈ Cand i≤j+#preﬁxC(α), then αis a proper preﬁx of wi,

and wiis of length at least ℓ+ 1. By construction, α′′ is the lexicographically

earliest word of length ℓ+ 1 that has a preﬁx of α, so α′′ ≤wi, and the number

of words in Cthat precede α′′ is equal to j, the number of words that precede

α.

Case (2c).If α∈C,i≤j+ #preﬁxC(α), and i6=j+ 1 then αmust be the

word at index j+ 1 < i, because αitself is the lexicographically earliest word

with the preﬁx α. Because words cannot appear multiple times in C,wimust

have αas a proper preﬁx. Therefore α′′ ≤wiand the number of words that

strictly precede α′′ is j+ 1: the number of words that strictly precede αplus α

itself.

Case (2d).If α∈Cand i=j+ 1, then wi=αbecause αitself is the

lexicographically earliest word with the preﬁx α, so it must occur at index

i=j+ 1.

Notice that each recursive call of fC

iincreases the sum of the letters of α. If

we suppose that Cis a ﬁnite set of words on the alphabet [n] of length at most

k, then unranking a word from C(≤k)requires at most nk recursive applications

of fC(≤k)

Therefore if there exists a polynomial time algorithm for computing #preﬁxC,

then there exists an unranking algorithm that is polynomial in the size of the

alphabet Aand the length of the longest word. In the case of restricted per-

mutations, each of these grow linearly with the number of letters in the m´enage

permutations.

2.2 Ranking words

Just as we can recursively ﬁnd a word at a given index, we can also recursively

ﬁnd a index corresponding to a given word.

Theorem 10. If C(Wis a collection of nonempty words over the alphabet

[n], then the rank of the word w∈Ccan be computed as the sum

rankC(w) =

|w|

i=1 C(w(i)) +

wi−1

ℓ=1

#preﬁxC(wℓ

(i−1))!

where

w= (w1, w2,...,w|w|),

w(i)= (w1, w2,...,wi−1, wi),

wℓ

(i−1) = (w1, w2,...,wi−1, ℓ),

and C:W→ {0,1}is the indicator function of C, where C(x) = 1 if and

only if x∈C.

Proof. Note that the inner sum

C(w(i)) +

wi−1

ℓ=1

#preﬁxC(wℓ

(i−1))

文档加载中……请稍候！
如果长时间未打开，您也可以点击刷新试试。

下载文档到电脑，查找使用更方便

10 玖币 0人已下载

立即下载

摘要：

arXiv:2210.17021v2[math.CO]9Nov2023RankingandUnrankingRestrictedPermutationsPeterKageyNovember10,2023AbstractWediscusseﬃcientmethodsforunrankingderangementsandm´enagepermutations.Thatis,wewillprovideanalgorithmtoeﬃcientlyextractthek-thearliestsuchpermutationunderthelexicographicordering.Wewillshowth...

展开>> 收起<<

Ranking and Unranking Restricted Permutations.pdf

共26页,预览5页

还剩页未读，继续阅读

声明：本站为文档C2C交易模式，即用户上传的文档直接被用户下载，本站只是中间服务平台，本站所有文档下载所得的收益归上传人(含作者)所有。玖贝云文库仅提供信息存储空间，仅对用户上传内容的表现方式做保护处理，对上载内容本身不做任何修改或编辑。若文档所含内容侵犯了您的版权或隐私，请立即通知玖贝云文库，我们立即给予删除！

Ranking and Unranking Restricted Permutations

相关推荐

开通VIP享超值会员特权

作者详情

相关内容

热门标签

举报选择: