133 lines
3.2 KiB
Plaintext
133 lines
3.2 KiB
Plaintext
// Lobster implementation of the (very fast) Go example
|
||
// http://rosettacode.org/wiki/Permutations#Go
|
||
// implementing the plain changes (bell ringers) algorithm, using a recursive function
|
||
// https://en.wikipedia.org/wiki/Steinhaus–Johnson–Trotter_algorithm
|
||
|
||
def permr(s, f):
|
||
if s.length == 0:
|
||
f(s)
|
||
return
|
||
def rc(np: int):
|
||
if np == 1:
|
||
f(s)
|
||
return
|
||
let np1 = np - 1
|
||
let pp = s.length - np1
|
||
rc(np1) // recurs prior swaps
|
||
var i = pp
|
||
while i > 0:
|
||
// swap s[i], s[i-1]
|
||
let t = s[i]
|
||
s[i] = s[i-1]
|
||
s[i-1] = t
|
||
rc(np1) // recurs swap
|
||
i -= 1
|
||
let w = s[0]
|
||
for(pp): s[_] = s[_+1]
|
||
s[pp] = w
|
||
rc(s.length)
|
||
|
||
// Heap's recursive method https://en.wikipedia.org/wiki/Heap%27s_algorithm
|
||
|
||
def permh(s, f):
|
||
def rc(k: int):
|
||
if k <= 1:
|
||
f(s)
|
||
else:
|
||
// Generate permutations with kth unaltered
|
||
// Initially k == length(s)
|
||
rc(k-1)
|
||
// Generate permutations for kth swapped with each k-1 initial
|
||
for(k-1) i:
|
||
// Swap choice dependent on parity of k (even or odd)
|
||
// zero-indexed, the kth is at k-1
|
||
if (k & 1) == 0:
|
||
let t = s[i]
|
||
s[i] = s[k-1]
|
||
s[k-1] = t
|
||
else:
|
||
let t = s[0]
|
||
s[0] = s[k-1]
|
||
s[k-1] = t
|
||
rc(k-1)
|
||
rc(s.length)
|
||
|
||
// iterative Boothroyd method
|
||
|
||
import std
|
||
|
||
def permi(xs, f):
|
||
var d = 1
|
||
let c = map(xs.length): 0
|
||
f(xs)
|
||
while true:
|
||
while d > 1:
|
||
d -= 1
|
||
c[d] = 0
|
||
while c[d] >= d:
|
||
d += 1
|
||
if d >= xs.length:
|
||
return
|
||
let i = if (d & 1) == 1: c[d] else: 0
|
||
let t = xs[i]
|
||
xs[i] = xs[d]
|
||
xs[d] = t
|
||
f(xs)
|
||
c[d] = c[d] + 1
|
||
|
||
// next lexicographical permutation
|
||
// to get all permutations the initial input `a` must be in sorted order
|
||
// returns false when input `a` is in reverse sorted order
|
||
|
||
def next_lex_perm(a):
|
||
def swap(i, j):
|
||
let t = a[i]
|
||
a[i] = a[j]
|
||
a[j] = t
|
||
let n = a.length
|
||
/* 1. Find the largest index k such that a[k] < a[k + 1]. If no such
|
||
index exists, the permutation is the last permutation. */
|
||
var k = n - 1
|
||
while k > 0 and a[k-1] >= a[k]: k--
|
||
if k == 0: return false
|
||
k -= 1
|
||
/* 2. Find the largest index l such that a[k] < a[l]. Since k + 1 is
|
||
such an index, l is well defined */
|
||
var l = n - 1
|
||
while a[l] <= a[k]: l--
|
||
/* 3. Swap a[k] with a[l] */
|
||
swap(k, l)
|
||
/* 4. Reverse the sequence from a[k + 1] to the end */
|
||
k += 1
|
||
l = n - 1
|
||
while l > k:
|
||
swap(k, l)
|
||
l -= 1
|
||
k += 1
|
||
return true
|
||
|
||
var se = [0, 1, 2, 3] //, 4, 5, 6, 7, 8, 9, 10]
|
||
|
||
print "Iterative lexicographical permuter"
|
||
|
||
print se
|
||
while next_lex_perm(se): print se
|
||
|
||
print "Recursive plain changes iterator"
|
||
|
||
se = [0, 1, 2, 3]
|
||
|
||
permr(se): print(_)
|
||
|
||
print "Recursive Heap\'s iterator"
|
||
|
||
se = [0, 1, 2, 3]
|
||
|
||
permh(se): print(_)
|
||
|
||
print "Iterative Boothroyd iterator"
|
||
|
||
se = [0, 1, 2, 3]
|
||
|
||
permi(se): print(_)
|