Exercise - Rotate Array

arithma

Given an array of numbers, and a rotate parameter, move the elements of the array to the right (for a positive rotate parameter and to the left for a negative one). Overflowing elements will wrap around to the other end of the array.

Example:
rotate: +1
array: 0 1 2 3 4 5 6
result: 6 0 1 2 3 4 5

Extra
Since the above can be easily solved by creating another array and mapping elements then copying back to the array, here's an extra challenge.

Your result must be a list of pairs. These pairs designate the swaps between elements that when all done sequentially will return the desired output. In a sense you're returning instructions from a constrained instruction set. Each pair is the two index parameters that will be passed to a swap function.

You can essentially replace the array with a single count number since the content of the array should not affect the result. I was hoping this sentence would have resolved the ambiguity.

Example:
rotate: -1
array: [0 1 2 3]
result: (0, 1), (1, 2), (2, 3)... this transforms the above array into: [1 2 3 0]

Same Example:
rotate: -1
array: [a b c d]
should return the same result, transforming the array to:

In essence, all the algorithm needs is the array size and the shift parameter.
[a b c d] swap (0, 1) ->
swap (1, 2) ->
swap (2, 3) ->

Hope that clarifies things.

mesa177

This is using the 'circshift' command in Matlab (as written in Command Window):

>> array = (0:1:6)

array =

     0     1     2     3     4     5     6

>> circshift(array,[0,1])

ans =

     6     0     1     2     3     4     5

I'll write the code for reading the given commands:
rotate: num
array: [bla,bla,bla...]
with a text file and post it soon

As for the extra part, the result of the transform you made is [3 0 1 2].
The actual transform to be conducted is either:
(0,3), (1,3), (2,3) or
(0,3), (1,2), (1,3) or
(0,3), (2,3), (1,2)
I'll also work on this

Georges

Nice exercise Arithma.
This technique is used in Cryptography too. It's an Encryption By Substitution.

Caesar Cipher
The earliest known use of a substitution cipher, and the simplest, was by Julius Caesar. The Caesar cipher involves replacing each letter of the alphabet with the letter standing three places further down the alphabet. For example,

plain: meet me after the toga party
cipher: PHHW PH DIWHU WKH WRJD SDUWB

Note that the alphabet is wrapped around, so that the letter following Z is A. We can define the transformation by listing all possibilities, as follows:

plain: a b c d e f g h i j k l m n o p q r s t u v w x y z
cipher: D E F G H I J K L M N O P Q R S T U V W X Y Z A B C

----
As for the solution, Here's mine. (in C#)

class RotateArray
{
        public static int key;
        public static string Rotate(string textToRotate)
        {
            StringBuilder origText = new StringBuilder(textToRotate);
            StringBuilder rotText = new StringBuilder(textToRotate.Length);
            int c;

            for (int i = 0; i < textToRotate.Length; i++)
            {
                c = (int)origText[i];
                c = (c + key);

                rotText.Append((char)c);
            }
            return rotText.ToString();
        }
}

And a quick use of that class in a windows form.

private void performRotation()
{
            int key = (Convert.ToInt16(rotationKey.Value)); // Got through a numeric updown control.
            string rotated;
            RotateArray.key = key; // Provide the rotation key.

            rotated = RotateArray.Rotate(txtOriginalText.Text); // Perform rotation on textbox text

            txtEncryptedText.Text = rotated;
}

Edit: Please note that this method covers all possible combinations of inputs. (Numbers, characters, etc.)

arithma

Please check the edit for some disambiguation. mesa, what I posted the first time is indeed correct. It's a little bit out of place to "assume that I am wrong in solving the problem that I am proposing" as opposed to "placing an inquiry for more information about the problem so that the examples make sense".

mesa177

arithma wrotePlease check the edit for some disambiguation. mesa, what I posted the first time is indeed correct. It's a little bit out of place to "assume that I am wrong in solving the problem that I am proposing" as opposed to "placing an inquiry for more information about the problem so that the examples make sense".

Ok Skafi, you meant the numbers in the swap transfrom are the entries on the array => there is no such thing as entry 0 => use entry numbers 1, 2, 3 and 4

arithma

mesa177 wrote
arithma wrotePlease check the edit for some disambiguation. mesa, what I posted the first time is indeed correct. It's a little bit out of place to "assume that I am wrong in solving the problem that I am proposing" as opposed to "placing an inquiry for more information about the problem so that the examples make sense".
Ok Skafi, you meant the numbers in the swap transfrom are the entries on the array => there is no such thing as entry 0 => use entry numbers 1, 2, 3 and 4

This depends on the language you are using. MATLAB uses base-1 while most other languages use base-0.

Georges

Here's another solution that fits the extra part you wanted:
[a b c d] swap (0, 1) ->
swap (1, 2) ->
swap (2, 3) ->

int[] myIntArray = new int[6] {0, 1, 2, 3, 4, 5 };
int[] myArray = new int[6] { 0, 1, 2, 3, 4, 5 };

Console.WriteLine("Please Enter the Shift Parameter: ");
int key = Convert.ToInt32(Console.ReadLine());

if (key < 0)
    key = myIntArray.Length + key;

if (key > myIntArray.Length)
    key = key % myIntArray.Length;

// Original Array.
Console.Write("\nOriginal Array\t: ");
for (int j = 0; j < myIntArray.Length; j++)
{
    Console.Write(myIntArray[j].ToString() + " ");
}

for (int i = myIntArray.Length - 1; i >= 0; i--)
{
    myArray[(i + key) % myArray.Length] = myIntArray[(i)];
}

Console.Write("\nOutput Array\t: ");
for (int j = 0; j < myArray.Length; j++)
{
    Console.Write(myArray[j].ToString() + " ");
}
            
Console.Write("\n\nPress any key to exit...");
Console.ReadKey();

Edit: Code Corrected...

@Arithma:
1- In the case of a negative number, the result is the same as the positive shifting by a value of (length + negative key).
EX: At a shift Parameter of -2, the result is the same as a shift parameter of 4. (length + negative key)
(6 + (-2) = 4).

2- For a shift parameter larger than the length of the array, it's just enough to do this:
Key = Key % array.length

arithma

George I don't think your algorithm is correct. I tried it with a key value of 2 and -2. I got weird incorrect results.
For key = 2:

Original Array : 0 1 2 3 4 5

Swap (5 - 1) : 0 5 2 3 4 1
Swap (4 - 0) : 4 5 2 3 0 1
Swap (3 - 5) : 4 5 2 5 0 3
Swap (2 - 4) : 4 5 4 5 2 3
Swap (1 - 3) : 4 3 4 1 2 3
Swap (0 - 2) : 2 3 0 1 2 3

Output Array : 2 3 0 1 2 3

Additionally you ought to cater for cases where key < 0 and Abs(key)>length_of_array.

Let me also raise the bar a bit higher with this requirement:
Return the minimum number of swaps necessary to do the shift operation, and the corresponding swaps.

mesa177

Matlab with circshift command:

clear all
clc

fid = fopen('Circular Shift input.txt'); % Open file where input arrays and
                                         % circular shift key are located
C = {};                           % Cell to store input arrays
SK = [];                          % Array to store shift keys
flag = 1;                         % Flag to indicate whether shift key or
                                  % array is being extracted
fresult = {};                     % Cell to store shifted arrays
n = 1;
while ~feof(fid)                  % Read input arrays until end of file     
    tline = fgetl(fid);           % Read current line
    if mod(flag,2)                % Shift key is being identified
       flag = flag + 1;
       k = 0;                     % Identify shift left or right
       if (k+1 < length(tline))
           while ~isequal(tline(k+1),' ') 
                 k = k + 1;
           end
       else
           error('Wrong input for demanding circular shift.');
       end
       tline = tline(k+2:end);
       if isequal('-',tline(1))
           SK(n) = str2double(tline(2:end))*(-1);
           disp('Shift to left');
       else 
           SK(n) = str2double(tline);
           if ~SK(n)
               disp('No shift performed');
           else
               disp('Shift to right');
           end
       end
       n = n + 1;
    else
       flag = flag + 1;
       k = 0;                     % Identify input array
       if (k+1 < length(tline))
           while ~isequal(tline(k+1),' ') 
                 k = k + 1;
           end
       else
           error('Wrong entry of input array.');
       end
       tline = tline(k+2:end);
       cnt = 1;
       while ~isempty(tline)
             k = 0;
             if (k+1 < length(tline))
                 while (k < length(tline))&&(~isequal(tline(k+1),' ')) 
                       k = k + 1;
                 end
             else
                 k = 1;
             end
             C{n-1}(cnt) = str2double(tline(1:k)); 
             cnt = cnt + 1;
             if (length(tline) > 1)
                 tline = tline(k+2:end);
             else
                 tline = [];
             end
       end
       if (abs(SK(n-1)) > length(C{n-1}))
           error('Shift cannot be performed. Key size exceeds length of array.');
       else                       % Peforming circular shift
           fresult{n-1} = circshift(C{n-1},[0,SK(n-1)]);
       end
       disp('The resulting shifted array is:');
       disp(num2str(fresult{n-1}));
    end
end
status = fclose(fid);             % Close file

Matlab with array concatenations:

clear all
clc

fid = fopen('Circular Shift input.txt'); % Open file where input arrays and
                                         % circular shift key are located
C = {};                           % Cell to store input arrays
SK = [];                          % Array to store shift keys
flag = 1;                         % Flag to indicate whether shift key or
                                  % array is being extracted
fresult = {};                     % Cell to store shifted arrays
n = 1;
while ~feof(fid)                  % Read input arrays until end of file     
    tline = fgetl(fid);           % Read current line
    if mod(flag,2)                % Shift key is being identified
       flag = flag + 1;
       k = 0;                     % Identify shift left or right
       if (k+1 < length(tline))
           while ~isequal(tline(k+1),' ') 
                 k = k + 1;
           end
       else
           error('Wrong input for demanding circular shift.');
       end
       tline = tline(k+2:end);
       if isequal('-',tline(1))
           SK(n) = str2double(tline(2:end))*(-1);
           disp('Shift to left');
       else 
           SK(n) = str2double(tline);
           if ~SK(n)
               disp('No shift performed');
           else
               disp('Shift to right');
           end
       end
       n = n + 1;
    else
       flag = flag + 1;
       k = 0;                     % Identify input array
       if (k+1 < length(tline))
           while ~isequal(tline(k+1),' ') 
                 k = k + 1;
           end
       else
           error('Wrong entry of input array.');
       end
       tline = tline(k+2:end);
       cnt = 1;
       while ~isempty(tline)
             k = 0;
             if (k+1 < length(tline))
                 while (k < length(tline))&&(~isequal(tline(k+1),' ')) 
                       k = k + 1;
                 end
             else
                 k = 1;
             end
             C{n-1}(cnt) = str2double(tline(1:k)); 
             cnt = cnt + 1;
             if (length(tline) > 1)
                 tline = tline(k+2:end);
             else
                 tline = [];
             end
       end
       if (abs(SK(n-1)) > length(C{n-1}))
           error('Shift cannot be performed. Key size exceeds length of array.');
       elseif (SK(n-1) > 0)       % Peforming circular shift
           fresult{n-1} = horzcat(C{n-1}(end-SK(n-1)+1:end),C{n-1}(1:end-SK(n-1)));
       elseif ~SK(n-1)
           fresult{n-1} = C{n-1};
       else
           tS = length(C{n-1}) + SK(n-1);
           fresult{n-1} = horzcat(C{n-1}(end-tS+1:end),C{n-1}(1:end-tS));
       end
       disp('The resulting shifted array is:');
       disp(num2str(fresult{n-1}));
    end
end
status = fclose(fid);             % Close file

Example:

rotate: 3
array: 0 1 2 3 4 5 6
rotate: -2
array: 0 1 2 3 4 5 6 7 8 9 10

Answer:
Shift to right
The resulting shifted array is:
4 5 6 0 1 2 3
Shift to left
The resulting shifted array is:
2 3 4 5 6 7 8 9 10 0 1

Still editing my swapping algorithm, found a good way to swap entries on arrays which have an odd number of entries and the number of swaps performed is length(array)-1 (for first example given it is 6) no matter how the shift is performed (to the right, to the left, a shift key of 1, 2, 3, etc...). Suddenly, I find out that I can decrease the number of swapping processes for specific shift keys. So the consistency I found suddenly crumbled :(
As for the even number of entries, the previously developed algorithm matches it so far, but there's one minor change done to it.

mesa177

This is where I got so far in the swapping:

clear all
clc

fid = fopen('Circular Shift input.txt'); % Open file where input arrays and
                                         % circular shift key are located
C = {};                           % Cell to store input arrays
SK = [];                          % Array to store shift keys
flag = 1;                         % Flag to indicate whether shift key or
                                  % array is being extracted
fresult = {};                     % Cell to store shifted arrays
n = 1;
while ~feof(fid)                  % Read input arrays until end of file     
    tline = fgetl(fid);           % Read current line
    if mod(flag,2)                % Shift key is being identified
       flag = flag + 1;
       k = 0;                     % Identify shift left or right
       if (k+1 < length(tline))
           while ~isequal(tline(k+1),' ') 
                 k = k + 1;
           end
       else
           error('Wrong input for demanding circular shift.');
       end
       tline = tline(k+2:end);
       if isequal('-',tline(1))
           SK(n) = str2double(tline(2:end))*(-1);
           disp('Shift to left');
       else 
           SK(n) = str2double(tline);
           if ~SK(n)
               disp('No shift performed');
           else
               disp('Shift to right');
           end
       end
       n = n + 1;
    else
       flag = flag + 1;
       k = 0;                     % Identify input array
       if (k+1 < length(tline))
           while ~isequal(tline(k+1),' ') 
                 k = k + 1;
           end
       else
           error('Wrong entry of input array.');
       end
       tline = tline(k+2:end);
       cnt = 1;
       while ~isempty(tline)
             k = 0;
             if (k+1 < length(tline))
                 while (k < length(tline))&&(~isequal(tline(k+1),' ')) 
                       k = k + 1;
                 end
             else
                 k = 1;
             end
             C{n-1}(cnt) = str2double(tline(1:k)); 
             cnt = cnt + 1;
             if (length(tline) > 1)
                 tline = tline(k+2:end);
             else
                 tline = [];
             end
       end
       if (abs(SK(n-1)) > length(C{n-1}))
           error('Shift cannot be performed. Key size exceeds length of array.');
       elseif (SK(n-1) > 0)       % Peforming circular shift
           N = SK(n-1);
           fresult{n-1} = C{n-1};
           if mod(length(C{n-1}),2)
              if (N <= (length(C{n-1})-1)/2)
                  for i = 1:length(C{n-1})-1
                      if isequal(N,SK(n-1))
                         N = 1;
                      else
                         N = N + 1;
                      end
                      temp = fresult{n-1}(i);
                      fresult{n-1}(i) = fresult{n-1}(end - SK(n-1) + N);
                      fresult{n-1}(end - SK(n-1) + N) = temp;
                      disp(strcat('Step',num2str(i),': Swap (',num2str(i),...
                           ',',num2str(length(C{n-1}) - SK(n-1) + N),')'));
                      disp(num2str(fresult{n-1}));
                  end
              else
                  for i = 1:length(C{n-1})-1
                      if isequal(N,SK(n-1))
                         N = 1;
                      else
                         N = N + 1;
                      end
                      if (i <= SK(n-1))
                         temp = fresult{n-1}(i);
                         fresult{n-1}(i) = fresult{n-1}(end - SK(n-1) + N);
                         fresult{n-1}(end - SK(n-1) + N) = temp;
                         disp(strcat('Step',num2str(i),': Swap (',...
                             num2str(i),',',...
                             num2str(length(C{n-1}) - SK(n-1) + N),')'));
                         disp(num2str(fresult{n-1}));
                      else
                         temp = fresult{n-1}(i);
                         fresult{n-1}(i) = fresult{n-1}(end);
                         fresult{n-1}(end) = temp;
                         disp(strcat('Step',num2str(i),': Swap (',...
                             num2str(i),',',num2str(length(C{n-1})),')'));
                         disp(num2str(fresult{n-1}));
                      end 
                  end
              end
           else
              if (N <= (length(C{n-1})-1)/2)
                  for i = 1:length(C{n-1})-SK(n-1)
                      if isequal(N,SK(n-1))
                         N = 1;
                      else
                         N = N + 1;
                      end
                      temp = fresult{n-1}(i);
                      fresult{n-1}(i) = fresult{n-1}(end - SK(n-1) + N);
                      fresult{n-1}(end - SK(n-1) + N) = temp;
                      disp(strcat('Step',num2str(i),': Swap (',num2str(i),...
                           ',',num2str(length(C{n-1}) - SK(n-1) + N),')'));
                      disp(num2str(fresult{n-1}));
                  end
              else
                  for i = 1:SK(n-1)
                      if isequal(N,SK(n-1))
                         N = 1;
                      else
                         N = N + 1;
                      end
                      temp = fresult{n-1}(i);
                      fresult{n-1}(i) = fresult{n-1}(end - SK(n-1) + N);
                      fresult{n-1}(end - SK(n-1) + N) = temp;
                      disp(strcat('Step',num2str(i),': Swap (',num2str(i),...
                           ',',num2str(length(C{n-1}) - SK(n-1) + N),')'));
                      disp(num2str(fresult{n-1})); 
                  end
              end
           end
       elseif ~SK(n-1)
           fresult{n-1} = C{n-1};
       else
           tS = length(C{n-1}) + SK(n-1);
           N = tS;
           fresult{n-1} = C{n-1};
           if mod(length(C{n-1}),2)
              if (N <= (length(C{n-1})-1)/2)
                  for i = 1:length(C{n-1})-1
                      if isequal(N,tS)
                         N = 1;
                      else
                         N = N + 1;
                      end
                      temp = fresult{n-1}(i);
                      fresult{n-1}(i) = fresult{n-1}(end - tS + N);
                      fresult{n-1}(end - tS + N) = temp;
                      disp(strcat('Step',num2str(i),': Swap (',num2str(i),...
                           ',',num2str(length(C{n-1}) - tS + N),')'));
                      disp(num2str(fresult{n-1}));
                  end
              else
                  for i = 1:length(C{n-1})-1
                      if isequal(N,tS)
                         N = 1;
                      else
                         N = N + 1;
                      end
                      if (i <= tS)
                         temp = fresult{n-1}(i);
                         fresult{n-1}(i) = fresult{n-1}(end - tS + N);
                         fresult{n-1}(end - tS + N) = temp;
                         disp(strcat('Step',num2str(i),': Swap (',...
                             num2str(i),',',...
                             num2str(length(C{n-1}) - tS + N),')'));
                         disp(num2str(fresult{n-1}));
                      else
                         temp = fresult{n-1}(i);
                         fresult{n-1}(i) = fresult{n-1}(end);
                         fresult{n-1}(end) = temp;
                         disp(strcat('Step',num2str(i),': Swap (',...
                             num2str(i),',',num2str(length(C{n-1})),')'));
                         disp(num2str(fresult{n-1}));
                      end 
                  end
              end
           else
              if (N <= (length(C{n-1})-1)/2)
                  for i = 1:length(C{n-1})-tS
                      if isequal(N,tS)
                         N = 1;
                      else
                         N = N + 1;
                      end
                      temp = fresult{n-1}(i);
                      fresult{n-1}(i) = fresult{n-1}(end - tS + N);
                      fresult{n-1}(end - tS + N) = temp;
                      disp(strcat('Step',num2str(i),': Swap (',num2str(i),...
                           ',',num2str(length(C{n-1}) - tS + N),')'));
                      disp(num2str(fresult{n-1}));
                  end
              else
                  for i = 1:tS
                      if isequal(N,tS)
                         N = 1;
                      else
                         N = N + 1;
                      end
                      temp = fresult{n-1}(i);
                      fresult{n-1}(i) = fresult{n-1}(end - tS + N);
                      fresult{n-1}(end - tS + N) = temp;
                      disp(strcat('Step',num2str(i),': Swap (',num2str(i),...
                           ',',num2str(length(C{n-1}) - tS + N),')'));
                      disp(num2str(fresult{n-1})); 
                  end
              end
           end
       end
       disp('The resulting shifted array is:');
       disp(num2str(fresult{n-1}));
    end
end
status = fclose(fid);             % Close file

Of course some of the lines can be placed in functions to minimize the code length of the main program, but I'm too lazy to generate them for now :P

Example:
rotate: -2
array: 0 1 2 3 4 5 6 7
rotate: 6
array: 0 1 2 3 4 5 6 7 8 9 10

Answer:
Shift to left
Step1: Swap (1,3)
2 1 0 3 4 5 6 7
Step2: Swap (2,4)
2 3 0 1 4 5 6 7
Step3: Swap (3,5)
2 3 4 1 0 5 6 7
Step4: Swap (4,6)
2 3 4 5 0 1 6 7
Step5: Swap (5,7)
2 3 4 5 6 1 0 7
Step6: Swap (6,8)
2 3 4 5 6 7 0 1
The resulting shifted array is:
2 3 4 5 6 7 0 1
Shift to right
Step1: Swap (1,6)
5 1 2 3 4 0 6 7 8 9 10
Step2: Swap (2,7)
5 6 2 3 4 0 1 7 8 9 10
Step3: Swap (3,8)
5 6 7 3 4 0 1 2 8 9 10
Step4: Swap (4,9)
5 6 7 8 4 0 1 2 3 9 10
Step5: Swap (5,10)
5 6 7 8 9 0 1 2 3 4 10
Step6: Swap (6,11)
5 6 7 8 9 10 1 2 3 4 0
Step7: Swap (7,11)
5 6 7 8 9 10 0 2 3 4 1
Step8: Swap (8,11)
5 6 7 8 9 10 0 1 3 4 2
Step9: Swap (9,11)
5 6 7 8 9 10 0 1 2 4 3
Step10: Swap (10,11)
5 6 7 8 9 10 0 1 2 3 4
The resulting shifted array is:
5 6 7 8 9 10 0 1 2 3 4

Joe

A C implementation of swapping that does not declare more variables:

#include <stdlib.h>
#include <stdio.h>
#define ARRAY_SIZE 6

void init_array(int* array, int size)
{
    int i = 0;

    for (i=0; i<size; i++)
    {
        array[i] = i;
    }
}

void print_array (int* array, int size)
{
    int i = 0;
    for (i=0; i<size; i++)
    {
        printf ("%d\t", array[i]);
    }

    printf("\n");
}

void rotate_array (int* array, int size, int param)
{
   int i, j;
 
   for (i = 1; i <= param; i++)
   {
     for (j = size-1; j > 0; j--)
     {
        array[j-1] = array[j-1] + array[j];
        array[j] = array[j-1] - array[j];
        array[j-1] = array[j-1] - array[j];
     }
    }
}
        

int main (int argc, char** argv)
{
    int array[ARRAY_SIZE];
    int i;

    init_array(array, ARRAY_SIZE);

    rotate_array(array, ARRAY_SIZE, 2);    


    print_array (array, ARRAY_SIZE);    
    printf("\n");

    return 0;

}

Focus on the rotate_array() function. Items are swapped one by one. This method, though mathematical, has some computer limitations as array[j-1] + array[j could overflow. You could also use a boolean xor operation. This has been discussed in previous post.

I will try to output the pairs tomorrow.

arithma

This method, though mathematical, has some computer limitations as array[j-1] + array[j could overflow

To put the butter on the toast, you gotta keep in mind: int overflow is not defined in C++ (or perhaps it is just compiler specific, which can be good for different reasons). unsigned int overflow is defined, and the numbers just overlap. So if you cast whatever you need into int swap them and cast back you should be save with the plus and minus swap.

I really can't wrap my head around all your code mesa. It's just too much. Can you give out some psuedocode? In addition there's too much code on one hand, and too little swaps on the other hand, are there just too many switch conditions?

A litmus test for your algorithm: How many swaps approximately will there be for shifting a 1 million integers (~3.18MB) through these shifts: -1000, +1000, -100 000, +100 000.
I'll post a new exercise that may shed light on a particular special implementation that's very optimized for this swap thing.

Joe

To put the butter on the toast, you gotta keep in mind: int overflow is not defined in C++ (or perhaps it is just compiler specific, which can be good for different reasons). unsigned int overflow is defined, and the numbers just overlap. So if you cast whatever you need into int swap them and cast back you should be save with the plus and minus swap.

I'm guessing you're talking about the extra bit used for signs (as opposed to unsigned variables). Am I correct?

arithma

Here's the related exercise I was talking about: http://www.lebgeeks.com/forums/viewtopic.php?id=7584

@rahmu:
It's related, yes. Some C++ compilers may convert an int overflow into a saturated value (especially when dealing with digital signal processing). The standard leaves it up to the implementers to decide what fits and makes it easier for the domain. However the overflow behavior of an unsigned int is very well defined (wrap around the integer domain) and is compatible with your swap function (so even if it does overflow, it will still behave correctly). Do note that: the operators themselves take more memory than they save by removing the variable, and more so, the compiler may optimize out a temp value and replace the whole thing with an XCHANGE op code. It's always better to tell the compiler what is your intent rather than microoptimizing an algorithm (or at least it's suggested that you do as such, and if you care that much about that last bit of memory, why are you not using assembly to start with.. People developing high performance applications usually do optimize code that is called the most to assembly occasionally if the compiler doesn't take the hint... Think custom memory allocation for a VM (be it an environment or an OS virtualization system) and the likes..)

arithma

@mesa: I rechecked how your algorithm is working from the swaps, and I think I get the gist of it. You are mostly dividing the problem into two subparts. Shifting members around until you hit the max element, then you'd reverse the resulting array that you is left unoperated on.

I don't have matlab installed here, can you try this input and print the resulting swaps as well:
array: 0 1 2 3 4 5 6 7 8
shift: -2

arithma

EX: At a shift Parameter of -2, the result is the same as a shift parameter of 4. (length + negative key)
(6 + (-2) = 4).

@George: What if the shift parameter is -1000? 6 + (-1000) = -994.
You should: ((k%n)+n)%k. This will solve all your troubles.
k%n belongs to (-n, n). This an open interval.
(k%n)+n belongs to (0, 2n)
((k%n)+n)%k belongs to [0, n). Capiche?

mesa177

Ok, so I added an enhancement and some extra comments to help (hopefully) in realizing the algorithm behind the swapping:

clear all
clc

fid = fopen('Circular Shift input.txt'); % Open file where input arrays and
                                         % circular shift key are located
C = {};                           % Cell to store input arrays
SK = [];                          % Array to store shift keys
flag = 1;                         % Flag to indicate whether shift key or
                                  % array is being extracted
fresult = {};                     % Cell to store shifted arrays
n = 1;
while ~feof(fid)                  % Read input arrays until end of file     
    tline = fgetl(fid);           % Read current line
    if mod(flag,2)                % Shift key is being identified
       flag = flag + 1;
       k = 0;                     % Identify shift left or right
       if (k+1 < length(tline))
           while ~isequal(tline(k+1),' ') 
                 k = k + 1;
           end
       else
           error('Wrong input for demanding circular shift.');
       end
       tline = tline(k+2:end);
       if isequal('-',tline(1))
           SK(n) = str2double(tline(2:end))*(-1);
           disp('Shift to left');
       else 
           SK(n) = str2double(tline);
           if ~SK(n)
               disp('No shift performed');
           else
               disp('Shift to right');
           end
       end
       n = n + 1;
    else
       flag = flag + 1;
       k = 0;                     % Identify input array
       if (k+1 < length(tline))
           while ~isequal(tline(k+1),' ') 
                 k = k + 1;
           end
       else
           error('Wrong entry of input array.');
       end
       tline = tline(k+2:end);
       cnt = 1;
       while ~isempty(tline)
             k = 0;
             if (k+1 < length(tline))
                 while (k < length(tline))&&(~isequal(tline(k+1),' ')) 
                       k = k + 1;
                 end
             else
                 k = 1;
             end
             C{n-1}(cnt) = str2double(tline(1:k)); 
             cnt = cnt + 1;
             if (length(tline) > 1)
                 tline = tline(k+2:end);
             else
                 tline = [];
             end
       end
       if (abs(SK(n-1)) > length(C{n-1}))
          % Key size exceeds length of array
          if (SK(n-1) > 0)
              SK(n-1) = mod(SK(n-1),length(C{n-1}));
          else
              SK(n-1) = -mod(abs(SK(n-1)),length(C{n-1}));
          end
       end
       if (SK(n-1) > 0)       % Peforming circular shift
           N = SK(n-1);
           fresult{n-1} = C{n-1};
           if mod(length(C{n-1}),2) % Array has an odd number of entries
              if (N <= (length(C{n-1})-1)/2) % Key is smaller than or equal to half the size of the array
                  for i = 1:length(C{n-1})-1
                      if isequal(N,SK(n-1))
                         N = 1;
                      else
                         N = N + 1;
                      end
                      temp = fresult{n-1}(i);
                      fresult{n-1}(i) = fresult{n-1}(end - SK(n-1) + N);
                      fresult{n-1}(end - SK(n-1) + N) = temp;
                      disp(strcat('Step',num2str(i),': Swap (',num2str(i),...
                           ',',num2str(length(C{n-1}) - SK(n-1) + N),')'));
                      disp(num2str(fresult{n-1}));
                  end
              else % Key is greater than half the size of the array
                  for i = 1:length(C{n-1})-1
                      if isequal(N,SK(n-1))
                         N = 1;
                      else
                         N = N + 1;
                      end
                      if (i <= SK(n-1))
                         temp = fresult{n-1}(i);
                         fresult{n-1}(i) = fresult{n-1}(end - SK(n-1) + N);
                         fresult{n-1}(end - SK(n-1) + N) = temp;
                         disp(strcat('Step',num2str(i),': Swap (',...
                             num2str(i),',',...
                             num2str(length(C{n-1}) - SK(n-1) + N),')'));
                         disp(num2str(fresult{n-1}));
                      else
                         temp = fresult{n-1}(i);
                         fresult{n-1}(i) = fresult{n-1}(end);
                         fresult{n-1}(end) = temp;
                         disp(strcat('Step',num2str(i),': Swap (',...
                             num2str(i),',',num2str(length(C{n-1})),')'));
                         disp(num2str(fresult{n-1}));
                      end 
                  end
              end
           else % Array has an even number of entries
              if (N <= (length(C{n-1})-1)/2) % Key is smaller than or equal to half the size of the array
                  for i = 1:length(C{n-1})-SK(n-1)
                      if isequal(N,SK(n-1))
                         N = 1;
                      else
                         N = N + 1;
                      end
                      temp = fresult{n-1}(i);
                      fresult{n-1}(i) = fresult{n-1}(end - SK(n-1) + N);
                      fresult{n-1}(end - SK(n-1) + N) = temp;
                      disp(strcat('Step',num2str(i),': Swap (',num2str(i),...
                           ',',num2str(length(C{n-1}) - SK(n-1) + N),')'));
                      disp(num2str(fresult{n-1}));
                  end
              else % Key is greater than half the size of the array
                  for i = 1:SK(n-1)
                      if isequal(N,SK(n-1))
                         N = 1;
                      else
                         N = N + 1;
                      end
                      temp = fresult{n-1}(i);
                      fresult{n-1}(i) = fresult{n-1}(end - SK(n-1) + N);
                      fresult{n-1}(end - SK(n-1) + N) = temp;
                      disp(strcat('Step',num2str(i),': Swap (',num2str(i),...
                           ',',num2str(length(C{n-1}) - SK(n-1) + N),')'));
                      disp(num2str(fresult{n-1})); 
                  end
              end
           end
       elseif ~SK(n-1)
           fresult{n-1} = C{n-1};
       else
           tS = length(C{n-1}) + SK(n-1);
           N = tS;
           fresult{n-1} = C{n-1};
           if mod(length(C{n-1}),2) % Array has an odd number of entries
              if (N <= (length(C{n-1})-1)/2) % Key is smaller than or equal to half the size of the array
                  for i = 1:length(C{n-1})-1
                      if isequal(N,tS)
                         N = 1;
                      else
                         N = N + 1;
                      end
                      temp = fresult{n-1}(i);
                      fresult{n-1}(i) = fresult{n-1}(end - tS + N);
                      fresult{n-1}(end - tS + N) = temp;
                      disp(strcat('Step',num2str(i),': Swap (',num2str(i),...
                           ',',num2str(length(C{n-1}) - tS + N),')'));
                      disp(num2str(fresult{n-1}));
                  end
              else % Key is greater than half the size of the array
                  for i = 1:length(C{n-1})-1
                      if isequal(N,tS)
                         N = 1;
                      else
                         N = N + 1;
                      end
                      if (i <= tS)
                         temp = fresult{n-1}(i);
                         fresult{n-1}(i) = fresult{n-1}(end - tS + N);
                         fresult{n-1}(end - tS + N) = temp;
                         disp(strcat('Step',num2str(i),': Swap (',...
                             num2str(i),',',...
                             num2str(length(C{n-1}) - tS + N),')'));
                         disp(num2str(fresult{n-1}));
                      else
                         temp = fresult{n-1}(i);
                         fresult{n-1}(i) = fresult{n-1}(end);
                         fresult{n-1}(end) = temp;
                         disp(strcat('Step',num2str(i),': Swap (',...
                             num2str(i),',',num2str(length(C{n-1})),')'));
                         disp(num2str(fresult{n-1}));
                      end 
                  end
              end
           else % Array has an even number of entries
              if (N <= (length(C{n-1})-1)/2) % Key is smaller than or equal to half the size of the array
                  for i = 1:length(C{n-1})-tS
                      if isequal(N,tS)
                         N = 1;
                      else
                         N = N + 1;
                      end
                      temp = fresult{n-1}(i);
                      fresult{n-1}(i) = fresult{n-1}(end - tS + N);
                      fresult{n-1}(end - tS + N) = temp;
                      disp(strcat('Step',num2str(i),': Swap (',num2str(i),...
                           ',',num2str(length(C{n-1}) - tS + N),')'));
                      disp(num2str(fresult{n-1}));
                  end
              else % Key is greater than half the size of the array
                  for i = 1:tS
                      if isequal(N,tS)
                         N = 1;
                      else
                         N = N + 1;
                      end
                      temp = fresult{n-1}(i);
                      fresult{n-1}(i) = fresult{n-1}(end - tS + N);
                      fresult{n-1}(end - tS + N) = temp;
                      disp(strcat('Step',num2str(i),': Swap (',num2str(i),...
                           ',',num2str(length(C{n-1}) - tS + N),')'));
                      disp(num2str(fresult{n-1})); 
                  end
              end
           end
       end
       disp('The resulting shifted array is:');
       disp(num2str(fresult{n-1}));
    end
end
status = fclose(fid);             % Close file

Note that the most part of the code is reading a text file which has the shift keys and the input arrays entered:

while ~feof(fid)                  % Read input arrays until end of file     
    tline = fgetl(fid);           % Read current line
    if mod(flag,2)                % Shift key is being identified
       flag = flag + 1;
       k = 0;                     % Identify shift left or right
       if (k+1 < length(tline))
           while ~isequal(tline(k+1),' ') 
                 k = k + 1;
           end
       else
           error('Wrong input for demanding circular shift.');
       end
       tline = tline(k+2:end);
       if isequal('-',tline(1))
           SK(n) = str2double(tline(2:end))*(-1);
           disp('Shift to left');
       else 
           SK(n) = str2double(tline);
           if ~SK(n)
               disp('No shift performed');
           else
               disp('Shift to right');
           end
       end
       n = n + 1;
    else
       flag = flag + 1;
       k = 0;                     % Identify input array
       if (k+1 < length(tline))
           while ~isequal(tline(k+1),' ') 
                 k = k + 1;
           end
       else
           error('Wrong entry of input array.');
       end
       tline = tline(k+2:end);
       cnt = 1;
       while ~isempty(tline)
             k = 0;
             if (k+1 < length(tline))
                 while (k < length(tline))&&(~isequal(tline(k+1),' ')) 
                       k = k + 1;
                 end
             else
                 k = 1;
             end
             C{n-1}(cnt) = str2double(tline(1:k)); 
             cnt = cnt + 1;
             if (length(tline) > 1)
                 tline = tline(k+2:end);
             else
                 tline = [];
             end
       end
...

This is the enhancement made for when the shift key is greater than the size of the array:

if (abs(SK(n-1)) > length(C{n-1}))
          % Key size exceeds length of array
          if (SK(n-1) > 0)
              SK(n-1) = mod(SK(n-1),length(C{n-1}));
          else
              SK(n-1) = -mod(abs(SK(n-1)),length(C{n-1}));
          end
       end

As for the jist of the code, it lies here (note that the same code is used for a shift key with a negative value but the shift is done according to "length(array) + shift key negative value" because as George pointed out previously a shift to the left is the same as a shift to the right by a shift key of "length(array) + shift key negative value"):

if (SK(n-1) > 0)       % Peforming circular shift
           N = SK(n-1);
           fresult{n-1} = C{n-1};
           if mod(length(C{n-1}),2) % Array has an odd number of entries
              if (N <= (length(C{n-1})-1)/2) % Key is smaller than or equal to half the size of the array
                  for i = 1:length(C{n-1})-1
                      if isequal(N,SK(n-1))
                         N = 1;
                      else
                         N = N + 1;
                      end
                      temp = fresult{n-1}(i);
                      fresult{n-1}(i) = fresult{n-1}(end - SK(n-1) + N);
                      fresult{n-1}(end - SK(n-1) + N) = temp;
                      disp(strcat('Step',num2str(i),': Swap (',num2str(i),...
                           ',',num2str(length(C{n-1}) - SK(n-1) + N),')'));
                      disp(num2str(fresult{n-1}));
                  end
              else % Key is greater than half the size of the array
                  for i = 1:length(C{n-1})-1
                      if isequal(N,SK(n-1))
                         N = 1;
                      else
                         N = N + 1;
                      end
                      if (i <= SK(n-1))
                         temp = fresult{n-1}(i);
                         fresult{n-1}(i) = fresult{n-1}(end - SK(n-1) + N);
                         fresult{n-1}(end - SK(n-1) + N) = temp;
                         disp(strcat('Step',num2str(i),': Swap (',...
                             num2str(i),',',...
                             num2str(length(C{n-1}) - SK(n-1) + N),')'));
                         disp(num2str(fresult{n-1}));
                      else
                         temp = fresult{n-1}(i);
                         fresult{n-1}(i) = fresult{n-1}(end);
                         fresult{n-1}(end) = temp;
                         disp(strcat('Step',num2str(i),': Swap (',...
                             num2str(i),',',num2str(length(C{n-1})),')'));
                         disp(num2str(fresult{n-1}));
                      end 
                  end
              end
           else % Array has an even number of entries
              if (N <= (length(C{n-1})-1)/2) % Key is smaller than or equal to half the size of the array
                  for i = 1:length(C{n-1})-SK(n-1)
                      if isequal(N,SK(n-1))
                         N = 1;
                      else
                         N = N + 1;
                      end
                      temp = fresult{n-1}(i);
                      fresult{n-1}(i) = fresult{n-1}(end - SK(n-1) + N);
                      fresult{n-1}(end - SK(n-1) + N) = temp;
                      disp(strcat('Step',num2str(i),': Swap (',num2str(i),...
                           ',',num2str(length(C{n-1}) - SK(n-1) + N),')'));
                      disp(num2str(fresult{n-1}));
                  end
              else % Key is greater than half the size of the array
                  for i = 1:SK(n-1)
                      if isequal(N,SK(n-1))
                         N = 1;
                      else
                         N = N + 1;
                      end
                      temp = fresult{n-1}(i);
                      fresult{n-1}(i) = fresult{n-1}(end - SK(n-1) + N);
                      fresult{n-1}(end - SK(n-1) + N) = temp;
                      disp(strcat('Step',num2str(i),': Swap (',num2str(i),...
                           ',',num2str(length(C{n-1}) - SK(n-1) + N),')'));
                      disp(num2str(fresult{n-1})); 
                  end
              end
           end
...

For the example you gave me Skafi:

rotate: -2
array: 0 1 2 3 4 5 6 7 8

The answer would be:
Shift to left
Step1: Swap (1,3)
2 1 0 3 4 5 6 7 8
Step2: Swap (2,4)
2 3 0 1 4 5 6 7 8
Step3: Swap (3,5)
2 3 4 1 0 5 6 7 8
Step4: Swap (4,6)
2 3 4 5 0 1 6 7 8
Step5: Swap (5,7)
2 3 4 5 6 1 0 7 8
Step6: Swap (6,8)
2 3 4 5 6 7 0 1 8
Step7: Swap (7,9)
2 3 4 5 6 7 8 1 0
Step8: Swap (8,9)
2 3 4 5 6 7 8 0 1
The resulting shifted array is:
2 3 4 5 6 7 8 0 1

However, this example doesn't show the power of the algorithm developed because the minimum number of operations required to conduct the shift is length(array)-1 = 8.

For this example:
rotate: 3
array: 0 1 2 3 4 5

The answer is:
Shift to right
Step1: Swap (1,4)
3 1 2 0 4 5
Step2: Swap (2,5)
3 4 2 0 1 5
Step3: Swap (3,6)
3 4 5 0 1 2
The resulting shifted array is:
3 4 5 0 1 2

So instead of needing length(array)-1 = 6 steps of swapping, only 3 are required => minimum steps required to conduct the shift.

mesa177

Semi version of pseudo-code (will not compile properly with Matlab, to do so use above code)

  % Peforming circular shift
           N = key; % key is either the entered positive shift key or length(array) + negative shift key
           shiftedArray = array;
           if mod(length(array),2) % Array has an odd number of entries
              if (N <= (length(array)-1)/2) % Key is smaller than or equal to half the size of the array
                  for i = 1:length(array)-1
                      if isequal(N,key) % Used pattern to select entry to be swapped
                         N = 1;
                      else
                         N = N + 1;
                      end
                      temp = shiftedArray(i); % Swap entry values
                      shiftedArray(i) = shiftedArray(end - key + N); % end resembles last entry on array
                      shiftedArray(end - key + N) = temp;
                      display "Step number: Swap (entry1,entry2)"; % that's what the jargon does in the
                      display shiftedArray;                        % original code
                  end
              else % Key is greater than half the size of the array
                  for i = 1:length(array)-1
                      if isequal(N,key) % Used pattern to select entry to be swapped
                         N = 1;
                      else
                         N = N + 1;
                      end
                      if (i <= key) % Change of selected pattern of entry swapping 
                         temp = shiftedArray(i); % Swap entry values
                         shiftedArray(i) = shiftedArray(end - key + N); % <= notice the index change =
                         shiftedArray(end - key + N) = temp;                                         %
                         display "Step number: Swap (entry1,entry2)";                                %
                         display shiftedArray;                                                       %
                      else                                                                           %
                         temp = shiftedArray(i); % Swap entry values                                 %
                         shiftedArray(i) = shiftedArray(end);           % <==========================%
                         shiftedArray(end) = temp;
                         display "Step number: Swap (entry1,entry2)";                                
                         display shiftedArray;
                      end 
                  end
              end
           else % Array has an even number of entries
              if (N <= (length(array)-1)/2) % Key is smaller than or equal to half the size of the array
                  for i = 1:length(array)-key % <= change in number of looping i.e. swapping repetitions =
                      if isequal(N,key)                                                                  %
                         N = 1;                                                                          %
                      else                                                                               %
                         N = N + 1;                                                                      %
                      end                                                                                %
                      temp = shiftedArray(i); % Swap entry values                                        %
                      shiftedArray(i) = shiftedArray(end - key + N);                                     %
                      shiftedArray(end - key + N) = temp;                                                %
                      display "Step number: Swap (entry1,entry2)";                                       % 
                      display shiftedArray;                                                              %
                  end                                                                                    %
              else % Key is greater than half the size of the array                                      %
                  for i = 1:key % <======================================================================%
                      if isequal(N,key)
                         N = 1;
                      else
                         N = N + 1;
                      end
                      temp = shiftedArray(i); % Swap entry values                                        
                      shiftedArray(i) = shiftedArray(end - key + N);                                     
                      shiftedArray(end - key + N) = temp;                                                
                      display "Step number: Swap (entry1,entry2)";                                        
                      display shiftedArray; 
                  end
              end
           end

mesa177

Now, if you run the code for some shift keys, you will notice erroneous results in the swapping process (either exceeding the number of swapping steps or requiring more swapping steps).

These are the shift keys that give wrong swapping results (tested for arrays with lengths reaching 15 entries):

(Format of writing: shift key bla gives error for arrays with bla entries)
key 3,5 for an array length of 8
key 6 for an array length of 9
key 3,4,5,6,7 for an array length of 10
key 3,4,7,8 for an array length of 11
key 5,6,7 for an array length of 12
key 5,8 for an array length of 13
key 3,4,5,6,8,9,10,11 for an array of length of 14
key 4,6,9,10,11,12 for an array of length of 15

No errors occur for arrays that have no more than 7 entries.

As you can see, there is no capability of logically tracing wrong shift key rotations.

Anyone care to point out something I've missed or has a better way for swapping with minimum steps acheived? (Yes, we can swap the last element over and over, but we won't have the minimum steps of swapping)

arithma

Hello all, I see Alaa has been quite busy with the exercise. I am glad you found the errors in your algorithm though it looks promising. After getting down my algorithm correctly, I researched a little and found an algo similar to what you're implementing.
Excuse me for not being able to parse all that much MATLAB to make sense of it. By the way, is it too much trouble to ask to code in C++? It's usually better to implement algorithms in an "atomic" language rather than one tuned for bulk operations like MATLAB (otherwise you'd end up hiding computational complexity and losing sight of the real value of a problem). However, in this exercise, I think the most trouble is our inability to read it so that to help you fast. I really hope you'd convert to C++ for many various reasons that we can talk about soon.