[QUIZ] Counting to 100 (#119)

ruby-talk
1

It would be really interesting to write a non-recursive permute
function that could map a number n to each permutation of digits, and
map n+1 to the next permutation. Then we could just count from 1 to
6561 for 9 digits, 1 to 19683 for 10 digits, etc. Something like
this:
  permutation(1, 1..9) => [1, 2, 3, 4, 5, 6, 7, 8, 9]
  permutation(6549, 1..9) => [123456, 78, 9]
  permutation(6560, 1..9) => [123456, 789]

This is easy when we're permuting a single number (it's just
converting to another base), but it might not be possible in this
problem. I guess the recursive method really only goes 9 or 10 level
deep anyway.

#!/usr/bin/env ruby

# return all combinations of numbers using @digits
def permute digits, progress=[], results=[]
  # last used digit
  last = progress.last ? digits.index(progress.last % 10) : -1

  # this permutation is all done
  return results << progress if last+1 == digits.size

  remaining = digits[last+1 .. -1]
  remaining.size.times do |b|
    # if the last digit used was 1, we'll try these as the next number;
    # 2, 23, 234, 2345, ..., 23456789

    num = remaining[0..b].join.to_i
    permute digits, progress+[num], results
  end

  results
end

# all permutations of n operations, ops
def operations ops, n, progress=[], results=[]
  # done when we've got n operation is progress array
  return results << progress if progress.size == n

  ops.each{|o| operations ops, n, progress+[o], results }
  results # modified by method call
end

# return expr string and value, give set of numbers and corresponding ops
def compute numbers, ops
  e = numbers.zip(ops).flatten.map{|n| n.to_s}.join ' ' # make a string
  v = eval(e) # evaluate it
  ["#{e}= #{v}", v]
end

def target value, digits=(1..9).to_a, ops=[:+, :-]
  # note: only digits 0 - 9 work, because of % 10 math in permute method

  stars = '*'*76 + "\n"
  count = 0
  cache = {}
  permutations = permute digits

  permutations.each do |nums|
    # cache permutations of nums.size-1 operations
    opers = cache[nums.size-1] ||
           (cache[nums.size-1] = operations(ops, nums.size-1))

    opers.each do |o|
      count += 1
      expr, val = compute(nums, o)

      if val != value
        puts expr
      else
        puts stars + expr << "\n" << stars
      end

    end
  end

  puts "#{count} possible equations tested"
end

if $0 == __FILE__
    target 100, (1..9).to_a, [:+, :-]
end

2

This isn't permuting -- it's partitioning. Permuting is coming up with
all possible orders for the elements in the array.

Although it brings up a point that I find interesting -- most of the
permutation generator implementations I've seen for Ruby are recursive --
they do very specific things with the positions in the array without
regard to what the contents are. This causes issues like duplicate
permutations when there are duplicate elements in the array.

Is there an implementation of a permutation generator out there that
works similar to the C++ STL's next_permutation function? The C++ STL's
next_permutation function doesn't have the luxury of recursion or state,
so it has to generate permutations based on the ordering of elements
according to the comparison operators.

--Ken Bloom

···

On Wed, 11 Apr 2007 10:55:07 +0900, Erwin Abbott wrote:

It would be really interesting to write a non-recursive permute function
that could map a number n to each permutation of digits, and map n+1 to
the next permutation. Then we could just count from 1 to 6561 for 9
digits, 1 to 19683 for 10 digits, etc. Something like this:
  permutation(1, 1..9) => [1, 2, 3, 4, 5, 6, 7, 8, 9]
  permutation(6549, 1..9) => [123456, 78, 9]
  permutation(6560, 1..9) => [123456, 789]

This is easy when we're permuting a single number (it's just converting
to another base), but it might not be possible in this problem. I guess
the recursive method really only goes 9 or 10 level deep anyway.

--
Ken Bloom. PhD candidate. Linguistic Cognition Laboratory.
Department of Computer Science. Illinois Institute of Technology.
http://www.iit.edu/~kbloom1/

3

OK. Here we go. I've ported this from the G++ 4.1 STL, which can be found
in /usr/include/c++/4.1.2/bits/stl_algo.h

class Array
   #based on the C++ standard library's implementation
   def next_permutation!
      return self if length<2
      i=length-1
      while true
   ii=i
   i-=1
   if self[i]<self[ii]
      j=length
      nil until self[i]<self[j-=1]
      self[i],self[j]=self[j],self[i]
      reverse_part!(ii,length)
      return self
   end
   if (i == 0)
      reverse!
      return self
   end
      end
   end

   def next_permutation
      dup.next_permutation!
   end

   def reverse_part! start,stop
      while start<stop
   self[start],self[stop-1]=self[stop-1],self[start]
   stop-=1
   start+=1
      end
   end
   private :reverse_part!

   #each_permutation implementation that permutes based on
   #the contents of the array. No duplicate permutations are
   #yielded, even when there are duplicate elements in
   #the array. The elements of the array must
   #be mutually comparable.
   def each_permutation
      temp=sort
      stop=temp.reverse
      yield temp
      until temp.next_permutation! == stop
   yield temp
      end
   end
end

···

On Wed, 11 Apr 2007 03:08:07 +0000, Ken Bloom wrote:

On Wed, 11 Apr 2007 10:55:07 +0900, Erwin Abbott wrote:

It would be really interesting to write a non-recursive permute
function that could map a number n to each permutation of digits, and
map n+1 to the next permutation. Then we could just count from 1 to
6561 for 9 digits, 1 to 19683 for 10 digits, etc. Something like this:
  permutation(1, 1..9) => [1, 2, 3, 4, 5, 6, 7, 8, 9] permutation(6549,
  1..9) => [123456, 78, 9] permutation(6560, 1..9) => [123456, 789]

This is easy when we're permuting a single number (it's just converting
to another base), but it might not be possible in this problem. I
guess the recursive method really only goes 9 or 10 level deep anyway.

This isn't permuting -- it's partitioning. Permuting is coming up with
all possible orders for the elements in the array.

Although it brings up a point that I find interesting -- most of the
permutation generator implementations I've seen for Ruby are recursive
-- they do very specific things with the positions in the array without
regard to what the contents are. This causes issues like duplicate
permutations when there are duplicate elements in the array.

Is there an implementation of a permutation generator out there that
works similar to the C++ STL's next_permutation function? The C++ STL's
next_permutation function doesn't have the luxury of recursion or state,
so it has to generate permutations based on the ordering of elements
according to the comparison operators.

--
Ken Bloom. PhD candidate. Linguistic Cognition Laboratory.
Department of Computer Science. Illinois Institute of Technology.
http://www.iit.edu/~kbloom1/

4

It would be really interesting to write a non-recursive permute
function that could map a number n to each permutation of digits, and
map n+1 to the next permutation. Then we could just count from 1 to
6561 for 9 digits, 1 to 19683 for 10 digits, etc. Something like
this:
  permutation(1, 1..9) => [1, 2, 3, 4, 5, 6, 7, 8, 9]
  permutation(6549, 1..9) => [123456, 78, 9] permutation(6560, 1..9)
  => [123456, 789]

This is easy when we're permuting a single number (it's just
converting to another base), but it might not be possible in this
problem. I guess the recursive method really only goes 9 or 10 level
deep anyway.

This isn't permuting -- it's partitioning. Permuting is coming up with
all possible orders for the elements in the array.

Although it brings up a point that I find interesting -- most of the
permutation generator implementations I've seen for Ruby are recursive
-- they do very specific things with the positions in the array without
regard to what the contents are. This causes issues like duplicate
permutations when there are duplicate elements in the array.

Is there an implementation of a permutation generator out there that
works similar to the C++ STL's next_permutation function? The C++ STL's
next_permutation function doesn't have the luxury of recursion or
state, so it has to generate permutations based on the ordering of
elements according to the comparison operators.

OK. Here we go. I've ported this from the G++ 4.1 STL, which can be
found in /usr/include/c++/4.1.2/bits/stl_algo.h

FYI, since this is a derived work from the G++ STL, it's under the GNU
General Public license, version 2 or (at your option) any later version.

···

On Thu, 12 Apr 2007 15:08:09 +0000, Ken Bloom wrote:

On Wed, 11 Apr 2007 03:08:07 +0000, Ken Bloom wrote:

On Wed, 11 Apr 2007 10:55:07 +0900, Erwin Abbott wrote:

class Array
   #based on the C++ standard library's implementation def
   next_permutation!
      return self if length<2
      i=length-1
      while true
   ii=i
   i-=1
   if self[i]<self[ii]
      j=length
      nil until self[i]<self[j-=1]
      self[i],self[j]=self[j],self[i]
      reverse_part!(ii,length)
      return self
   end
   if (i == 0)
      reverse!
      return self
   end
      end
   end

   def next_permutation
      dup.next_permutation!
   end

   def reverse_part! start,stop
      while start<stop
   self[start],self[stop-1]=self[stop-1],self[start] stop-=1
   start+=1
      end
   end
   private :reverse_part!

   #each_permutation implementation that permutes based on #the contents
   of the array. No duplicate permutations are #yielded, even when there
   are duplicate elements in #the array. The elements of the array must
   #be mutually comparable.
   def each_permutation
      temp=sort
      stop=temp.reverse
      yield temp
      until temp.next_permutation! == stop
   yield temp
      end
   end
end

--
Ken Bloom. PhD candidate. Linguistic Cognition Laboratory.
Department of Computer Science. Illinois Institute of Technology.
http://www.iit.edu/~kbloom1/