Skip to content

Instantly share code, notes, and snippets.

@vysogot vysogot/permset.rb
Created Jul 4, 2011

Embed
What would you like to do?
permute sets with acumulators
def permute(*args)
# initialize the register for each array
# with [array itself, offset, its size]
memory = []
perm_count = 1
args.each do |array|
size = array.size
memory << [array, 0, size-1]
# get the number of all combinations
perm_count *= size
end
# remember the memory size
msize = memory.size
result = []
# for every possible permutation
perm_count.times do |i|
# prepare empty array and bumped flag
permutation = []
bumped = false
# iterate over subsets
msize.times do |j|
# get element with a registered offset
permutation.push(memory[j][0][memory[j][1]])
# if no offset was bumped yet, bump one
unless bumped
# the current one
if memory[j][1] < memory[j][2]
memory[j][1] += 1
bumped = true
else
# or any next possible one that will not overflow yet
# and set the current offset to 0
memory[j][1] = 0
bump_next(memory, j)
bumped = true
end
end
end
# save the permutation to the results array
result << permutation.join
end
result
end
# finiding the one that can be bumped
def bump_next(memory, j)
n = j+1
unless memory[n].nil?
unless full?(memory[n])
memory[n][1] += 1
else
memory[n][1] = 0
bump_next(memory, n)
end
end
end
# check if the offset doesn't overflow
def full?(array)
array[1]==array[2]
end
@vysogot

This comment has been minimized.

Copy link
Owner Author

commented Jul 5, 2011

ruby 1.9.2

        user     system      total        real

10 element 100 arrays 100 times 0.040000 0.000000 0.040000 ( 0.050629)
10 element 100 arrays 1000 times 0.310000 0.000000 0.310000 ( 0.471094)
10 element 100 arrays 10000 times 3.020000 0.020000 3.040000 ( 3.369595)

100 element 100 arrays 100 times 0.080000 0.000000 0.080000 ( 0.112240)
100 element 100 arrays 1000 times 0.820000 0.010000 0.830000 ( 0.866143)
100 element 100 arrays 10000 times 8.190000 0.040000 8.230000 ( 9.561974)

10 element 1000 arrays 100 times 0.310000 0.000000 0.310000 ( 0.469500)
10 element 1000 arrays 1000 times 3.020000 0.040000 3.060000 ( 3.487028)
10 element 1000 arrays 10000 times 29.430000 0.320000 29.750000 ( 31.103277)

100 element 1000 arrays 100 times 0.820000 0.000000 0.820000 ( 0.857183)
100 element 1000 arrays 1000 times 8.080000 0.020000 8.100000 ( 8.342246)
100 element 1000 arrays 10000 times 81.660000 0.440000 82.100000 ( 91.066071)

10 element 10000 arrays 100 times 3.200000 0.050000 3.250000 ( 3.452642)
10 element 10000 arrays 1000 times 32.060000 0.480000 32.540000 ( 36.341177)
10 element 10000 arrays 10000 times320.460000 4.620000 325.080000 (352.346425)

100 element 10000 arrays 100 times 8.270000 0.090000 8.360000 ( 8.599300)
100 element 10000 arrays 1000 times 82.920000 0.890000 83.810000 ( 88.063314)
100 element 10000 arrays 10000 times830.910000 9.180000 840.090000 (896.051414)

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.