Permutations Computer

Wednesday, 13 April 2011 11:27

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

#



$bigbox = Array.new

$level = -1

$count = 1



def visit(numberArray, arraySize, k)

  $level += 1

  numberArray[k] = $level

  if ($level == arraySize)

    $bigbox.push(numberArray.dup) # we pass the value, not the reference!

    $count += 1

  else

    for i in 0..arraySize-1

      if (numberArray[i] == 0)

        visit(numberArray, arraySize, i)

      end

    end

  end

  $level -= 1

  numberArray[k] = 0

end



puts "Bogolomyn Permutations Computer v.1.0"

N = 4 # Permutation of numbers between 1 and 4

puts "== START COMPUTING PERMUTATIONS =="

numbers = Array.new(N)

for j in 0..N-1

  numbers[j] = 0

end

visit(numbers, N, 0)

puts "== #{$count-1} elements found:"

$bigbox.each do

  |line| puts line.inspect

end

puts "== END =="