Building all permutations of something is a typical recursive task.
But in this case I dont want a recursive solution because:
There's a non-recursive permutation algorithm at:
Here is an implementation I once made:
class Array
def swap!(idx1, idx2)
if (idx1.abs > self.length || idx2.abs > self.length )
raise ArgumentError.new("non valid indices!")
end
a = self[idx1]
self[idx1] = self[idx2]
self[idx2] = a
self
end
end
# algorithm by: Yahoo | Mail, Weather, Search, Politics, News, Finance, Sports & Videos
class Permutations
def initialize(ary)
if (not ary.kind_of?(Array) or ary.empty?)
raise ArgumentError.new("ary should be a non-empty Array!")
end
@ary = ary.sort
@n = ary.length
@pary = (0..@n+1).to_a
@i = 1
@first = true
end
attr_reader :ary, :i
def next
if not @first
raise StandardError, "Permutations Exhausted!" if @i >= @n
@pary[i] -= 1
j = (i%2 == 0 ? 0 : @pary[i]) # if i is odd, then let j =
p[i] otherwise let j = 0
@ary.swap!(i, j)
@i = 1
while (@pary[i] == 0)
@pary[i] = @i
@i += 1
end # end while (p[i] is equal to 0)
else
@first = false
end
if block_given?
yield ary
end
ary
end
def hasNext?
@i < @n
end
def reset
@ary = ary.sort
@n = ary.length
@pary = (0..n+1).to_a
@i = 1
end
def Permutations.go(array)
if ( not array.kind_of?(Array) or array.empty?)
raise ArgumentError.new("ary should be a non-empty Array!")
end
ary = array.sort
n = ary.length
pary = (0..n+1).to_a
i = 1
while (i < n)
yield ary
pary[i] -= 1
j = (i%2 == 0 ? 0 : pary[i]) # if i is odd, then let j =
p[i] otherwise let j = 0
ary.swap!(i, j)
i = 1
while (pary[i] == 0)
pary[i] = i
i += 1
end # end while (p[i] is equal to 0)
end # end while (i < N)
yield ary
end
end