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

```