Ruby:如何设置枚举器的状态？

Question

我正在做一个基于 64 的排列增量器。我已经编写了所有工作代码。但看看 Ruby 已经作为 Array::permutation 生成了一个枚举器；我想利用它并更进一步。

无需使用“next”完成每个排列，我可以设置起点吗？

x = ('A'..'Z').to_a + ('a'..'z').to_a + ('0'..'9').to_a + ['+','/']
y = x.permutation(12)
y.peek.join
=> "ABCDEFGHIJKL"
y.next
y.peek.join
=> "ABCDEFGHIJKM"

。 # 做这样的事情

y.set_current_enumerator_state_to("ABCDEFGHIJK/".split(""))

。 # 并按如下方式拾取

y.peek.join
=> "ABCDEFGHIJK/"
y.next
y.peek.join
=> "ABCDEFGHIJLK"

能够设置枚举器继续的状态将简单地解决所有问题。我为此创建了一个高尔夫挑战。将所有代码写出来后，我无法得到少于 600 多个字符的代码。但是，如果我可以设置枚举器将从中开始的状态，我可以轻松地用接近 100 个或更少的代码字符来完成它。

我真的只是尽我最大的努力去了解 Ruby 及其核心的一些深层 secret 。

如果您对代码感兴趣，这是我所做的高尔夫挑战:http://6ftdan.com/2014/05/03/golf-challenge-unique-base-64-incrementor/

Answer 1

结果

对于您的示例，

x = ('A'..'Z').to_a + ('a'..'z').to_a + ('0'..'9').to_a + ['+','/']

start = "ABCDEFGHIJK/".split("")

以下内容是通过枚举器 head_start_permutation 获得的我构建如下:

y = x.head_start_permutation(start)
  #=> #<Enumerator: #<Enumerator::Generator:0x000001011e62f0>:each>
y.peek.join(' ') #=>  "A B C D E F G H I J K /"
y.next.join(' ') #=>  "A B C D E F G H I J K /"
y.next.join(' ') #=>  "A B C D E F G H I J L K"
y.next.join(' ') #=>  "A B C D E F G H I J L M"
y.take(3).map { |a| a.join(' ') }
                 #=> ["A B C D E F G H I J L M",
                 #    "A B C D E F G H I J L N",
                 #    "A B C D E F G H I J L O"]

第二个next是最有趣的。如'A'和'/'是 x 的第一个和最后一个元素， 'K/' 之后序列中的下一个元素将是'LA'但自从 'A'已经出现在排列中，'LB'因同样的原因尝试并被拒绝，依此类推，直到 'LK'已接受。

另一个例子:

start = x.sample(12)
  # => ["o", "U", "x", "C", "D", "7", "3", "m", "N", "0", "p", "t"]
y = x.head_start_permutation(start)

y.take(10).map { |a| a.join(' ') }
  #=> ["o U x C D 7 3 m N 0 p t",
  #    "o U x C D 7 3 m N 0 p u",
  #    "o U x C D 7 3 m N 0 p v",
  #    "o U x C D 7 3 m N 0 p w",
  #    "o U x C D 7 3 m N 0 p y",
  #    "o U x C D 7 3 m N 0 p z",
  #    "o U x C D 7 3 m N 0 p 1",
  #    "o U x C D 7 3 m N 0 p 2",
  #    "o U x C D 7 3 m N 0 p 4",
  #    "o U x C D 7 3 m N 0 p 5"]

请注意 'x'和'3'作为每个数组中的最后一个元素被跳过，因为排列的其余部分包含这些元素。

排列顺序

在考虑如何有效处理你的问题之前，我们必须考虑排列顺序的问题。由于您希望以特定排列开始枚举，因此有必要确定哪些排列在前，哪些排列在后。

我假设您想使用lexicographical ordering数组的偏移量(如下所述)，这就是 Ruby 使用的 Array#permuation , Array#combinaton等等。这是“字典”单词排序的概括。

举例来说，假设我们想要以下元素的所有排列:

arr = [:a,:b,:c,:d]

一次拍摄三个。这是:

arr_permutations = arr.permutation(3).to_a
  #=> [[:a,:b,:c], [:a,:b,:d], [:a,:c,:b], [:a,:c,:d], [:a,:d,:b], [:a,:d,:c],
  #=>  [:b,:a,:c], [:b,:a,:d], [:b,:c,:a], [:b,:c,:d], [:b,:d,:a], [:b,:d,:c],
  #=>  [:c,:a,:b], [:c,:a,:d], [:c,:b,:a], [:c,:b,:d], [:c,:d,:a], [:c,:d,:b],
  #=>  [:d,:a,:b], [:d,:a,:c], [:d,:b,:a], [:d,:b,:c], [:d,:c,:a], [:d,:c,:b]]

如果我们替换 arr 的元素以及他们的立场:

pos = [0,1,2,3]

我们看到:

pos_permutations = pos.permutation(3).to_a
  #=> [[0, 1, 2], [0, 1, 3], [0, 2, 1], [0, 2, 3], [0, 3, 1], [0, 3, 2],  
  #    [1, 0, 2], [1, 0, 3], [1, 2, 0], [1, 2, 3], [1, 3, 0], [1, 3, 2],
  #    [2, 0, 1], [2, 0, 3], [2, 1, 0], [2, 1, 3], [2, 3, 0], [2, 3, 1],
  #    [3, 0, 1], [3, 0, 2], [3, 1, 0], [3, 1, 2], [3, 2, 0], [3, 2, 1]]

如果您将这些数组中的每一个视为以 4 为基数的三位数 ( arr.size )，您可以看到我们在这里只是从零到最大的数 333，跳过那些具有共同数字的数字。这是 Ruby 使用的顺序，我也将使用该顺序。

请注意:

pos_permutations.map { |p| arr.values_at(*p) } == arr_permutations #=> true

这表明一旦我们有 pos_permutations ，我们可以将其应用于任何需要排列的数组。

简单的领先枚举器

假设数组 arr上面我们想要一个枚举器，一次排列所有元素三个，第一个是 [:c,:a,:d] 。我们可以按如下方式获取该枚举器:

temp = arr.permutation(3).to_a
ndx = temp.index([:c,:a,:d]) #=> 13
temp = temp[13..-1]
  #=>[              [:c,:a,:d], [:c,:b,:a], [:c,:b,:d], [:c,:d,:a], [:c,:d,:b],
  #   [:d, :a, :b], [:d,:a,:c], [:d,:b,:a], [:d,:b,:c], [:d,:c,:a], [:d,:c,:b]]
enum = temp.to_enum
  #=> #<Enumerator: [[:c, :a, :d], [:c, :b, :a],...[:d, :c, :b]]:each>
enum.map { |a| a.map(&:to_s).join }
  #=> [       "cad", "cba", "cbd", "cda", "cdb",
  #    "dab", "dac", "dba", "dbc", "dca", "dcb"]

但是等一下!如果我们只想使用这个枚举器一次，这很难节省时间。将完整的枚举器转换为数组、砍掉开头并将剩下的内容转换为枚举器的投资enum如果我们打算使用 enum 可能有意义(但不适用于您的示例)多次(即始终具有相同的枚举起点)，这当然是可能的。

滚动你自己的枚举器

上面第一部分的讨论表明构建一个枚举器

head_start_permutation(start)

也许并没有那么困难。第一步是创建一个 next偏移量数组的方法。这是一种可行的方法:

class NextUniq
  def initialize(offsets, base)
    @curr = offsets
    @base = base
    @max_val = [base-1] * offsets.size
  end

  def next
    loop do
      return nil if @curr == @max_val 
      rruc = @curr.reverse
      ndx = rruc.index { |e| e < @base - 1 }
      if ndx
        ndx = @curr.size-1-ndx
        @curr = @curr.map.with_index do |e,i|
          case i <=> ndx
          when -1 then e
          when  0 then e+1
          when  1 then 0
          end
        end
      else
        @curr = [1] + ([0] * @curr.size)
      end
      (return @curr) if (@curr == @curr.uniq) 
    end  
  end  
end

我选择的特定实现并不是特别有效，但它确实达到了目的:

nxt = NextUniq.new([0,1,2], 4)
nxt.next #=> [0, 1, 3]
nxt.next #=> [0, 2, 1]
nxt.next #=> [0, 2, 3]
nxt.next #=> [0, 3, 1]
nxt.next #=> [0, 3, 2]
nxt.next #=> [1, 0, 2]

注意它是如何跳过包含重复项的数组的。

接下来，我们构造枚举器方法。我选择通过对类进行猴子修补来实现此目的 Array ，但也可以采取其他方法:

class Array
  def head_start_permutation(start)
    # convert the array start to an array of offsets
    offsets = start.map { |e| index(e) } 
    # create the instance of NextUtil
    nxt = NextUniq.new(offsets, size)
    # build the enumerator  
    Enumerator.new do |e|
      loop do
        e << values_at(*offsets)
        offsets = nxt.next
        (raise StopIteration) unless offsets
      end
    end
  end  
end

让我们尝试一下:

arr   = [:a,:b,:c,:d]
start = [:c,:a,:d]

arr.head_start_permutation(start).map { |a| a.map(&:to_s).join }
  #=> [       "cad", "cba", "cbd", "cda", "cdb",
  #    "dab", "dac", "dba", "dbc", "dca", "dcb"]

请注意，构造枚举器会更容易

head_start_repeated_permutation(start)

唯一的区别是 NextUniq#next我们不会跳过有重复的候选人。