compute the permutation and combination of a string (or a collection of characters)

per_com.rb

def permutation(data, used=nil, prev='')
    	used = Array.new(data.size) if used == nil

	(0..data.size-1).each do |i|
		result = prev
		if used[i] == false || used[i] == nil 
			used[i] = true
			result += data[i]
			if result.length == data.size 
				puts result
			else 
				permutation(data, used, result)
			end
			used[i] = false
		end
	end
end

def permutation2(data, startIndex = 0 , endIndex = nil)
	endIndex = data.size-1 if endIndex == nil 
	if startIndex == endIndex
		puts data.join('') 
	else 
		(startIndex..endIndex).each do |j|
			data[startIndex], data[j] = data[j], data[startIndex]
			permutation2(data, startIndex+1, endIndex)
			data[startIndex], data[j] = data[j], data[startIndex]
		end
	end
end

# (1+1)^n = C(n,0) + C(n, 1) + ... + C(n, n-1) + C(n, n)
# C(n,0) = 1 corresponds to the empty string
# C(n,n) = 1 corresponds to the original string 
# what the function provides below is all except the empty string
# when n = 3, 2^n - 1 = 8 - 1 = 7
# when n = 5, 2^n - 1 = 32 -1 = 31
def combination(data, start = 0, prev = "")
	(start..data.size-1).each do |i|
		result = prev
		result += data[i]
		puts result
		combination(data, i+1, result)
	end
end

data = ['a', 'b', 'c', 'd', 'e']
permutation(data)
permutation2(data)
combination(data)