In Ruby we have permutations and combinations procs for arrays, and variants
with repetition.
I have not found too much of this for Nim yet, so I tried myself:
# https://ruby-doc.org/core-2.4.0/Array.html#method-i-repeated_combination
# https://rosettacode.org/wiki/Combinations
#
http://stackoverflow.com/questions/127704/algorithm-to-return-all-combinations-of-k-elements-from-n
proc repeatedPermutations[T](a: openarray[T], n: int): seq[seq[T]] =
result = newSeq[seq[T]]()
if n <= 0: return
for i in 0 .. a.high:
if n == 1:
result.add(@[a[i]])
else:
for j in repeatedPermutations(a, n - 1):
result.add(a[i] & j)
proc perm[T](a: openarray[T], n: int, use: var seq[bool]): seq[seq[T]] =
result = newSeq[seq[T]]()
if n <= 0: return
for i in 0 .. a.high:
if not use[i]:
if n == 1:
result.add(@[a[i]])
else:
use[i] = true
for j in perm(a, n - 1, use):
result.add(a[i] & j)
use[i] = false
proc permutations[T](a: openarray[T], n: int): seq[seq[T]] =
var use = newSeq[bool](a.len)
perm(a, n, use)
proc comb[T](a: openarray[T]; n: int; use: seq[bool]): seq[seq[T]] =
result = newSeq[seq[T]]()
var use = use
if n <= 0: return
for i in 0 .. a.high:
if not use[i]:
if n == 1:
result.add(@[a[i]])
else:
use[i] = true
for j in comb(a, n - 1, use):
result.add(a[i] & j)
proc combinations[T](a: openarray[T], n: int): seq[seq[T]] =
var use = newSeq[bool](a.len)
comb(a, n, use)
proc rcomb[T](a: openarray[T]; n: int; use: seq[bool]): seq[seq[T]] =
result = newSeq[seq[T]]()
var use = use
if n <= 0: return
for i in 0 .. a.high:
if not use[i]:
if n == 1:
result.add(@[a[i]])
else:
for j in rcomb(a, n - 1, use):
result.add(a[i] & j)
use[i] = true
proc repeatedCombinations[T](a: openarray[T], n: int): seq[seq[T]] =
var use = newSeq[bool](a.len)
rcomb(a, n, use)
# now we try to make an iterator
iterator repeatedPermutation[T](a: openarray[T], n: int): seq[T] =
for i in 0 .. a.high:
if n == 1:
yield @[a[i]]
else:
for j in repeatedPermutations(a, n - 1):
for k in j:
yield @[a[i]] & k
when isMainModule:
let ar = [1, 2, 3, 4]
let ll = 2
echo "Permutations"
echo permutations(ar, ll)
echo "repeated Permutations"
echo repeatedPermutations(ar, ll)
echo "repeated Combinations"
echo repeatedCombinations(ar, ll)
echo "combinations"
echo combinations(ar, ll)
let arr = ['A', 'B', 'C', 'D']
echo "Permutations"
echo permutations(arr, ll)
echo "repeated Permutations"
echo repeatedPermutations(arr, ll)
echo "repeated Combinations"
echo repeatedCombinations(arr, ll)
echo "combinations"
echo combinations(arr, ll)
echo "repeated Permutation Iterator"
for i in repeatedPermutation(ar, ll): echo i
$ ./fun | sed 's/@//g'
Permutations
[[1, 2], [1, 3], [1, 4], [2, 1], [2, 3], [2, 4], [3, 1], [3, 2], [3, 4],
[4, 1], [4, 2], [4, 3]]
repeated Permutations
[[1, 1], [1, 2], [1, 3], [1, 4], [2, 1], [2, 2], [2, 3], [2, 4], [3, 1],
[3, 2], [3, 3], [3, 4], [4, 1], [4, 2], [4, 3], [4, 4]]
repeated Combinations
[[1, 1], [1, 2], [1, 3], [1, 4], [2, 2], [2, 3], [2, 4], [3, 3], [3, 4],
[4, 4]]
combinations
[[1, 2], [1, 3], [1, 4], [2, 3], [2, 4], [3, 4]]
Permutations
[[A, B], [A, C], [A, D], [B, A], [B, C], [B, D], [C, A], [C, B], [C, D],
[D, A], [D, B], [D, C]]
repeated Permutations
[[A, A], [A, B], [A, C], [A, D], [B, A], [B, B], [B, C], [B, D], [C, A],
[C, B], [C, C], [C, D], [D, A], [D, B], [D, C], [D, D]]
repeated Combinations
[[A, A], [A, B], [A, C], [A, D], [B, B], [B, C], [B, D], [C, C], [C, D],
[D, D]]
combinations
[[A, B], [A, C], [A, D], [B, C], [B, D], [C, D]]
repeated Permutation Iterator
[1, 1]
[1, 2]
[1, 3]
[1, 4]
[2, 1]
[2, 2]
[2, 3]
[2, 4]
[3, 1]
[3, 2]
[3, 3]
[3, 4]
[4, 1]
[4, 2]
[4, 3]
[4, 4]
Output seems to be identical to Ruby results.
First question: Is all that already available somewhere?
Next: Is it a stupid solution?
And last: How to convert that to iterators? I have managed that somehow for the
simplest case, but the iterator calls the proc with same name. And for the
other procs it is more difficult because each exported proc calls a local child.
