Ruby: How do you set an Enumerator's state?

Question 1

Results

For your example,

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

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

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

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.

Another example:

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

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.

Permutation ordering

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.

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]

taken three at a time. This is:

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

If we replace the elements of arr with their positions:

pos = [0,1,2,3]

we see that:

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

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.

Note that:

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

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

Easy head-start enumerator

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

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.

Roll your own enumerator

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

head_start_permutation(start)

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.

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

Let's try it:

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)

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

Question 2

You can try using drop_while (using lazy to avoid having the permutation enumerator from going over all its elements):

z = y.lazy.drop_while { |p| p.join != 'ABCDEFGHIJK/' }
z.peek.join
# => "ABCDEFGHIJK/"
z.next
z.peek.join
# => "ABCDEFGHIJLK"