nextPermutation<T> function

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

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

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

Example:

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

Implementation

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