Instantly share code, notes, and snippets.

# vysogot/fast_permute_sets.rb Created Jul 7, 2011

Fast, fully iterative permute sets
 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]]
Owner Author

### vysogot commented Jul 7, 2011

 ruby 1.9.2 user system total real 10 element 100 arrays 100 times 0.010000 0.000000 0.010000 ( 0.009669) 10 element 100 arrays 1000 times 0.090000 0.000000 0.090000 ( 0.101657) 10 element 100 arrays 10000 times 0.870000 0.000000 0.870000 ( 0.935505) 100 element 100 arrays 100 times 0.010000 0.000000 0.010000 ( 0.009122) 100 element 100 arrays 1000 times 0.090000 0.000000 0.090000 ( 0.087561) 100 element 100 arrays 10000 times 0.870000 0.010000 0.880000 ( 0.903019) 10 element 1000 arrays 100 times 0.090000 0.000000 0.090000 ( 0.090390) 10 element 1000 arrays 1000 times 0.870000 0.000000 0.870000 ( 0.898616) 10 element 1000 arrays 10000 times 8.600000 0.040000 8.640000 ( 9.439106) 100 element 1000 arrays 100 times 0.100000 0.000000 0.100000 ( 0.104338) 100 element 1000 arrays 1000 times 0.880000 0.000000 0.880000 ( 0.892480) 100 element 1000 arrays 10000 times 8.710000 0.040000 8.750000 ( 9.205378) 10 element 10000 arrays 100 times 0.810000 0.000000 0.810000 ( 0.869141) 10 element 10000 arrays 1000 times 8.290000 0.070000 8.360000 ( 9.166838) 10 element 10000 arrays 10000 times 82.290000 0.370000 82.660000 ( 88.191194) 100 element 10000 arrays 100 times 0.830000 0.000000 0.830000 ( 0.829901) 100 element 10000 arrays 1000 times 8.470000 0.040000 8.510000 ( 9.386524) 100 element 10000 arrays 10000 times 84.370000 0.330000 84.700000 ( 88.605024)