文章基本信息

标题：Pattern Popularity in Γ₁ − Non Deranged Permutations: An Algebraic and Algorithmic Approach
本地全文：下载
作者：K. O. Aremu ; A. H. Ibrahim ; S. Buoro 等
期刊名称：Annals. Computer Science Series
印刷版ISSN：1583-7165
电子版ISSN：2065-7471
出版年度：2017
卷号：15
期号：2
页码：115-122
出版社：Mirton Publishing House, Timisoara
摘要：Given a permutation pattern say τ = τ₁ ... τ_k ∈ S_k and permutation ω = ω₁ ... ω_n ∈ S , we say that ω contains the pattern τ if there exist 1 ≤ i₁ < ... < i_k ≤ n such that red(ω_i1 ... ω_ik) = τ. Each subsequence in ω is known as an occurrence of the pattern ω. Conversely, if there exists no occurrence of τ in ω, then we say that the permutation ω avoids the pattern τ. The popularity of a pattern τ is the total number of copies of τ within all permutations of a set. In this work, we address popularity of length-3 patterns in Γ1 - non deranged permutations in two approaches; algebraically and algorithmically. We first establish algebraically that pattern τ₁ is the most popular and pattern τ₃, τ₄ and τ₅ are equipopular in G^Γ1_p. We further provide efficient algorithms that also report same results on popularity and equipopularity of patterns of length-3 in G^Γ1_p as obtained by the algebraic approach.
关键词：Permutation; Pattern; Popularity; Equipopularity; Sorting.