Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
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]]
@vysogot

This comment has been minimized.

Copy link
Owner Author

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)

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.