Самый простой способ повернуть список в С#

Списки говорят, что у меня есть список List<int> {1,2,3,4,5}

Поворот означает:

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

Возможно, поворот - это не лучшее слово для этого, но надеюсь, что вы поймете, что я имею в виду

Мой вопрос, самый простой способ (в коротком коде, С# 4 Linq готов) и не пострадает от производительности (разумная производительность)

Спасибо.

Ответы

Ответ 1

Вы можете реализовать его как очередь. Dequeue и Enqueue то же значение.

** Я не был уверен в производительности при преобразовании списка в очередь, но люди поддержали мой комментарий, поэтому я отправляю это как ответ.

Ответ 2

List<T>

Самый простой способ (для List<T>) - использовать:

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

Производительность является неприятной, хотя - O (n).

Массив

Это в основном эквивалентно версии List<T>, но более ручной:

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

LinkedList<T>

Если бы вы могли использовать LinkedList<T>, это было бы намного проще:

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

Это O (1), поскольку каждая операция является постоянным временем.

Queue<T>

Решение cadrell0 использования очереди - это один оператор, поскольку Dequeue удаляет элемент и возвращает его:

queue.Enqueue(queue.Dequeue());

Пока я не могу найти документацию о характеристиках производительности, я ожидал бы, что Queue<T> будет реализован с использованием массива и индекса как "виртуальной начальной точки" - в этом случае это еще один O ( 1) решение.

Обратите внимание, что во всех этих случаях вам нужно сначала проверить, что список пуст. (Вы можете считать это ошибкой или нет-op.)

Ответ 3

Я использую этот:

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

Ответ 4

Кажется, что некоторые респонденты рассматривали это как возможность исследовать структуры данных. Хотя эти ответы являются информативными и полезными, они не очень похожи на Linq'ish.

Linq'ish-подход: вы получаете метод расширения, который возвращает ленивый IEnumerable, который знает, как построить то, что вы хотите. Этот метод не изменяет источник и должен при необходимости выделять копию источника.

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

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

  //similar to list.Take(i), but using list 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];
  }
}

Используется как:

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

Ответ 5

Как насчет этого:

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

Где rot - количество поворотных точек, которое должно быть меньше количества элементов в списке input.

Как показано в ответе @cadrell0, если это все, что вы делаете со своим списком, вы должны использовать очередь вместо списка.

Ответ 6

Попробуйте

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]);

Хотя, мне нравится, что Джон Скит лучше отвечает.

Ответ 7

Вы можете хорошо играть в .net framework.

Я понимаю, что то, что вы хотите сделать, скорее должно быть итерационным поведением, чем новым типом коллекции; поэтому я бы предложил вам попробовать этот метод расширения на основе IEnumerable, который будет работать с коллекциями, списками и т.д.

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;
    }
}

Разумная производительность
Гибкая

Если вы хотите пойти дальше, сделайте CircularList и удерживайте того же перечислителя, чтобы пропустить Skip() при вращении, как в вашем примере.

Ответ 8

Мое решение для массивов:

    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);
    }

Ответ 9

Мое решение может быть слишком простым (я бы не хотел говорить, что он хромой...), а не LINQ'ish.
Тем не менее, он имеет довольно хорошую производительность.

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 do the magic here...
  Array.Copy(inArray, 1, inArray, 0, max-1);
  inArray[max-1] = thisData;
}

Ответ 10

Вы можете использовать код ниже для левого вращения.

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

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

Ответ 11

Я использовал следующие расширения для этого:

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();
}

Они, безусловно, легки (запрос заголовка OP), и у них есть разумная производительность (запрос на запись в OP). Вот небольшая демонстрация, которую я запускал в LINQPad 5 на ноутбуке выше среднего:

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
}

Ответ 12

ниже мой подход. Спасибо вам

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;
  }

Ответ 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;
}

Ответ 14

Мне было предложено изменить массив символов с минимальным использованием памяти.

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

Метод:

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;
    }
}

Ответ 15

Как насчет использования модульной арифметики:

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);
}

Итак, в основном добавление значений в массив, когда я читаю с консоли.