- #!/usr/bin/env ruby
- # PERMUTATIONS COMPUTER
- # based on Bogomolyn algorithm
- # <a href="http://www.bearcave.com/random_hacks/permute.html">http://www.bearcave.com/random_hacks/permute.html
- # Author: Alessio Saltarin <a href="http://axsaxs.altervista.org/">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 =="
- #该片段来自于http://www.codesnippet.cn/detail/070420132721.html
来源: http://www.codesnippet.cn/detail/070420132721.html