DZone Snippets is a public source code repository. Easily build up your personal collection of code snippets, categorize them with tags / keywords, and share them with the world

has posted 3 posts at DZone. View Full User Profile

Permutations Computer

04.13.2011
| 2970 views |
  • submit to reddit
        Permutations 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 =="