ruby枚举器：立即跳过多次迭代(或从n开始迭代)

a8jjtwal 于 2023-05-28 发布在 Ruby

关注(0)|答案(1)|浏览(102)

我正在迭代一个列表（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| '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

ruby

来源：https://stackoverflow.com/questions/44789583/ruby-enumerators-immediately-skip-multiple-iterations-or-start-iterating-from

1条答案

按热度按时间

yb3bgrhw1#

我首先构造了一个helper方法change_base，它有三个参数：

off，到给定数组arr的重复排列序列中的以10为基数的偏移，
m，数字系统基;和
p，置换大小。

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

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

通过设置m = arr.size，off_m的每个数字都是arr的偏移量，因此off_m将基数为10的偏移量Map到大小为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]
...

赞(0）回复(0）举报 2023-05-28

我来回答

ruby枚举器：立即跳过多次迭代(或从n开始迭代)

1条答案

相关问题

热门标签

最新问答