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 2007-04-11 03:55

on 2007-04-11 05:13

```
On Wed, 11 Apr 2007 10:55:07 +0900, Erwin Abbott 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 Bloom
```

on 2007-04-12 17:11

On Wed, 11 Apr 2007 03:08:07 +0000, Ken Bloom 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 2007-04-12 18:10

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