Steinhaus-Johnson-Trotter algorithm

The Steinhaus-Johnson-Trotter algorithm generates all permutations of a list in an order such that each permutation is obtained by transposing two adjacent elements from the previous permutation.

Each element of the list has a direction (initialized at -1) that changes at each permutation and that is used to determine which elements to transpose. Thus in addition to the permutation itself, the direction of each element is also stored.

Note that the permutations are not generated in lexicographic order.

AUTHORS:

  • Martin Grenouilloux (2024-05-22): initial version

class sage.combinat.SJT.SJT(l, directions=None)[source]

Bases: CombinatorialElement

A representation of a list permuted using the Steinhaus-Johnson-Trotter algorithm.

Each element of the list has a direction (initialized at -1) that changes at each permutation and that is used to determine which elements to transpose. The directions have three possible values:

  • -1: element transposes to the left

  • 1: element transposes to the right

  • 0: element does not move

Thus in addition to the permutation itself, the direction of each element is also stored.

Note that the permutations are not generated in lexicographic order.

Warning

An SJT object should always be created with identity permutation for the algorithm to behave properly. If the identity permutation is not provided, it expects a coherent list of directions according to the provided input. This list is not checked.

Todo

Implement the previous permutation for the Steinhaus-Johnson-Trotter algorithm.

EXAMPLES:

sage: from sage.combinat.SJT import SJT
sage: s = SJT([1, 2, 3, 4]); s
[1, 2, 3, 4]
sage: s = s.next(); s
[1, 2, 4, 3]
sage: p = Permutation(s._list, algorithm='sjt', sjt=s)
sage: p
[1, 2, 4, 3]
sage: p.next()
[1, 4, 2, 3]

>>> from sage.all import *
>>> from sage.combinat.SJT import SJT
>>> s = SJT([Integer(1), Integer(2), Integer(3), Integer(4)]); s
[1, 2, 3, 4]
>>> s = s.next(); s
[1, 2, 4, 3]
>>> p = Permutation(s._list, algorithm='sjt', sjt=s)
>>> p
[1, 2, 4, 3]
>>> p.next()
[1, 4, 2, 3]
next()[source]

Produce the next permutation of self following the Steinhaus-Johnson-Trotter algorithm.

OUTPUT: the list of the next permutation

EXAMPLES:

sage: from sage.combinat.SJT import SJT
sage: s = SJT([1, 2, 3, 4])
sage: s = s.next(); s
[1, 2, 4, 3]
sage: s = s.next(); s
[1, 4, 2, 3]

>>> from sage.all import *
>>> from sage.combinat.SJT import SJT
>>> s = SJT([Integer(1), Integer(2), Integer(3), Integer(4)])
>>> s = s.next(); s
[1, 2, 4, 3]
>>> s = s.next(); s
[1, 4, 2, 3]