Thread Subject:

Go from end to start of array

Hi guys.

I'm making a script, but I'm stuck with a major problem (which should be solved simply).

Say I have an array, and I want to delete every fourth component, until one component remains. For example:

[1 2 3 4 5 6 7 8 9 10] %input array

will become

[1 2 3 5 6 7 8 9 10] %array after deleting the first fourth component ("4")
[1 2 3 5 6 7 9 10] %array after deleting the second fourth component ("8")

But then it should go back tot the beginning, and delete "2":

[1 3 5 6 7 9 10]
[1 3 5 6 9 10]
[1 5 6 9 10]
[1 5 6 9]
[1 5 6]
[5 6]
[5]

But, I don't know how to give a command to count further from the beginning from the array. So if anyone has some ideas, I would be very thankful.

Thanks a lot in advance!

Arthur <artnaz@gmail.com> wrote in message <15173892.1234517269163.JavaMail.jakarta@nitrogen.mathforum.org>...
> Hi guys.
>
> I'm making a script, but I'm stuck with a major problem (which should be solved simply).
>
> Say I have an array, and I want to delete every fourth component, until one component remains. For example:
>
> [1 2 3 4 5 6 7 8 9 10] %input array
>
> will become
>
> [1 2 3 5 6 7 8 9 10] %array after deleting the first fourth component ("4")
> [1 2 3 5 6 7 9 10] %array after deleting the second fourth component ("8")
>
> But then it should go back tot the beginning, and delete "2":
>
> [1 3 5 6 7 9 10]
> [1 3 5 6 9 10]
> [1 5 6 9 10]
> [1 5 6 9]
> [1 5 6]
> [5 6]
> [5]
>
> But, I don't know how to give a command to count further from the beginning from the array. So if anyone has some ideas, I would be very thankful.
>
> Thanks a lot in advance!

I understand the deleting of the 4th and 8th elements, but can you expand on why "2" has to go?

Arthur <artnaz@gmail.com> writes:

>Hi guys.

>I'm making a script, but I'm stuck with a major problem (which should be solved simply).
The following's not built for speed or even elegance.

x=3;
a=[1 2 3 4 5 6 7 8 9 10]

while (length(a)>1)
  a(x+1)=[]
  x=rem(x-1+4,length(a))
  a
end

> I understand the deleting of the 4th and 8th
> elements, but can you expand on why "2" has to go?

See the array as the number of balls lying in a circle. If you're counting them and you reach the end, the counting continues with with ball number one.

My example wasn't very good though, see my next reply.

Thanks a lot!!! That's the little thing I was looking for. See my comment to see what I made of it.

Sorry, I made a mistake. You have to start with deleting the first element. So the example will be:

[ 1 2 3 4 5 6 7 8 9 10 ]
[ 2 3 4 5 6 7 8 9 10 ]
[ 2 3 4 6 7 8 9 10 ]
[ 2 3 4 6 7 8 10 ]
[ 2 3 6 7 8 10 ]
[ 2 3 6 7 8 ]
[ 2 3 6 8 ]
[ 2 3 8 ]
[ 2 3 ]
[ 2 ]

This is what I got, where

N=amount of balls = input
M=balls to be skipped = input

>m=M;
>a = [2:N]; %we start with the second element since the first must be deleted anyway
>while length(a)>1
> a(M+1)=[];
> M=mod(M+m,length(a+1));
>end
>a %=output

The last thing I have to do is to create a second part where M>N.

So I think this should be it. If there are any comments or tips to save work or make the script better/faster, I would gladly hear them.

Arthur <artnaz@gmail.com> wrote in message <24575660.1235063653276.JavaMail.jakarta@nitrogen.mathforum.org>...
> Sorry, I made a mistake. You have to start with deleting the first element. So the example will be:
>
> [ 1 2 3 4 5 6 7 8 9 10 ]
> [ 2 3 4 5 6 7 8 9 10 ]
> [ 2 3 4 6 7 8 9 10 ]
> [ 2 3 4 6 7 8 10 ]
> [ 2 3 6 7 8 10 ]
> [ 2 3 6 7 8 ]
> [ 2 3 6 8 ]
> [ 2 3 8 ]
> [ 2 3 ]
> [ 2 ]
>
> This is what I got, where
>
> N=amount of balls = input
> M=balls to be skipped = input
>
> >m=M;
> >a = [2:N]; %we start with the second element since the first must be deleted anyway
> >while length(a)>1
> > a(M+1)=[];
> > M=mod(M+m,length(a+1));
> >end
> >a %=output
>
> The last thing I have to do is to create a second part where M>N.
>
> So I think this should be it. If there are any comments or tips to save work or make the script better/faster, I would gladly hear them.

  If the final value of 'a' is the only output you are seeking, and if you wish to do this for large n - the initial length of 'a' - say 50 or more, the following code is an alternative method of doing your calculations which is faster, though for small n it may be slower. For n in the thousands it is dramatically faster, since it is an order log(n) algorithm. 'm' is the length of skip taken in vector 'a' and may be larger than n if desired.

if m == 1
 a = n;
else
 a = 1;
 k = 1;
 while k < n
  c = ceil((k-a+1)/(m-1));
  if c <= n-k
   k = k + c;
   a = mod(a+m*c-2,k-1)+2;
  else
   a = a + m*(n-k);
   k = n;
  end
 end
end

  I am hoping you won't ask me for the theory behind this algorithm. It would be rather troublesome for me to have to explain it.

Roger Stafford

Thanks a lot for the input, but it doesn't give the correct output. And I don't know where you got this from:

>if m == 1
>a = n;

For example, if n=5 and m=1, we get:

[ 1 2 3 4 5 ]
[ 2 3 4 5 ]
[ 2 4 5 ]
[ 2 4 ]
[ 2 ]

And the rest of it doesn't give the correct answer either. Maybe you forgot to start deleting with '1'?

Other than that, I'm afraid I don't understand the theory behind your algorithm on first sight. But maybe that when you have corrected it I could figure it out myself...

Arthur <artnaz@gmail.com> wrote in message <23120260.1235142966555.JavaMail.jakarta@nitrogen.mathforum.org>...
> Thanks a lot for the input, but it doesn't give the correct output. And I don't know where you got this from:
>
> >if m == 1
> >a = n;
>
> For example, if n=5 and m=1, we get:
>
> [ 1 2 3 4 5 ]
> [ 2 3 4 5 ]
> [ 2 4 5 ]
> [ 2 4 ]
> [ 2 ]
>
> And the rest of it doesn't give the correct answer either. Maybe you forgot to start deleting with '1'?
>
> Other than that, I'm afraid I don't understand the theory behind your algorithm on first sight. But maybe that when you have corrected it I could figure it out myself...

  Of course you are the final arbiter of what kind of answer it is you want, Arthur, but I claim that result you are quoting with n = 5 and m = 1 is inconsistent with the description you gave yesterday. With n = 10 and m = 4 your first two deletions yesterday were 1 and 5. Now work on backwards from that decreasing m by one each time. With n = 10 and m = 3, the first two deletions would be 1 and 4; with n = 10 and m = 2, it would be 1 and 3. With n = 10 and m = 1, it would be 1 and 2 in my mind. How do you justify deleting 1 and 3 the first two times in this case? The same inconsistency holds for n = 5.

  Perhaps what we have here is a discrepancy in the definition of m? When you said earlier "I want to delete every fourth component" does that correspond to m = 4 or m = 3, in your view? If "delete every fourth component" means m = 3, then the m in the formula I gave you is off by 1. That is an easy correction to make.

Roger Stafford

You're right, sorry for not being clear. M=amount of elements to be skipped, and (M+1)=element to be deleted. So when N=10 and M=2, we delete '1' and then '4'. When M=4, we delete '1', then '6'.

Your script is working perfectly, it really is lots and lots faster than mine. This would be it:

>if M == 0
> a = N;
>else
> a = 1;
> k = 1;
> while k < N
> c = ceil((k-a+1)/M);
> if c <= N-k
> k = k + c;
> a = mod(a+(M+1)*c-2,k-1)+2;
> else
> a = a + (M+1)*(N-k);
> k = N;
> end
> end
>end

But frankly, I really don't see what's going on. I understand it will be difficult and time-consuming to explain, but maybe you could direct me to some easy examples where I could see the principle?

Arthur <artnaz@gmail.com> wrote in message <28689491.1235151366987.JavaMail.jakarta@nitrogen.mathforum.org>...
> You're right, sorry for not being clear. M=amount of elements to be skipped, and (M+1)=element to be deleted. So when N=10 and M=2, we delete '1' and then '4'. When M=4, we delete '1', then '6'.
>
> Your script is working perfectly, it really is lots and lots faster than mine. This would be it:
>
> >if M == 0
> > a = N;
> >else
> > a = 1;
> > k = 1;
> > while k < N
> > c = ceil((k-a+1)/M);
> > if c <= N-k
> > k = k + c;
> > a = mod(a+(M+1)*c-2,k-1)+2;
> > else
> > a = a + (M+1)*(N-k);
> > k = N;
> > end
> > end
> >end
>
> But frankly, I really don't see what's going on. I understand it will be difficult and time-consuming to explain, but maybe you could direct me to some easy examples where I could see the principle?
------------------------------------------
  Well, I'll try to give a brief explanation, Arthur. Suppose we use the example you gave earlier with your M = 3 (and my m = 4) but for each of the values of n from 1 up to 25. That is, we do twenty-five different problems. In the first row below are listed the various values of n and in the second row the corresponding computed values of the final 'a' in each case. In particular, notice that under n = 10 there is a final 'a' value of a = 2.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25
1 2 2 3 3 2 6 3 7 2 6 10 2 6 10 14 2 6 10 14 18 22 4 8 12

  Now we look for some kind of regularity in this sequence, and sure enough, there is a very definite pattern to be seen. It is easier to see it in the higher values of n here. Consider the subsequence of a's from n = 17 to n = 22. The a's which go from 2 up to 22 are increasing at each step by 4. Then suddenly at n = 23 they drop down to 4. How do we account for that drop? I claim the computation goes like this. First add another 4 to get 22+4=26. However this would exceed the corresponding n=23 at that point, so we subtract as many of the previous n=22 values as are needed to bring it down sufficiently so as not to exceed 23. In this case just one 22 will do the job: 26-1*22=4. If you study the remaining ascending sequences here, as well as those for higher values of n and other m values, you will find that this simple rule always gives the proper answer. Even at the first
step from n = 1 to n = 2 it works. Starting with n = 1 and a = 1, add 4 to a to get 5. Then subtract as many values 1 as are necessary to bring 'a' down to at most n+1=2 and the answer is to subtract three 1's to arrive at exactly 2.

  We can put this rule into general terms. To go from a current n and a, we add 1 to n to get n+1 and first we add m to a to get a+m. (This is my m; using your M it would be a+M+1.) If that exceeds the new n+1, we subtract as many of the prior values n from a+m as are needed to bring it down to at most n+1. This step can be entirely expressed in terms of the 'mod' function using two simple lines of matlab code:

 a = mod(a+m-2,n)+2;
 n = n+1;

  The new 'a' can lie anywhere from 2 up to the new n+1. Only the first value of 'a' can be equal to 1. It can never occur later since it is always deleted at the first step. Also 'a' can never exceed the corresponding n at each step since otherwise initially there would be no such a-value present to be deleted.

  This simple procedure could actually be used to generate an entire matrix of final 'a' values for ranges of m, say from m1 to m2, and ranges of n extending up from 1 to N using a for-loop:

 m = (m1:m2).';
 a = ones(size(m,1),N);
 for n = 1:N-1
  a(:,n+1) = mod(a(:,n)+m-2,n)+2;
 end

This would be a very efficient way of creating entire tables of these 'a' values. However to obtain single values of n, it is not much faster doing this iteration starting up from 1 and on up to n than it is deleting the n values one at a time. I was after "bigger game".

  To make a more efficient routine for just solving a single value of m and n, the strategy I used was this. As you can imagine, if n is very large, the successive ascending subsequences of a's get longer and longer and the points where it is necessary for the a's to suddenly drop down get farther and farther apart. These ascending sequences become exponentially longer as n increases. The code I wrote shortens this process by skipping directly from one start point of an ascending sequence to the beginning of the next ascending sequence in just one step. From the beginning of each such sequence it is possible to predict where the next one will occur, and that is the reason behind the line of code:

 c = ceil((k-a+1)/(m-1));

It is figuring out just how much to increase k (the current n value) to get to the next start point at which an "overflow" will occur. Only at the last step when that would go beyond the specified value of n is the procedure altered to do only a simple addition without any use of 'mod'. Checking for this latter is the reason for the "if c <= n-k" test.

  As for establishing that the above procedure is mathematically valid, come back to the picture you had, Arthur, of n balls lying in a circle. That is an excellent way of thinking about this problem. Temporarily forget about numbering them. Starting with n balls beginning at a certain ball to be initially deleted, suppose you have completely solved the problem of which ball will be the last to be deleted. Now imagine the same problem starting with n+1 balls. I make the claim that after you have deleted the first ball and have moved around m balls to the position of the second ball to be deleted, before you have actually deleted it you are then facing the same n-ball problem as before except with a different ball as a starting point. In other words the starting point for the corresponding n-ball problem is advanced m positions from the n+1-ball starting point, and therefore the
position of the final ball in the n+1 problem is also advanced m ball positions from that of the ordinary n-ball problem. That is why the 'a' values have m added to them in the above lists each time n increases by 1, except when the numbering system has to start over around the circular path. Of course such renumbering has to be based on the number of balls present in the circle after the first ball was deleted and therefore leads to a divisor of n being used in the corresponding modulo-type operation. What you have here is an informal version of a rigorous proof by mathematical induction. Such a proof also requires that the statement needs to be proven for the first step going from n=1 to n=2, but that is trivial.

Roger Stafford

Roger,

Can you indicates what I need to change in the parameters in the script below to force the two algorithms output the same result.

Thanks

Bruno

%%%%%%%%%%%%%

% Test case:
n=10;
m=4;
a=(1:n);

% Basic algo
i=1;
while length(a)>1
    disp(a)
    i=mod(i+m-2,length(a))+1;
    a(i)=[];
end
disp(a)

% Roger's algorithm
n=10;
m=4;
if m == 1
    a = n;
else
    a = 1;
    k = 1;
    while k < n
        c = ceil((k-a+1)/(m-1));
        if c <= n-k
            k = k + c;
            a = mod(a+m*c-2,k-1)+2;
        else
            a = a + m*(n-k);
            k = n;
        end
    end
end
a % how to get 5?

"Bruno Luong" <b.luong@fogale.findmycountry> wrote in message <gnoa4p$j9q$1@fred.mathworks.com>...
> Roger,
>
> Can you indicates what I need to change in the parameters in the script below to force the two algorithms output the same result.
>
> Thanks
>
> Bruno
>
> %%%%%%%%%%%%%
>
> % Test case:
> n=10;
> m=4;
> a=(1:n);
>
> % Basic algo
> i=1;
> while length(a)>1
> disp(a)
> i=mod(i+m-2,length(a))+1;
> a(i)=[];
> end
> disp(a)
> ......
------------
Hi Bruno,

  Your parameters are all just right. You simply neglected to start by deleting the first element of a. To agree with Arthur's procedure you should have:

% Test case:
n=10;
m=4;
a=(1:n);

% Basic algo
i=1;
a(i) = []; % <-- Add this, RAS
while length(a)>1
    disp(a)
    i=mod(i+m-2,length(a))+1;
    a(i)=[];
end
disp(a)

That should end up with 2 in this case.

  Bear in mind that the two algorithms are doing quite different things as they proceed. Only at the end should they agree as to the final value of 'a'. My claim is that for very large values of n with m small, the while-loop method should be considerably faster because it has fewer steps to take. The smaller the parameter m is, the greater the number of skipped steps.

Roger Stafford

"Roger Stafford" <ellieandrogerxyzzy@mindspring.com.invalid> wrote in message <gnq1pu$mtt$1@fred.mathworks.com>...

>
> Bear in mind that the two algorithms are doing quite different things as they proceed. Only at the end should they agree as to the final value of 'a'. My claim is that for very large values of n with m small, the while-loop method should be considerably faster because it has fewer steps to take. The smaller the parameter m is, the greater the number of skipped steps.
>

The naive algorithm is not fast at all. Deleting single element on a loop brings the complexity to O(n^2) on the memory access count. It is obviously slow for large n, regardless m.

Bruno

"Bruno Luong" <b.luong@fogale.findmycountry> wrote in message <gnr4bb$ehi$1@fred.mathworks.com>...
> The naive algorithm is not fast at all. Deleting single element on a loop brings the complexity to O(n^2) on the memory access count. It is obviously slow for large n, regardless m.
>
> Bruno

  It would only be order n^2 if you were calculating the final a's for each value from 1 to n, performing each deletion task separately. However that task is most efficiently carried out by

 m = 5; % Or whatever m you choose
 a = ones(1,N);
 for n = 1:N-1
  a(n+1) = mod(a(n)+m-2,n)+2;
 end

which would accomplish the same thing in order n. Note that this isn't tracing out the successive deletions. It is solving each a-problem in one step, but it has to start with n = 1 to do so. I would judge that this is the best algorithm one could use to generate an entire list of the final a's from 1 to some N. (That is, unless someone comes up with some kind of formula for the a's that can be vectorized.)

Roger Stafford

"Roger Stafford" <ellieandrogerxyzzy@mindspring.com.invalid> wrote in message <gns2v0$2sf$1@fred.mathworks.com>...
> "Bruno Luong" <b.luong@fogale.findmycountry> wrote in message
>
> m = 5; % Or whatever m you choose
> a = ones(1,N);
> for n = 1:N-1
> a(n+1) = mod(a(n)+m-2,n)+2;
> end
>

Great progress you have made Roger, and I have an impression it's not yet finished.

Bruno

Hi Roger,

Sorry for my late response...

Thank you enormously for great explanation! I don't understand it for 100% yet, but I'm almost there I think.

Again, thanks for the effort!