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.
For permutation, it's already available in algorithm lib.
It just simply do permutation on entire seq/array in place though.
Great, thanks.
Your "iterator combinations" is exactly what I need currently. I was already thinking about a similar non recursive solution to get a real iterator, but it would have been not easy for me to get it really working myself.
Here's a an iterator to generate combinations.
iterator choose*[T](a: openarray[T], num_choose: int): seq[T] =
var
chosen: seq[T]
i = 0
i_stack = newSeqOfCap[int](num_choose)
while true:
if chosen.len == num_choose:
yield chosen
discard chosen.pop()
i = i_stack.pop() + 1
elif i != a.len:
chosen.add(a[i])
i_stack.add(i)
inc i
elif i_stack.len > 0:
discard chosen.pop()
i = i_stack.pop() + 1
else:
break
Example use:
for choice in choose(@[11, 22, 33, 44, 55, 66], 3):
echo choice
Outputs:
@[11, 22, 33]
@[11, 22, 44]
@[11, 22, 55]
@[11, 22, 66]
@[11, 33, 44]
@[11, 33, 55]
@[11, 33, 66]
@[11, 44, 55]
@[11, 44, 66]
@[11, 55, 66]
@[22, 33, 44]
@[22, 33, 55]
@[22, 33, 66]
@[22, 44, 55]
@[22, 44, 66]
@[22, 55, 66]
@[33, 44, 55]
@[33, 44, 66]
@[33, 55, 66]
@[44, 55, 66]