Easiest way to Rotate a List in c#

Question

Lists say I have a list List<int> {1,2,3,4,5}

Rotate means:

=> {2,3,4,5,1} => {3,4,5,1,2} => {4,5,1,2,3}

Maybe rotate is not the best word for this, but hope you understand what I means

My question, whats the easiest way (in short code, c# 4 Linq ready), and will not be hit by performance (reasonable performance)

Thanks.

Answer 1

List<T>

The simplest way (for a List<T>) is to use:

int first = list[0];
list.RemoveAt(0);
list.Add(first);

Performance is nasty though - O(n).

Array

This is basically equivalent to the List<T> version, but more manual:

int first = array[0];
Array.Copy(array, 1, array, 0, array.Length - 1);
array[array.Length - 1] = first;

LinkedList<T>

If you could use a LinkedList<T> instead, that would be much simpler:

int first = linkedList.First;
linkedList.RemoveFirst();
linkedList.AddLast(first);

This is O(1) as each operation is constant time.

Queue<T>

cadrell0's solution of using a queue is a single statement, as Dequeue removes the element and returns it:

queue.Enqueue(queue.Dequeue());

While I can't find any documentation of the performance characteristic of this, I'd expect Queue<T> to be implemented using an array and an index as the "virtual starting point" - in which case this is another O(1) solution.

Note that in all of these cases you'd want to check for the list being empty first. (You could deem that to be an error, or a no-op.)

Answer 2

You could implement it as a queue. Dequeue and Enqueue the same value.

**I wasn't sure about performance in converting a List to a Queue, but people upvoted my comment, so I'm posting this as an answer.

Answer 3

I use this one:

public static List<T> Rotate<T>(this List<T> list, int offset)
{
    return list.Skip(offset).Concat(list.Take(offset)).ToList();
}

Answer 4

It seems like some answerers have treated this as a chance to explore data structures. While those answers are informative and useful, they are not very Linq'ish.

The Linq'ish approach is: You get an extension method which returns a lazy IEnumerable that knows how to build what you want. This method doesn't modify the source and should only allocate a copy of the source if necessary.

public static IEnumerable<IEnumerable<T>> Rotate<T>(this List<T> source)
{
  for(int i = 0; i < source.Count; i++)
  {
    yield return source.TakeFrom(i).Concat(source.TakeUntil(i));
  }
}

  //similar to list.Skip(i-1), but using list's indexer access to reduce iterations
public static IEnumerable<T> TakeFrom<T>(this List<T> source, int index)
{
  for(int i = index; i < source.Count; i++)
  {
    yield return source[i];
  }
}

  //similar to list.Take(i), but using list's indexer access to reduce iterations    
public static IEnumerable<T> TakeUntil<T>(this List<T> source, int index)
{
  for(int i = 0; i < index; i++)
  {
    yield return source[i];
  }
}

Used as:

List<int> myList = new List<int>(){1, 2, 3, 4, 5};
foreach(IEnumerable<int> rotation in myList.Rotate())
{
  //do something with that rotation
}

Answer 5

How about this:

var output = input.Skip(rot)
                  .Take(input.Count - rot)
                  .Concat(input.Take(rot))
                  .ToList();

Where rot is the number of spots to rotate - which must be less than the number of elements in the input list.

As @cadrell0 answer shows if this is all you do with your list, you should use a queue instead of a list.

Answer 6

My solution maybe too basic (I wouldn't like to say it's lame...) and not LINQ'ish.
However, it has a pretty good performance.

int max = 5; //the fixed size of your array.
int[] inArray = new int[5] {0,0,0,0,0}; //initial values only.

void putValueToArray(int thisData)
{
  //let's do the magic here...
  Array.Copy(inArray, 1, inArray, 0, max-1);
  inArray[max-1] = thisData;
}

Answer 7

You can play nice in .net framework.

I understand that what you want to do is more up to be an iteration behavior than a new collection type; so I would suggest you to try this extension method based on IEnumerable, which will work with Collections, Lists and so on...

class Program
{
    static void Main(string[] args)
    {
        int[] numbers = { 1, 2, 3, 4, 5, 6, 7 };

        IEnumerable<int> circularNumbers = numbers.AsCircular();

        IEnumerable<int> firstFourNumbers = circularNumbers
            .Take(4); // 1 2 3 4

        IEnumerable<int> nextSevenNumbersfromfourth = circularNumbers
            .Skip(4).Take(7); // 4 5 6 7 1 2 3 
    }
}

public static class CircularEnumerable
{
    public static IEnumerable<T> AsCircular<T>(this IEnumerable<T> source)
    {
        if (source == null)
            yield break; // be a gentleman

        IEnumerator<T> enumerator = source.GetEnumerator();

        iterateAllAndBackToStart:
        while (enumerator.MoveNext()) 
            yield return enumerator.Current;

        enumerator.Reset();
        if(!enumerator.MoveNext())
            yield break;
        else
            yield return enumerator.Current;
goto iterateAllAndBackToStart;
    }
}

• Reasonable performance
• Flexible

If you want go further, make a CircularList and hold the same enumerator to skip the Skip() when rotating like in your sample.

Answer 8

My solution for Arrays:

    public static void ArrayRotate(Array data, int index)
    {
        if (index > data.Length)
            throw new ArgumentException("Invalid index");
        else if (index == data.Length || index == 0)
            return;

        var copy = (Array)data.Clone();

        int part1Length = data.Length - index;

        //Part1
        Array.Copy(copy, 0, data, index, part1Length);
        //Part2
        Array.Copy(copy, part1Length, data, 0, index);
    }

Answer 9

I've used the following extensions for this:

static class Extensions
{
    public static IEnumerable<T> RotateLeft<T>(this IEnumerable<T> e, int n) =>
        n >= 0 ? e.Skip(n).Concat(e.Take(n)) : e.RotateRight(-n);

    public static IEnumerable<T> RotateRight<T>(this IEnumerable<T> e, int n) =>
        e.Reverse().RotateLeft(n).Reverse();
}

They're certainly easy (OP title request), and they've got reasonable performance (OP write-up request). Here's a little demo I ran in LINQPad 5 on an above-average-powered laptop:

void Main()
{
    const int n = 1000000;
    const int r = n / 10;
    var a = Enumerable.Range(0, n);

    var t = Stopwatch.StartNew();

    Console.WriteLine(a.RotateLeft(r).ToArray().First());
    Console.WriteLine(a.RotateLeft(-r).ToArray().First());
    Console.WriteLine(a.RotateRight(r).ToArray().First());
    Console.WriteLine(a.RotateRight(-r).ToArray().First());

    Console.WriteLine(t.ElapsedMilliseconds); // e.g. 236
}

Answer 10

You can use below code for left Rotation.

List<int> backUpArray = array.ToList();

for (int i = 0; i < array.Length; i++)
{
    int newLocation = (i + (array.Length - rotationNumber)) % n;
    array[newLocation] = backUpArray[i];
}

Answer 11

Try

List<int> nums = new List<int> {1,2,3,4,5};
var newNums = nums.Skip(1).Take(nums.Count() - 1).ToList();
newNums.Add(nums[0]);

Although, I like Jon Skeet's answer better.

Answer 12

below is my approach. Thank you

public static int[] RotationOfArray(int[] A, int k)
  {
      if (A == null || A.Length==0)
          return null;
      int[] result =new int[A.Length];
      int arrayLength=A.Length;
      int moveBy = k % arrayLength;
      for (int i = 0; i < arrayLength; i++)
      {
          int tmp = i + moveBy;
          if (tmp > arrayLength-1)
          {
              tmp =  + (tmp - arrayLength);
          }
          result[tmp] = A[i];             
      }        
      return result;
  }

Answer 13

public static int[] RightShiftRotation(int[] a, int times) {
  int[] demo = new int[a.Length];
  int d = times,i=0;
  while(d>0) {
    demo[d-1] = a[a.Length - 1 - i]; d = d - 1; i = i + 1;
  }
  for(int j=a.Length-1-times;j>=0;j--) { demo[j + times] = a[j]; }
  return demo;
}

Answer 14

Using Linq,

List<int> temp = new List<int>();     

 public int[] solution(int[] array, int range)
    {
        int tempLength = array.Length - range;

        temp = array.Skip(tempLength).ToList();

        temp.AddRange(array.Take(array.Length - range).ToList());

        return temp.ToArray();
    }

Answer 15

If you're working with a string you can do this quite efficiently using ReadOnlySpans:

ReadOnlySpan<char> apiKeySchema = "12345";
const int apiKeyLength = 5;
for (int i = 0; i < apiKeyLength; i++)
{
    ReadOnlySpan<char> left = apiKeySchema.Slice(start: i, length: apiKeyLength - i);
    ReadOnlySpan<char> right = apiKeySchema.Slice(start: 0, length: i);
    Console.WriteLine(string.Concat(left, right));
}       

Output:

12345
23451
34512
45123
51234

Answer 16

I was asked to reverse a character array with minimal memory usage.

char[] charArray = new char[]{'C','o','w','b','o','y'};

Method:

static void Reverse(ref char[] s)
{
    for (int i=0; i < (s.Length-i); i++)
    {
        char leftMost = s[i];
        char rightMost = s[s.Length - i - 1];

        s[i] = rightMost;
        s[s.Length - i - 1] = leftMost;
    }
}

Answer 17

How about using modular arithmetic :

public void UsingModularArithmetic()
{ 
  string[] tokens_n = Console.ReadLine().Split(' ');
  int n = Convert.ToInt32(tokens_n[0]);
  int k = Convert.ToInt32(tokens_n[1]);
  int[] a = new int[n];

  for(int i = 0; i < n; i++)
  {
    int newLocation = (i + (n - k)) % n;
    a[newLocation] = Convert.ToInt32(Console.ReadLine());
  }

  foreach (int i in a)
    Console.Write("{0} ", i);
}

So basically adding the values to the array when I am reading from console.