4/6/15 - Permutations in Ruby

I rewrote my ruby permutations algorithm to use yield instead of return. This is a lazy algorithm: rather than generating all permutations at once, it generates them as they are needed. So the line permutations(%w[a b c d]).first(5) only generates the first 5 permutations of the array. Here is the implementation:

	def permutations_lazy(list)
	# recursion's base case: return, not yield (outside of enumerator)
	return [list] if list.size == 1
	en = Enumerator.new do |y|
	list.each do |locked|
	puts "locking #{locked}"
	list_copy = list.dup
	list_copy.delete locked
	permutations_lazy(list_copy).each do |permutation|
	puts "permutation #{permutation}, locked #{locked}"
	y.yield permutation.insert(0, locked)
	end
	end
	end
	en
	end
	if __FILE__ == $0
	pl = permutations_lazy %w[a b c d]
	pl.first(5).each {|i| p i} # in case you're not familiar with ruby, the p keyword prints the output of an object's #inspect method
	end

view raw permutations_lazy1.rb hosted with ❤ by GitHub

	Output:
	["a", "b", "c", "d"]
	["a", "b", "d", "c"]
	["a", "c", "b", "d"]
	["a", "c", "d", "b"]
	["a", "d", "b", "c"]

view raw ~output.txt hosted with ❤ by GitHub

As it turns out, this function is already built into ruby! This statement does the exact same thing.

%w[a b c d].permutation.first(5).each {|i| p i} #=> same output as permutations_lazy1.rb

view raw permutations_lazy4.rb hosted with ❤ by GitHub