ruby enumerators: immediately skip multiple iterations (or start iterating from n)

Question

I'm iterating over permutations of a list (18 items) like this:

List = [item0..item18] # (unpredictable)
Permutation_size = 7
Start_at = 200_000_000

for item, i in List.repeated_permutation(Permutation_size).each_with_index
  next if i < Start_at
  # do stuff
end

Start_at is used to resume from a previously saved state so it's always different but it takes almost 200s to reach 200 million so I'm wondering if there is a faster way to skip multiple iterations or start at iteration n (converting the enumerator to an array takes even longer). If not, a way to create a custom repeated_permutation(n).each_with_index (that yields results in the same order) would also be appreciated.

Feel free to redirect me to an existing answer (I haven't found any)

PS. (what I had come up with)

class Array
  def rep_per_with_index len, start_at = 0
    b = size
    raise 'btl' if b > 36
    counter = [0]*len
    # counter = (start_at.to_s b).split('').map {|i| '0123456789'.include?(i) ? i.to_i : (i.ord - 87)} #this is weird, your way is way faster
    start_at.to_s(b).chars.map {|i| i.to_i b}
    counter.unshift *[0]*(len - counter.length)
    counter.reverse!
    i = start_at
    Enumerator.new do |y|
      loop do
        y << [counter.reverse.map {|i| self[i]}, i]
        i += 1
        counter[0] += 1
        counter.each_with_index do |v, i|
          if v >= b
            if i == len - 1
              raise StopIteration
            else
              counter[i] = 0
              counter[i + 1] += 1
            end
          else
            break
          end
        end
      end
    end
  end
end

Answer 1

I first construct a helper method, change_base, with three arguments:

• off, the base-10 offset into the sequence of repeated permutations of the given array arr,
• m, a number system base; and
• p, the permutation size.

The method performs three steps to construct an array off_m:

• converts off to base m (radix m);
• separates the digits of the base m value into an array; and
• if necessary, pads the array with leading 0s to make it of size p.

By setting m = arr.size, each digit of off_m is an offset into arr, so off_m maps the base-10 offset to a unique permutation of size p.

def change_base(m, p, off)
  arr = off.to_s(m).chars.map { |c| c.to_i(m) }
  arr.unshift(*[0]*(p-arr.size)) 
end

Some examples:

change_base(16, 2, 32)
  #=> [2, 0]
change_base(16, 3, 255)
  #=> [0, 15, 15]
change_base(36, 4, 859243)
  #=> [18, 14, 35, 31]
18*36**3 + 14*36**2 + 35*36**1 + 31  
  #=> 859243

This implementation of change_base requires that m <= 36. I assume that will be sufficient, but algorithms are available to convert base-10 numbers to numbers with arbitrarily-large bases.

We now construct a method which accepts the given array, arr, the size of each permutation, p and a given base-10 offset into the sequence of permutations. The method returns a permutation, namely, an array of size p whose elements are elements of arr.

def offset_to_perm(arr, p, off)
  arr.values_at(*change_base(arr.size, p, off))
end

We can now try this with an example.

arr = (0..3).to_a
p = 2

(arr.size**p).times do |off|
  print "perm for off = "
  print " " if off < 10
  print "#{off}: "
  p offset_to_perm(arr, p, off)
end

perm for off =  0: [0, 0]
perm for off =  1: [0, 1]
perm for off =  2: [0, 2]
perm for off =  3: [0, 3]
perm for off =  4: [0, 1]
perm for off =  5: [1, 1]
perm for off =  6: [2, 1]
perm for off =  7: [3, 1]
perm for off =  8: [0, 2]
perm for off =  9: [1, 2]
perm for off = 10: [2, 2]
perm for off = 11: [3, 2]
perm for off = 12: [0, 3]
perm for off = 13: [1, 3]
perm for off = 14: [2, 3]
perm for off = 15: [3, 3]

If we wish to begin at, say, offset 5, we can write:

i = 5
p offset_to_perm(arr, p, i)
[1, 1]
i = i.next #=> 6
p offset_to_perm(arr, p, i)
[2, 1]
...