Merge pull request #2049 from def-/permutations

Add nextPermutation and prevPermutation

1 files changed, 59 insertions, 0 deletions

diff --git a/lib/pure/algorithm.nim b/lib/pure/algorithm.nim
index 0358a9a81..20bfc5c7c 100644
--- a/lib/pure/algorithm.nim
+++ b/lib/pure/algorithm.nim
@@ -220,3 +220,62 @@ proc product*[T](x: openArray[seq[T]]): seq[seq[T]] =
     result.add(res)
     index = 0
     indexes[index] -=1
+
+proc nextPermutation*[T](x: var openarray[T]): bool {.discardable.} =
+  ## Calculates the next lexicographic permutation, directly modifying ``x``.
+  ## The result is whether a permutation happened, otherwise we have reached
+  ## the last-ordered permutation.
+  ##
+  ## .. code-block:: nim
+  ##
+  ##     var v = @[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
+  ##     v.nextPermutation()
+  ##     echo v
+  if x.len < 2:
+    return false
+
+  var i = x.high
+  while i > 0 and x[i-1] >= x[i]:
+    dec i
+
+  if i == 0:
+    return false
+
+  var j = x.high
+  while j >= i and x[j] <= x[i-1]:
+    dec j
+
+  swap x[j], x[i-1]
+  x.reverse(i, x.high)
+
+  result = true
+
+proc prevPermutation*[T](x: var openarray[T]): bool {.discardable.} =
+  ## Calculates the previous lexicographic permutation, directly modifying
+  ## ``x``.  The result is whether a permutation happened, otherwise we have
+  ## reached the first-ordered permutation.
+  ##
+  ## .. code-block:: nim
+  ##
+  ##     var v = @[0, 1, 2, 3, 4, 5, 6, 7, 9, 8]
+  ##     v.prevPermutation()
+  ##     echo v
+  if x.len < 2:
+    return false
+
+  var i = x.high
+  while i > 0 and x[i-1] <= x[i]:
+    dec i
+
+  if i == 0:
+    return false
+
+  x.reverse(i, x.high)
+
+  var j = x.high
+  while j >= i and x[j-1] < x[i-1]:
+    dec j
+
+  swap x[i-1], x[j]
+
+  result = true