Description
The Permutation 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.
Download
The latest version of permutation can be found at
The homepage of this library is located at
Installation
Just type into the command line as root:
# ruby install.rb
Or if you use rubygems just type and rubygems fetches the gem and installs it for you:
# gem install permutation
Creating Documentation
To create the documentation of this module, type either
$ ruby make_doc.rb
or with rake installed
$ rake doc
and the API documentation is generated by your rdoc command in the doc/ sub-directory.
The examples direcotry also contains a small demonstration that solves the Traveling Salesman Problem (TSP) with this library.
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.
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