Ruby:如何设置枚举器的状态? [英] Ruby: How do you set an Enumerator's state?

问题描述

我正在做一个基数为64的排列增量器.我已经写了所有的工作代码.但是，就像Ruby那样，它已经像Array :: permutation这样产生了一个Enumerator；我想使用它，并将它更进一步.

I'm doing a base 64 permutation incrementor. I've already written all the working code. But seeing as how Ruby already as Array::permutation which produces an Enumerator; I'd like to use that and take it a step further.

无需使用'next'进行所有排列，我可以设置起点吗?

Without having to go through every permutation by using 'next', can I set the start point?

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(""))

. #并按照以下步骤领取

. # AND PICK UP AS FOLLOWS

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

能够设置枚举器将继续运行的状态将解决所有问题.为此，我提出了高尔夫挑战赛.把所有代码写出来，我不能少于600个字符以上的代码.但是，如果我可以设置枚举器从其开始的状态，则可以很容易地在大约100个或更少的代码字符中进行操作.

Being able to set the state at which the Enumerator will continue would solve everything in simplicity. I created a Golf challenge for this. Writing all the code out I couldn't get it to less than 600+ characters of code. But if I can set the state from which Enumerator will proceed from I could easily do it in closer to around 100, or less, characters of code.

我真的是在尽我最大的努力来学习Ruby及其核心的一些深层黑暗秘密.

I'm really just doing my best to learn some of the deep dark secret's of Ruby and it's core.

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

Here's the golf challenge I did if you're interested in the code: http://6ftdan.com/2014/05/03/golf-challenge-unique-base-64-incrementor/

推荐答案

结果

例如，

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

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

以下是通过我在下面构造的枚举器head_start_permutation获得的:

the following is obtained with the enumerator head_start_permutation I've constructed below:

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

The second next is the most interesting. As 'A' and '/' are the first and last elements of x, the next element in sequence after 'K/' would be 'LA' but since 'A' already appears in the permutations, 'LB' is tried and rejected for the same reason, and so on, until 'LK' is accepted.

另一个例子:

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'被跳过了，成为每个数组中的最后一个元素，因为排列的其余部分包含这些元素.

Notice that 'x' and '3'were skipped over as the last element in each of the arrays, because the remainder of the permutation contains those elements.

排列顺序

在考虑如何有效处理您的问题之前，我们必须考虑排列顺序的问题.当您希望以特定排列开始枚举时，有必要确定哪些排列在前面，哪些在后面.

Before considering how to effectively deal with your problem, we must consider with the issue of the order of the permutations. As you wish to begin the enumeration at a particular permutation, it is necessary to determine which permutations come before and which come after.

我假设您要使用词典编排顺序通过数组的偏移量元素(如下所述)，这就是Ruby用于阵列#combinaton 等.这是单词字典"排序的概括.

I will assume that you want to use a lexicographical ordering of arrays by the offsets of array elements (as elaborated below), which is what Ruby uses for Array#permuation, Array#combinaton and so forth. This is a generalization of "dictionary" ordering of words.

通过示例，假设我们希望对以下元素进行所有排列:

By way of example, suppose we want all permutations of the elements of:

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的元素替换为它们的位置:

If we replace the elements of arr with their positions:

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使用的顺序，也是我将使用的顺序.

If you think of each of these arrays as a three-digit number in base 4 (arr.size), you can see we are here merely counting them from zero to the largest, 333, skipping over those with common digits. This is the ordering that Ruby uses and the one I will use as well.

请注意:

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

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

which shows that once we have pos_permutations, we can apply it to any array for which permutations are needed.

简单的枚举枚举

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

Suppose for the array arr above we want an enumerator that permutes all elements three at a time, with the first being [:c,:a,:d]. We can obtain that enumerator as follows:

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(即始终使用相同的枚举起点)，这当然是可能的.

But wait a minute! This is hardly a time-saver if we wish to use this enumerator only once. The investment in converting the full enumerator to an array, chopping off the beginning and converting what's left to the enumerator enum might make sense (but not for your example) if we intended to use enum multiple times (i.e., always with the same enumeration starting point), which of course is a possibility.

滚动您自己的枚举器

上面第一部分的讨论建议构造一个枚举器

The discussion in the first section above suggests that constructing an enumerator

head_start_permutation(start)

可能并不那么困难.第一步是为偏移数组创建一个next方法.这是可以完成的一种方法:

may not be all that difficult. The first step is to create a next method for the array of offsets. Here's one way that could be done:

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

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

The particular implementation I have chosen is not particularly efficient, but it does achieve its purpose:

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]

请注意，这是如何跳过包含重复项的数组的.

Notice how this has skipped over arrays containing duplicates.

接下来，我们构造枚举器方法.我选择通过猴子修补类Array来做到这一点，但是可以采用其他方法:

Next, we construct the enumerator method. I've chosen to do this by monkey-patching the class Array, but other approaches could be taken:

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"]

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

Note that it would be even easier to construct an enumerator

head_start_repeated_permutation(start)

唯一的区别是，在NextUniq#next中，我们不会跳过具有重复项的候选者.

The only difference is that in NextUniq#next we would not skip over candidates having duplicates.

这篇关于Ruby:如何设置枚举器的状态?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！