permutation.rb - Permutation class for Ruby
Author
Florian Frank flori@ping.de
License
This is free software; you can redistribute it and/or modify it under the terms of the GNU General Public License Version 2 as published by the Free Software Foundation: www.gnu.org/copyleft/gpl.html
Download
The latest version of permutation can be found at
The homepage of this library is located at
Description
This class has a dual purpose: It can be used to create permutations of a given size and to do some simple computations with/on permutations. The instances of this class don’t require much memory because they don’t include the permutation as a data structure. They only save the information necessary to create the permutation if asked to do so.
To generate permutations the ranking/unranking method described in [SS97] is used. Because of Ruby’s Bignum arithmetic it is useful also for permutations of very large size.
Examples
In this section some examples show what can be done with this class.
Creating all permutations and project them on data:
perm = Permutation.new(3)
# => #<Permutation:0x57dc94 @last=5, @rank=0, @size=3>
perm.map { |p| p.value }
# => [[0, 1, 2], [0, 2, 1], [1, 0, 2], [1, 2, 0], [2, 0, 1], [2, 1, 0]]
colors = [:r, :g, :b]
# => [:r, :g, :b]
perm.map { |p| p.project(colors) }
# => [[:r, :g, :b], [:r, :b, :g], [:g, :r, :b], [:g, :b, :r], [:b, :r, :g],
# [:b, :g, :r]]
string = "abc"# => "abc"
perm.map { |p| p.project(string) }
# => ["abc", "acb", "bac", "bca", "cab", "cba"]
Or perhaps more convenient to use:
perm = Permutation.for("abc")
perm.map { |p| p.project }
# => ["abc", "acb", "bac", "bca", "cab", "cba"]
Finding the successor and predecessor of Permutations or a certain Permutation for a given rank:
perm = Permutation.new(7) # => #<Permutation:0x8453c @rank=0, @size=7, @last=5039> perm.succ! # => #<Permutation:0x8453c @rank=1, @size=7, @last=5039> perm.succ! # => #<Permutation:0x8453c @rank=2, @size=7, @last=5039> perm.succ! # => #<Permutation:0x8453c @rank=3, @size=7, @last=5039> perm.pred! # => #<Permutation:0x8453c @rank=2, @size=7, @last=5039> perm.rank = 3200 # => 3200 perm # => #<Permutation:0x8453c @rank=3200, @size=7, @last=5039> perm.value # => [4, 2, 5, 1, 3, 0, 6]
Generating random Permutations
perm = Permutation.new(10)
# => #<Permutation:0x59f4c0 @rank=0, @size=10, @last=3628799>
perm.random!.value
# => [6, 4, 9, 7, 3, 5, 8, 1, 2, 0]
perm.random!.value
# => [3, 7, 6, 1, 4, 8, 9, 2, 5, 0]
perm.random!.value
# => [2, 8, 4, 9, 3, 5, 6, 7, 0, 1]
perm.random!.project("ABCDEFGHIJ")
# => "DFJGAEBCIH"
perm.random!.project("ABCDEFGHIJ")
# => "BFADEGHJCI"
Performing some mathematical operations on/with Permutations
p1 = Permutation.from_cycles([[1, 3, 2], [5, 7]], 10) # => #<Permutation:0x593594 @rank=80694, @size=10, @last=3628799> p2 = Permutation.from_value [3, 2, 0, 5, 6, 8, 9, 1, 4, 7] # => #<Permutation:0x5897b0 @rank=1171050, @size=10, @last=3628799> p3 = p1 * p2 # => #<Permutation:0x586a88 @rank=769410, @size=10, @last=3628799> p3.value # => [2, 1, 0, 7, 6, 8, 9, 3, 4, 5] p3.cycles # => [[0, 2], [3, 7], [4, 6, 9, 5, 8]] p4 = p1 * -p2 # => #<Permutation:0x581a10 @rank=534725, @size=10, @last=3628799> p4.value # => [1, 5, 3, 0, 8, 2, 4, 9, 7, 6] p4.cycles # => [[0, 1, 5, 2, 3], [4, 8, 7, 9, 6]] id = p1 * -p1 # => #<Permutation:0x583a7c @rank=0, @size=10, @last=3628799>
References
[SS97] The Algorithm Design Manual, Steven S. Skiena, Telos/Springer, 1997.