# Counting to 100 (#119)

**URL:** <https://www.ruby-forum.com/t/counting-to-100-119/91646>\
**Category:** Ruby\
**Created:** [April 11, 2007, 3:55am UTC](https://www.ruby-forum.com/t/counting-to-100-119/91646 "2007-04-11T03:55:38Z")\
**Posts on this page:** 4\
**Page:** 1

<div class="post-metadata">

**Author:** ![Erwin\_A](https://www.ruby-forum.com/letter_avatar_proxy/v4/letter/e/ce7236/32.png) [@Erwin\_A](https://www.ruby-forum.com/u/Erwin_A)\
**Post date:** [April 11, 2007, 3:55am UTC](https://www.ruby-forum.com/t/counting-to-100-119/91646/1 "2007-04-11T03:55:38Z")

</div>

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

---

<div class="post-metadata">

**Author:** ![Erwin\_A](https://www.ruby-forum.com/letter_avatar_proxy/v4/letter/e/ce7236/32.png) [@Erwin\_A](https://www.ruby-forum.com/u/Erwin_A)\
**Post date:** [April 11, 2007, 5:13am UTC](https://www.ruby-forum.com/t/counting-to-100-119/91646/2 "2007-04-11T05:13:42Z")

</div>

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.

---

<div class="post-metadata">

**Author:** ![Erwin\_A](https://www.ruby-forum.com/letter_avatar_proxy/v4/letter/e/ce7236/32.png) [@Erwin\_A](https://www.ruby-forum.com/u/Erwin_A)\
**Post date:** [April 12, 2007, 5:11pm UTC](https://www.ruby-forum.com/t/counting-to-100-119/91646/3 "2007-04-12T17:11:31Z")

</div>

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

---

<div class="post-metadata">

**Author:** ![Erwin\_A](https://www.ruby-forum.com/letter_avatar_proxy/v4/letter/e/ce7236/32.png) [@Erwin\_A](https://www.ruby-forum.com/u/Erwin_A)\
**Post date:** [April 12, 2007, 6:10pm UTC](https://www.ruby-forum.com/t/counting-to-100-119/91646/4 "2007-04-12T18:10:37Z")

</div>

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.