Generating stable permutations

✍ Scribed by A. Panayotopoulos

• Book ID: 103056662
• Publisher: Elsevier Science
• Year: 1986
• Tongue: English
• Weight: 129 KB
• Volume: 62
• Category: Article
• ISSN: 0012-365X
• DOI: 10.1016/0012-365x(86)90121-4

✦ Synopsis

A permutation 0 = xlx2. • .xn on [n] = {1, 2, ..., n} is called stable when:

For instance, the permutation o = 72631485 is a stable permutation (s.p.).

This term is derived from the stability concept of the graphs, which has been used by Berge [1, p. 260] in the classic problem of eight queens. The solution of this problem is the set of stable permutations for n = 8.

Using the permutation trees [3], we determine the elements of the set T~ of s.p. on [n], with the help of the following sets:

F(]): The subset of In] with elements the terminal vertices of arcs with initial vertex j.

H(]): The subset of [n], the elements of which are vertices of the path with first vertex 0 and last vertex j.

A(j): The subset of/'/(j) = [n] -H(j'), the elements of which are excluded by the formula of definition of s.p. with xi e H(j)