Moyen le plus simple de faire pivoter une liste en c#

Question

Les listes disent que j'ai une liste List {1,2,3,4,5}

Rotation signifie:

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

Peut-être que "rotation" n'est pas le meilleur mot pour cela, mais j'espère que vous comprenez ce que je veux dire

Ma question, quel est le moyen le plus facile (en peu de code, prêt pour Linq en c# 4), et ne sera pas affecté par les performances (performances raisonnables)

Merci.

Answer 1

List

La façon la plus simple (pour un List) est d'utiliser :

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

Les performances sont mauvaises cependant - O(n).

Array

C'est essentiellement équivalent à la version List, mais plus manuel :

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

LinkedList

Si vous pouviez utiliser une LinkedList à la place, ce serait beaucoup plus simple :

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

Ceci est O(1) car chaque opération est en temps constant.

Queue

La solution de cadrell0 utilisant une file d'attente est une seule déclaration, car Dequeue supprime l'élément et le retourne :

queue.Enqueue(queue.Dequeue());

Je ne trouve aucune documentation sur les caractéristiques de performances de ceci, je m'attends à ce que Queue soit implémenté en utilisant un tableau et un index comme "point de départ virtuel" - dans ce cas, c'est une autre solution O(1).

Remarquez que dans tous ces cas, vous voudriez vérifier d'abord si la liste est vide. (Vous pourriez considérer cela comme une erreur, ou une opération nulle.)

Answer 2

Vous pourriez l'implémenter en tant que file d'attente. Défilez et mettez en file d'attente la même valeur.

**Je n'étais pas sûr de la performance de la conversion d'une liste en file d'attente, mais les gens ont voté positivement pour mon commentaire, donc je poste ceci comme une réponse.

Answer 3

J'utilise celui-ci :

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

Answer 4

Il semble que certains répondants ont traité cela comme une opportunité d'explorer les structures de données. Bien que ces réponses soient informatives et utiles, elles ne sont pas très Linq'ish.

L'approche Linq'ish est la suivante : vous obtenez une méthode d'extension qui retourne un IEnumerable paresseux qui sait comment construire ce que vous voulez. Cette méthode ne modifie pas la source et ne doit allouer une copie de la source que si nécessaire.

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

  //similaire à list.Skip(i-1), mais en utilisant l'accès par indexeur de la liste pour réduire les itérations
public static IEnumerable TakeFrom(this List source, int index)
{
  for(int i = index; i < source.Count; i++)
  {
    yield return source[i];
  }
}

  //similaire à list.Take(i), mais en utilisant l'accès par indexeur de la liste pour réduire les itérations    
public static IEnumerable TakeUntil(this List source, int index)
{
  for(int i = 0; i < index; i++)
  {
    yield return source[i];
  }
}

Utilisé comme :

List myList = new List(){1, 2, 3, 4, 5};
foreach(IEnumerable rotation in myList.Rotate())
{
  //faire quelque chose avec cette rotation
}

Answer 5

Que diriez-vous de ceci :

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

Où rot est le nombre d'emplacements à faire pivoter - qui doit être inférieur au nombre d'éléments dans la liste input.

Comme le montre la réponse de @cadrell0, si c'est tout ce que vous faites avec votre liste, vous devriez utiliser une file d'attente à la place d'une liste.