红宝石枚举：立即跳过多次迭代（或者开始从n个迭代）

Question

我遍历列表的排列（18项）是这样的：

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用于从先前保存的状态恢复所以它总是不同的，但它几乎需要200s达到2亿，所以我想知道是否有更快的方法来跳过多个迭代或从迭代n开始（将枚举数转换为数组需要更长的时间）。如果不是的话，也会赞赏一种创建自定义repeated_permutation(n).each_with_index（即以相同顺序产生结果）的方法。

随时给我重定向到一个现有的答案（我还没有发现任何）

PS。 （我所想出）

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| ''.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

我首先构造一个辅助方法，change_base，具有三个参数：

• off，基部10偏移到给定的重复排列的序列数组arr,
• m，一个数字系统基础;和
• p，排列大小。

该方法执行三个步骤来构造一个数组off_m：

• 转换off到基座m（基数m）;
• 将基数m值的数字分隔为一个数组;和
• 如有必要，用领导0 s填充阵列使其大小为p。

通过设置m = arr.size，的off_m每个数字的偏移量arr，所以off_m映射10为底的偏移大小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 

一些例子：

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 

的change_base此实现需要m <= 36。我认为这足够了，但算法可以将基数为10的数字转换为任意大的基数。

我们现在构建一个方法，它接受给定数组，arr，每个排列的大小，p和给定的基数为10的偏移到排列序列中。该方法返回一个置换，即一个大小为p的数组，其元素是arr的元素。

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

我们现在可以试试这个例子。

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] 

如果我们想在开始，也就是说，偏移5，我们可以这样写：

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