TOPICS
Search

Encroaching List Set


A structure consisting of an ordered set of sorted lists such that the head and tail entries of later lists nest within earlier ones. For example, an encroaching list set for {6,7,1,8,2,5,9,3,4} is given by {{1,6,7,8,9},{2,5},{3,4}}. Encroaching list sets can be computed using EncroachingListSet[l] in the Wolfram Language package Combinatorica` .

It is conjectured that the number of encroaching lists associated with a random permutation of size n is ∼sqrt(2n) for sufficiently large n (Skiena 1988; Skiena 1990, p. 78).


Explore with Wolfram|Alpha

References

Skiena, S. "Encroaching Lists as a Measure if Presortedness." BIT 28, 775-784, 1988.Skiena, S. "Encroaching List Sets." §2.3.7 in Implementing Discrete Mathematics: Combinatorics and Graph Theory with Mathematica. Reading, MA: Addison-Wesley, pp. 75-76, 1990.

Referenced on Wolfram|Alpha

Encroaching List Set

Cite this as:

Weisstein, Eric W. "Encroaching List Set." From MathWorld--A Wolfram Web Resource. https://mathworld.wolfram.com/EncroachingListSet.html

Subject classifications