Add nextPermutation and prevPermutation

Fits best into algorithm module I guess. These are the most general
ways, an iterator could easily be implemented from this. Same algorithm
as in Rust: http://web.mit.edu/rust-lang_v0.11/doc/src/collections/var/tmp/alexp/rust/rust-0.11.0/src/libcollections/slice.rs.html#644

2 files changed, 76 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
diff --git a/tests/stdlib/tpermutations.nim b/tests/stdlib/tpermutations.nim
new file mode 100644
index 000000000..99bc424cd
--- /dev/null
+++ b/tests/stdlib/tpermutations.nim
@@ -0,0 +1,17 @@
+discard """
+  output: '''@[0, 1, 2, 3, 4, 5, 6, 7, 9, 8]
+@[0, 1, 2, 3, 4, 5, 6, 8, 7, 9]
+@[0, 1, 2, 3, 4, 5, 6, 8, 9, 7]
+@[0, 1, 2, 3, 4, 5, 6, 8, 7, 9]
+@[0, 1, 2, 3, 4, 5, 6, 7, 9, 8]
+@[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]'''
+"""
+import algorithm
+
+var v = @[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
+for i in 1..3:
+  v.nextPermutation()
+  echo v
+for i in 1..3:
+  v.prevPermutation()
+  echo v