# Counting to 100 (#119)

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

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

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

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

to another base), but it might not be possible in this problem. I

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

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 Thu, 12 Apr 2007 15:08:09 +0000, Ken B. wrote:

permutation(6549, 1…9) => [123456, 78, 9] permutation(6560, 1…9)
Although it brings up a point that I find interesting – most of the

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.