133 lines
3.2 KiB
Text
133 lines
3.2 KiB
Text
|
// 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(_)
|