Rotate an array using LINQ syntax

Question

I am solving this problem of rotating an array and got algorithm and code working

 int[] Rotate(int[] ar,int k)
        {
            if (k <= 0 || k > ar.Length - 1)
                return ar;
            Reverse(ar, 0, k - 1);
            Reverse(ar, k, ar.Length - 1);
            Reverse(ar, 0, ar.Length - 1);
            return ar;            
        }

 void Reverse(int[] ar,int start, int end)
        {
            while (start < end)
            {
                int temp = ar[start];
                ar[start] = ar[end];
                ar[end] = temp;
                start++;
                end--;
            }
        }

Now I want to do this in LINQ and I got the below code, I think this can be done much better.

 int[] Rotate(int[] ar,int k)
    {
        if (k <= 0 || k > ar.Length - 1)
            return ar;
        int[] ar1=ar.Take(k-1).Reverse().ToArray();
        int[] ar2=ar.Skip(k - 1).Take(ar.Length - k+1).Reverse().ToArray();
        int[] ar3 = ar1.Concat(ar2).Reverse().ToArray();
        return ar3;
    }

This is a well known algorithm from Programming pearls - http://books.google.com/books?id=kse_7qbWbjsC&lpg=PA14&ots=DfzTzQCSar&dq=rotate%20an%20array%20programming%20pearls&pg=PA14#v=onepage&q&f=false

And in general how to develop my LINQ skills, if I am given a programming problem, right now I am only thinking in for loops or foreach loops, how to think in terms of linq operators. I am reading C# 4.0 nutshell, other than practicing any advice?

Answer 1

I'm not sure why you've got all the reversals, to be honest. How about this:

int[] Rotate(int[] ar,int k)
{
    if (k <= 0 || k > ar.Length - 1)
        return ar;
    return ar.Skip(k)            // Start with the last elements
             .Concat(ar.Take(k)) // Then the first elements
             .ToArray();         // Then make it an array
}

Here's a short but complete program to demonstrate it:

using System;
using System.Linq;

class Test
{
    static int[] Rotate(int[] ar,int k)
    {
        if (k <= 0 || k > ar.Length - 1)
            return ar;
        return ar.Skip(k)            // Start with the last elements
                 .Concat(ar.Take(k)) // Then the first elements
                 .ToArray();         // Then make it an array
    }

    static void Main()
    {
        int[] values = { 1, 2, 3, 4, 5 };
        int[] rotated = Rotate(values, 3);

        Console.WriteLine(string.Join(", ", rotated));
    }
}

Output: 4, 5, 1, 2, 3

EDIT: I've just noticed one major difference between my code and your original: yours modifies the original array - mine returns a new array with the rotated values. So would your LINQ code, but it means if you were testing my code with something that only looked at the original array, you wouldn't see the rotation.

LINQ is designed to work this way in general - it favours returning a new sequence over modifying an existing one.

Answer 2

Starting with your code:

int[] ar1=ar.Take(k-1).Reverse().ToArray(); 
int[] ar2=ar.Skip(k - 1).Take(ar.Length - k+1).Reverse().ToArray(); 
int[] ar3 = ar1.Concat(ar2).Reverse().ToArray(); 

Since you just want to get all of the remaining elements, the Take in the second line isn't needed.

ar1 and ar2 are just enumerated, so they don't need to be arrays. The ToArray calls aren't needed. With a bit of creative renaming thrown in, we have:

IEnumerable<int> revFirst = ar.Take(k-1).Reverse(); 
IEnumerable<int> revLast = ar.Skip(k-1).Reverse(); 
int[] ar3 = revFirst.Concat(revLast).Reverse().ToArray(); 

Now we have

rev ( rev(first) + rev(last) )

distributing the outer rev gives

rev ( rev(last) ) + rev ( rev(first) )

which is the same as

last + first

applying the same operations to the code gives

IEnumerable<int> first = ar.Take(k-1); 
IEnumerable<int> last = ar.Skip(k-1); 
int[] ar3 = last.Concat(first).ToArray(); 

which further simplifies to

int[] ar3 = ar.Skip(k-1).Concat(ar.Take(k-1)).ToArray(); 

and now we have Jon Skeet's answer so we must be done.