Over a million developers have joined DZone.
{{announcement.body}}
{{announcement.title}}

Permutations Computer

DZone's Guide to

Permutations Computer

·
Free Resource
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 =="

Topics:

Opinions expressed by DZone contributors are their own.

THE DZONE NEWSLETTER

Dev Resources & Solutions Straight to Your Inbox

Thanks for subscribing!

Awesome! Check your inbox to verify your email so you can start receiving the latest in tech news and resources.

X

{{ parent.title || parent.header.title}}

{{ parent.tldr }}

{{ parent.urlSource.name }}