prevPermutation<T> function

bool prevPermutation<T>(
  1. List<T> list, {
  2. int compare(
    1. T,
    2. T
    )?,
})

Transforms the list into the previous permutation from the set of all permutations that are lexicographically ordered.

Returns true if the new permutation is lexicographically strictly less than the previous. If the list is already in its lowest permutation (e.g. sorted ascending), it wraps around to the highest permutation and returns false.

Example:

final list = [3, 2, 1];
prevPermutation(list); // list is now [3, 1, 2]

Implementation

bool prevPermutation<T>(List<T> list, {int Function(T, T)? compare}) {
  compare ??= _defaultCompare;
  if (list.length <= 1) return false;

  var i = list.length - 1;
  while (true) {
    var ii = i;
    --i;
    if (compare(list[ii], list[i]) < 0) {
      var j = list.length - 1;
      while (compare(list[j], list[i]) >= 0) {
        --j;
      }
      _swap(list, i, j);
      _reverseRange(list, ii, list.length);
      return true;
    }
    if (i == 0) {
      _reverseRange(list, 0, list.length);
      return false;
    }
  }
}