Fast! iterative algorithm for generating permutations from sets' single elements

I like it. I like this one. Last algorithm for this problem (here) was O(n^3). Now it's O(n). It may mean two things: first one was very shitty, or that the second one is really good. Probably both are true.

I came back home, without a laptop. With one hand holding the Algorithms book (I really recommend that one) and with notebook and a pen in the other. I choose notebook and pen. It did the trick.

I know I masturbate on that issue, but it's fun. After some furious paper programming I got here:


I asked myself 3 questions at the beginning:

1. How many times "1" will be first?
2. How many times "4" will be in the result?
3. How many times "5" will be in the result?"

I wanted to answer that questions without the use of any offset indexes kept in memory in other array. Keep it simple: what do I know about my input data?
So my answers were like that:

1. If I take all the sizes of following tables and multiply them, I'll get 12.
2. Always, cause it's a single element array, so 36 (total possible permutations.
3. The same as answer number one. 6 times in cycle of 3, 18.

The main conclusion was that I can fill the results array column by column instead of row by row. All permutations will be fully calculated at once, at the very end. No gathering the permutation by permutation and then pushing it to the results. No no no, that needs indexes and traveling across the array many times. This idea dropped the complexity from O(n^3) to O(n).

Cycles, subcycles, offsets. The most important thing was to calculate a proper index in the result table and stick the current argument element exactly there (IBID). No more talk, code is below and benchmark is on the gist comment.

	def permute(*args)
	# filter the arguments
	args.reject! {|x| !x.is_a?(Array) || x.empty?}
	# get the number of all combinations
	total = args.inject(1) {|total, array| total * array.size}
	# prepare the small_cycles array to know how many times
	# one element should be repeated in a loop
	small_cycle = total
	small_cycles = []
	# small cycle depends on the size of arrays are after the current array
	args.each do |array|
	small_cycle = small_cycle/array.size
	# if the array has only one element it should be everywhere
	if array.size == 1
	small_cycles << total
	else
	small_cycles << small_cycle
	end
	end
	# prepare the results table
	result = []
	(args.size).times do |i|
	array_size = args[i].size
	repeat_counter = if (i==0) || (array_size==1) then
	1
	else
	total/(small_cycles[i]*array_size)
	end
	(repeat_counter).times do |j|
	args[i].each_with_index do |element, index|
	(small_cycles[i]).times do |k|
	# calculate an index in the result array
	rindex = (j*small_cycles[i]*array_size)+(index*small_cycles[i])+k
	result[rindex] ||= []
	result[rindex] << element
	end
	end
	end
	end
	result
	end
	# output for: permute([1,2,3], ['X'], [4,5])
	# [[1, "X", 4], [1, "X", 5], [2, "X", 4], [2, "X", 5], [3, "X", 4], [3, "X", 5]]

view raw fast_permute_sets.rb hosted with ❤ by GitHub