Matlab algorithm issue

Question

So guys, I have a problem developing an algorithm that takes a finite list of real numbers that are sorted in increasing order and a real number N, and

-If there exists two indices i and j, such that 1 <= i <j <= numel(L) and L(i)+L(j)=N, then then algorithm returns the pair sumToN = [L(i) L(j)]; in the case that multiple pairs of indices exist with the required property, the function returns one of the valid pairs,

-If the equality L(i)+L(j)=N is not satisfied for any indices i and j, such that 1 <= i < j <= numel(L), the function return the empty pair Ret.

L = [1 2 2 3];
N = 3;
sumToN = 0;

for i=1:numel(L);
  for j=1:numel(L);
    if i<j;
        if L(i) + L(j) == N;

        sumToN = [L(i) L(j)];
    display(sumToN);
        else
        Ret = [0 0];
        display(Ret);
        end
    end
   end
end

Now, in this code that I've written in Matlab R2014, independently of the if conditions, I get a strange output: the command window displays two times the vector sumToN and four times the vector Ret. Any suggestion about how to solve this problem? I think that the algorithm is correct...

SO does not seem to support LateX markup can you edit your question so it's more readable please? thanks! — Benoit_11, Jul 29 '15 at 16:20

score 1 · Answer 1 · answered Jul 29 '15 at 16:24

The algorithm is correct and the display behavior is also correct. In your loop i<j is satisfied 6 times. That is for the (i,j) pairs (1,2),(1,3),(1,4),(2,3),(2,4),(3,4). So based on your code you should expect a display 6 times. In these pairs based on the data in L, the condition L(i)+L(j)==3 can be satisfied twice with (1,2) and (1,3). So you get sumToN displayed twice and the rest 4 times Ret displayed.

If you want to stop as soon as you find a pair, you should return the values from this function as soon as you detect L(i)+L(j) == N. You should initialize Ret to [0 0] before the start of the loops and return that after the loop ends. This will return [0 0] if you do not find L(i)+L(j) == N.

If it is a function you can just return from it. If not you need to set some flag variables and break from the loops. — Navan, Jul 30 '15 at 02:45

score 1 · Answer 2 · edited May 23 '17 at 11:43

Let's deconstruct your program a bit. The first thing I'm going to do is change the loop variables from i, j to a, b, because of this: Using i and j as variables in Matlab.

Next I'll look at the line

if i<j;

We always want this to be the case, so let's make it that way. (Switching to a, b now)...

for a=1:numel(L)-1
   for b=a+1:numel(L)

Notice that the loop for b now begins at the value a+1. So b is always greater than a and we no longer need this check. I've also ended the a loop at numel(L)-1 because there is no element after L(numel(L)) for b to occupy and we want to make sure that a+1 is always valid.
(Also note that I've removed the semicolon at the ends of the lines. They're unnecessary and effectively add a blank line to the loop.)

Now we're ready to see if the L(a), L(b) pair adds to N and if so, set our return value:

if L(a)+L(b) == N
   sumToN = [L(a) L(b)];

If you want the value displayed here, either do:

   display(sumToN);

or leave the semicolon off of the assignment sumToN = ...

If we're inside the if and we've assigned the return value, we want to stop looking for other answers. I'm going to assume at this point that you're supposed to be writing a standalone function and that this is all the function is supposed to do. To end the loops (and, indeed, any further processing of the function) you would use return immediately after the assignment. That makes the nested loops look like this:

sumToN = [0 0];
for a=1:numel(L)-1
   for b=a:numel(L)
      if L(a)+L(b) == N
         sumToN = [L(a) L(b)];
         return
      end
   end
end

From here, you can either add your initializations for L and N at the beginning and disp(sumToN); at the end for a script, or you can make a full-fledged function with a function declaration and another end:

function sumToEnd = summy(L,N)
   <all the stuff above goes here>
end

Things are a little more complicated if this is part of a larger script that you don't want to completely exit once you find a pair, but it's still quite possible. (You would have to use break twice, which exits out of a single loop each time, paired with a boolean variable to tell you when to break.)

The algorithm above doesn't seem to return the empty pair if the condition ´L(a)+L(b) == N´ isn't satisfied... — james42, Jul 30 '15 at 15:49
@ale42 It does for me. `sumToN = [0 0];` means that `[0 0]` will be returned if nothing overwrites it. Did you try running it? — beaker, Jul 30 '15 at 15:53
Yep. Now it works, and the code is ligher. I've added ´display(sumToN)´ right before the return in the ´for´ loop, just before ´return´ and at the end of the program, outside the loop. Thanks! — james42, Jul 30 '15 at 16:02

score 0 · Answer 3 · answered Jul 29 '15 at 17:18

Ok guys, I've solved the problem this way:

L = [1 2 2 3];
N = 3;
sumToN = 0;
Ret = [0 0];

for i=1:numel(L);
  for j=1:numel(L);
    if i<j && L(i) + L(j) == N;
     sumToN = [L(i) L(j)];
    end
  end
end
if sum(sumToN) == N;
     display(sumToN);

else
     display(Ret);
end

But, even if the result displayed is only one, the number of steps executed in the for loop doesn't change.

Matlab algorithm issue

3 Answers3

Linked