0

I am trying to loop the numbers 1 to 1000 in such a way that I have all possible pairs, e.g., 1 and 1, 1 and 2, 1 and 3, ..., but also 2 and 1, 2 and 2, 2 and 3, et cetera, and so on.

In this case I have a condition (amicable_pair) that returns true if two numbers are an amicable pair. I want to check all numbers from 1 to n against each other and add all amicable pairs to a total total. The first value will be added to the total if it is part of an amicable pair (not the second value of the pair, since we'll find that later in the loop). To do this I wrote the following "Java-like" code:

def add_amicable_pairs(n)
  amicable_values = []
  for i in 1..n
    for j in 1..n
      if (amicable_pair?(i,j)) 
        amicable_values.push(i)
        puts "added #{i} from amicable pair #{i}, #{j}"
      end
    end
  end
  return amicable_values.inject(:+)
end

Two issues with this: (1) it is really slow. (2) In Ruby you should not use for-loops.

This is why I am wondering how this can be accomplished in a faster and more Ruby-like way. Any help would be greatly appreciated.

Improve this question
13
  • 1
    As with a for loops, use 1.up_to(n) do |i| or (1..n).each do |i| instead. How fast given loop is depends heavily on amicable_pair implementation. Commented Mar 29, 2014 at 11:57
  • 3
    @Log1c, you can use for loops in Ruby if you want. But actually, internally they are converted to calls to each, so just using the each method makes it clearer what is actually happening. Commented Mar 29, 2014 at 11:59
  • 1
    @user2609980 see code here at ideone.com/21zVX0 it is really fast. Commented Mar 29, 2014 at 12:59
  • 1
    One important difference between using a for-loop and an enumerator is that the for-loop variable (e.g., i) is in scope after the loop's 'end' statement, whereas enumerators use variables whose scope is confined to their associated block. Generally, the latter is preferable, but the former could be useful if, for example, you wanted to know the value of a for-loop variable if you were to break from the loop. I'm not advocating the use of for-loops, however. I never use them, as I always seem to find a better alternative. Commented Mar 29, 2014 at 17:42
  • 1
    @user2609980 sorry for late reply as it was night here. Your code in add_amicable_pairs method uses either 2 level iteration or using array product method which in itself uses iteration to combine numbers within individual array, my code in same method uses single iteration. Your code in amicable_pair? method calls d(n) 2 times where my code in same method calls d(n) only one time, in amicable_pair?(a, b) a is b for previous method call so I am keeping it in a hash. Your method d(n) uses n/2 my code there uses sqrt(n)..... That is why my code is faster. Commented Mar 30, 2014 at 8:39

2 Answers 2

Reset to default
2

Your code has O(n^2) runtime, so if n gets moderately large then it will naturally be slow. Brute-force algorithms are always slow if the search space is large. To avoid this, is there some way you can directly find the "amicable pairs" rather than looping through all possible combinations and checking one by one?

As far as how to write the loops in a more elegant way, I would probably rewrite your code as:

(1..n).to_a.product((1..n).to_a).select { |a,b| amicable_pair?(a,b) }.reduce(0, &:+)
Improve this answer
Sign up to request clarification or add additional context in comments.

7 Comments

Alex thanks a lot! Full code is here. It has been running for the last half hour now and it is at 1200/10000.
@user2609980 it's a Cartesian/Cross product of the range 1 to n.
Apparently there are formulas for generating amicable pairs, but they won't generate all pairs, so unless you want to dive down the mathematical rabbit hole and try to invent a new, fast algorithm that generates all amicable numbers, I don't think you'll improve on the O(n^2) algorithm by more than a constant factor, especially for large n.
This answer to "How to solve project euler #21 faster?" may be of interest. Also, Project Euler 21: Sum of Amicable Pairs Under 10000.
@user2609980 the number of pairs between a set of n numbers joined with itself is equal to n^2, so generating all the pairs necessarily takes on the order of O(n^2) steps, no matter what algorithm you use, unless I'm missing some clever combinatorial trick. In fact, it's not just O(n^2), but rather Theta(n^2). Using the product method just uses less code than using for-loops (again, unless I'm missing a combinatorial shortcut).
|
2 
(1..1000).to_a.repeated_permutation(2).select{|pair| amicable_pair?(*pair)}
.map(&:first).inject(:+)
Improve this answer

7 Comments

Two things I do not understand: (1) *pair, where does it come from? Is pair the output from .permutation(2)? Then what is the *? (2) What does &:first mean? Thanks!
permutation returns a pair [x, y]. pair receives it, and *pair decomposes it as separate arguments. map{|x| x.first} takes the first argument of each pair.
@user2609980 I highly recommend that you pick up a copy of Programming Ruby: The Pragmatic Programmers' Guide. It's also known as the "Pickaxe" book in the Ruby community, and is considered to be the de facto standard guide to the Ruby language in English. Also, the Ruby Programming wiki book is a free resource that you can use.
@sawa is permutation a correct choice here? It won't generate a pair like (1,1), I think you'll need a cross-product for that.
@Cupcake Woops, you are right. I need repeated_permutation.
|

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.