permute sets with acumulators

permset.rb

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

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)