2

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.

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"

. # DO SOMETHING LIKE THIS

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

. # AND PICK UP AS FOLLOWS

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

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.

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

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/

5
  • Enumerator mixes in Enumerable. Does that help?
    – matt
    May 11, 2014 at 2:45
  • I've gone through the RubyDoc's for both of those Core objects. ruby-doc.org/core-1.9.3/Enumerable.html and ruby-doc.org/core-1.9.3/Enumerator.html
    – 6ft Dan
    May 11, 2014 at 2:49
  • The closest thing I've come across is slice_before(state) which returns an enumerator. But this solves nothing since it's just another subsection starting at the beginning and drops the value afterwards, which is what I need.
    – 6ft Dan
    May 11, 2014 at 2:55
  • 2
    The short answer is "you don't". Enumerators don't guarantee a fixed order, just that you will eventually get all of elements. I think what you want is to cast the entire enumeration to an Array, then maybe sorting the Array will let you do want you want. May 11, 2014 at 3:12
  • Any computer will hang trying to generate a full list of permutations of base 64. If there's a max on Array size, this probably goes beyond that.
    – 6ft Dan
    May 11, 2014 at 3:15

2 Answers 2

3

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.

3
  • 2
    This is a Book... :-) May 12, 2014 at 19:18
  • You have provided a very beautiful answer. I am definitely going to experiment with this.
    – 6ft Dan
    May 12, 2014 at 19:20
  • 2
    Thanks, 6ft Dan (not to be confused with 5ft Dan or 7ft Dan). May 12, 2014 at 20:11
0

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"
5
  • I believe that came out Ruby 2.0. It looks like a great solution! I suppose that's the only way.
    – 6ft Dan
    May 11, 2014 at 18:07
  • Yes, I believe 'lazy' is a 2.0 feature
    – Uri Agassi
    May 11, 2014 at 18:34
  • Uri, could you elaborate "using lazy to avoid having the permutation enumerator from going over all its elements"? Are you saying it doesn't use next repeatedly to get to the desired starting point? May 12, 2014 at 7:30
  • ruby-doc.org/core-2.1.1/Array.html#method-i-drop_while : "...and returns an array containing the remaining elements" drop_while actually iterates over all the elements building the result array. Enumerator::Lazy has its own implementation: ruby-doc.org/core-2.0/Enumerator/Lazy.html#method-i-drop_while
    – Uri Agassi
    May 12, 2014 at 7:39
  • 1
    Uri. This won't work. Even with lazy it needs to invoke next repeatedly to get to the starting value. Suppose the first element of the starting permutation were 'o'. As x.size => 64 and x.index('o') => 40, next would have to be invoked on the order of 64**40 times to get to 'o' as the first element of the permutation. If you try your code with, say, x.sample(12) you'll see what I mean. May 12, 2014 at 19:23

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.