Permutations Computer
Join the DZone community and get the full member experience.
Join For FreePermutations counter. Enter N=x where x is the permutation size
ie: N=4 gives all the permutations of numbers between 1 and 4
#!/usr/bin/env ruby
# PERMUTATIONS COMPUTER
# based on Bogomolyn algorithm
# http://www.bearcave.com/random_hacks/permute.html
# Author: Alessio Saltarin http://axsaxs.altervista.org/
class PermutationComputer
attr_reader :bigbox # Array of permutations
attr_reader :count # Number of elements found
def initialize(size)
@permutationSize = size
@bigbox = Array.new
@level = -1
@count = 1
@numbers = Array.new(@permutationSize)
(@permutationSize-1).downto(0) { |j| @numbers[j] = 0}
end
def compute()
visit(@numbers, 0)
@count -= 1
end
def visit(numberArray, k)
@level += 1
numberArray[k] = @level
if (@level == @permutationSize)
@bigbox << numberArray.dup # we pass the value, not the reference!
@count += 1
else
0.upto(@permutationSize - 1) do |i|
if (numberArray[i] == 0)
visit(numberArray, i)
end
end
end
@level -= 1
numberArray[k] = 0
end
end
puts "Bogolomyn Permutations Computer v.1.0"
# Permutations of numbers between 1 and 4
permutations = PermutationComputer.new(4)
puts "== START COMPUTING PERMUTATIONS =="
permutations.compute
puts "== #{permutations.count} elements found:"
permutations.bigbox.each do
|line| puts line.inspect
end
puts "== END =="
Computer
Opinions expressed by DZone contributors are their own.
Comments