Fast, fully iterative permute sets

fast_permute_sets.rb

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]]

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)