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

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 tourner n’est pas le meilleur mot pour cela, mais j’espère que vous comprendrez ce que je veux dire

Ma question, quelle est la manière la plus simple (en abrégé, c # 4 Linq ready), et ne sera pas touchée par les performances (performances raisonnables)

Merci.

Vous pouvez l’implémenter comme une queue. Dequeue et Enqueue ont la même valeur.

** Je n’étais pas certain de la performance lors de la conversion d’une liste en queue, mais les gens ont voté pour mon commentaire, alors je poste cette réponse.

List

Le moyen le plus simple (pour une List ) est d’utiliser:

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

La performance est méchante si – O (n).

Tableau

Ceci est essentiellement équivalent à la version List , mais plus manuelle:

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

LinkedList

Si vous pouviez utiliser un LinkedList place, cela serait beaucoup plus simple:

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

C’est O (1) car chaque opération est un temps constant.

Queue

La solution de cadrell0 consistant à utiliser une queue est une seule instruction, car Dequeue supprime l’élément et le renvoie:

 queue.Enqueue(queue.Dequeue()); 

Bien que je ne puisse pas trouver de documentation sur les caractéristiques de performance, je pense que Queue doit être implémenté en utilisant un tableau et un index comme “sharepoint départ virtuel” – auquel cas il s’agit d’un autre O (1) Solution.

Notez que dans tous ces cas, vous souhaitez vérifier que la liste est vide en premier. (Vous pouvez considérer cela comme une erreur ou un non-op.)

J’utilise celui-ci:

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

Il semble que certains intervenants aient considéré 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 linqish.

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 devrait allouer une copie de la source que si nécessaire.

 public static IEnumerable> Rotate(this List 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's indexer access to reduce iterations public static IEnumerable TakeFrom(this List source, int index) { for(int i = index; i < source.Length; i++) { yield return source[i]; } } //similar to list.Take(i), but using list's indexer access to reduce iterations 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()) { //do something with that rotation } 

Que dis-tu de ça:

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

rot est le nombre de points à faire pivoter – qui doit être inférieur au nombre d’éléments de la liste d’ input .

Comme @ cadrell0 answer montre si c’est tout ce que vous faites avec votre liste, vous devez utiliser une queue au lieu d’une liste.

Ma solution est peut-être trop simple (je ne voudrais pas dire que c’est boiteux …) et non LINQ’ish.
Cependant, il a une bonne 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; } 

Essayer

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

Bien que j’aime mieux la réponse de Jon Skeet.

Ma solution pour les tableaux:

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

Vous pouvez utiliser le code ci-dessous pour la rotation gauche.

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

Vous pouvez jouer gentil dans le framework .net.

Je comprends que ce que vous voulez faire est plus un comportement d’itération qu’un nouveau type de collection; Je vous suggère donc d’essayer cette méthode d’extension basée sur IEnumerable, qui fonctionnera avec les collections, les listes, etc.

 class Program { static void Main(ssortingng[] args) { int[] numbers = { 1, 2, 3, 4, 5, 6, 7 }; IEnumerable circularNumbers = numbers.AsCircular(); IEnumerable firstFourNumbers = circularNumbers.Take(4); // 1 2 3 4 IEnumerable nextSevenNumbersfromfourth = circularNumbers .Skip(4).Take(7); // 4 5 6 7 1 2 3 } } public static class CircularEnumerable { public static IEnumerable AsCircular(this IEnumerable source) { if (source == null) yield break; // be a gentleman IEnumerator 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; } } 
  • Performance raisonnable
  • Flexible

Si vous voulez aller plus loin, créez une liste CircularList et maintenez le même énumérateur pour ignorer le Skip() lors de la rotation comme dans votre exemple.

J’ai utilisé les extensions suivantes pour cela:

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

Ils sont certainement faciles (demande de titre OP), et ils ont des performances raisonnables (demande d’écriture OP). Voici une petite démo que j’ai courue dans LINQPad 5 sur un ordinateur portable au-dessus de la moyenne:

 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); // eg 236 } 

ci-dessous est mon approche. Je vous remercie

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

En utilisant Linq,

 List temp = new List(); 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(); } 

On m’a demandé d’inverser un tableau de caractères avec une utilisation minimale de la mémoire.

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

Méthode:

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

Que diriez-vous d’utiliser l’arithmétique modulaire:

 public void UsingModularArithmetic() { ssortingng[] 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); } 

Donc, en gros, append les valeurs au tableau lorsque je lis depuis la console.