Permutations: Difference between revisions
→{{header|Logtalk}}
Line 3,963:
321
</pre>
=={{header|Lobster}}==
<lang Lobster>
// 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(_)
</lang>
{{out}}
<pre>
Iterative lexicographical permuter
[0, 1, 2, 3]
[0, 1, 3, 2]
[0, 2, 1, 3]
[0, 2, 3, 1]
[0, 3, 1, 2]
[0, 3, 2, 1]
[1, 0, 2, 3]
[1, 0, 3, 2]
[1, 2, 0, 3]
[1, 2, 3, 0]
[1, 3, 0, 2]
[1, 3, 2, 0]
[2, 0, 1, 3]
[2, 0, 3, 1]
[2, 1, 0, 3]
[2, 1, 3, 0]
[2, 3, 0, 1]
[2, 3, 1, 0]
[3, 0, 1, 2]
[3, 0, 2, 1]
[3, 1, 0, 2]
[3, 1, 2, 0]
[3, 2, 0, 1]
[3, 2, 1, 0]
Recursive plain changes iterator
[0, 1, 2, 3]
[0, 1, 3, 2]
[0, 3, 1, 2]
[3, 0, 1, 2]
[0, 2, 1, 3]
[0, 2, 3, 1]
[0, 3, 2, 1]
[3, 0, 2, 1]
[2, 0, 1, 3]
[2, 0, 3, 1]
[2, 3, 0, 1]
[3, 2, 0, 1]
[1, 0, 2, 3]
[1, 0, 3, 2]
[1, 3, 0, 2]
[3, 1, 0, 2]
[1, 2, 0, 3]
[1, 2, 3, 0]
[1, 3, 2, 0]
[3, 1, 2, 0]
[2, 1, 0, 3]
[2, 1, 3, 0]
[2, 3, 1, 0]
[3, 2, 1, 0]
Recursive Heap's iterator
[0, 1, 2, 3]
[1, 0, 2, 3]
[2, 0, 1, 3]
[0, 2, 1, 3]
[1, 2, 0, 3]
[2, 1, 0, 3]
[3, 1, 0, 2]
[1, 3, 0, 2]
[0, 3, 1, 2]
[3, 0, 1, 2]
[1, 0, 3, 2]
[0, 1, 3, 2]
[0, 2, 3, 1]
[2, 0, 3, 1]
[3, 0, 2, 1]
[0, 3, 2, 1]
[2, 3, 0, 1]
[3, 2, 0, 1]
[3, 2, 1, 0]
[2, 3, 1, 0]
[1, 3, 2, 0]
[3, 1, 2, 0]
[2, 1, 3, 0]
[1, 2, 3, 0]
Iterative Boothroyd iterator
[0, 1, 2, 3]
[1, 0, 2, 3]
[2, 0, 1, 3]
[0, 2, 1, 3]
[1, 2, 0, 3]
[2, 1, 0, 3]
[3, 1, 0, 2]
[1, 3, 0, 2]
[0, 3, 1, 2]
[3, 0, 1, 2]
[1, 0, 3, 2]
[0, 1, 3, 2]
[0, 2, 3, 1]
[2, 0, 3, 1]
[3, 0, 2, 1]
[0, 3, 2, 1]
[2, 3, 0, 1]
[3, 2, 0, 1]
[3, 2, 1, 0]
[2, 3, 1, 0]
[1, 3, 2, 0]
[3, 1, 2, 0]
[2, 1, 3, 0]
[1, 2, 3, 0]
</pre>
=={{header|Logtalk}}==
<lang logtalk>:- object(list).
| |||