Déplacer les éléments dans le tableau par index

Tableau donné de n éléments, c.-à-d.

var array = [1, 2, 3, 4, 5]

Je peux écrire une extension au Array afin que je puisse modifier le tableau pour get cette sortie: [2, 3, 4, 5, 1] :

  mutating func shiftRight() { append(removeFirst()) } 

Existe-t-il un moyen d'implémenter une telle fonction qui déplacera le tableau par n'importe quel index, positif ou négatif. Je peux implémenter cette fonction dans un style impératif avec if-else clauses if-else , mais ce que je cherche, c'est une implémentation fonctionnelle.

L'algorithm est simple:

  1. Diviser le tableau en deux par l'index fourni
  2. append le premier tableau à la fin de la seconde

Y a-t-il un moyen de l'implémenter dans un style fonctionnel?

Le code que j'ai fini avec:

 extension Array { mutating func shift(var amount: Int) { guard -count...count ~= amount else { return } if amount < 0 { amount += count } self = Array(self[amount ..< count] + self[0 ..< amount]) } } 

Vous pouvez utiliser l'indexing à distance et concaténer les résultats. Cela vous donnera ce que vous cherchez, avec des noms similaires à la bibliothèque standard:

 extension Array { func shiftRight(var amount: Int = 1) -> [Element] { assert(-count...count ~= amount, "Shift amount out of bounds") if amount < 0 { amount += count } // this needs to be >= 0 return Array(self[amount ..< count] + self[0 ..< amount]) } mutating func shiftRightInPlace(amount: Int = 1) { self = shiftRight(amount) } } Array(1...10).shiftRight() // [2, 3, 4, 5, 6, 7, 8, 9, 10, 1] Array(1...10).shiftRight(7) // [8, 9, 10, 1, 2, 3, 4, 5, 6, 7] 

Au lieu de vous shiftRight() , vous pouvez aussi renvoyer Array(suffix(count - amount) + prefix(amount)) partir de shiftRight() .

Avec Swift 3, vous pouvez créer shift(withDistance:) et shiftInPlace(withDistance:) avec seulement quelques lignes de code:

 extension Array { func shift(withDistance distance: Int = 1) -> Array<Element> { let offsetIndex = distance >= 0 ? self.index(startIndex, offsetBy: distance, limitedBy: endIndex) : self.index(endIndex, offsetBy: distance, limitedBy: startIndex) guard let index = offsetIndex else { return self } return Array(self[index ..< endIndex] + self[startIndex ..< index]) } mutating func shiftInPlace(withDistance distance: Int = 1) { self = shift(withDistance: distance) } } 

Usage:

 let array1 = Array(1...10) let newArray = array1.shift(withDistance: 3) print(newArray) // prints: [4, 5, 6, 7, 8, 9, 10, 1, 2, 3] var array2 = Array(1...10) array2.shiftInPlace(withDistance: -2) print(array2) // prints: [9, 10, 1, 2, 3, 4, 5, 6, 7, 8] let array3 = Array(1...10) let newArray3 = array3.shift(withDistance: 30) print(newArray3) // prints: [1, 2, 3, 4, 5, 6, 7, 8, 9, 10] let array4 = Array(1...10) let newArray4 = array4.shift(withDistance: 0) print(newArray4) // prints: [1, 2, 3, 4, 5, 6, 7, 8, 9, 10] var array5 = Array(1...10) array5.shiftInPlace() print(array5) // prints: [2, 3, 4, 5, 6, 7, 8, 9, 10, 1] 

J'ai pris la peine d'écrire des extensions pour cela. Il a quelques fonctionnalités intéressantes:

  • Le décalage d'une valeur supérieure à la valeur de count entraîne un enveloppement.
  • Déplacer par montants négatifs returnne la direction
  • Expose des fonctions en tant qu'opérateurs binarys bit-shift ( << , <<= , >> , >>= )

 extension Array { func shiftedLeft(by rawOffset: Int = 1) -> Array { let clampedAmount = rawOffset % count let offset = clampedAmount < 0 ? count + clampedAmount : clampedAmount return Array(self[offset ..< count] + self[0 ..< offset]) } func shiftedRight(by rawOffset: Int = 1) -> Array { return self.shiftedLeft(by: -rawOffset) } mutating func shiftLeft(by rawOffset: Int = 1) { self = self.shiftedLeft(by: rawOffset) } mutating func shiftRight(by rawOffset: Int = 1) { self = self.shiftedRight(by: rawOffset) } } //Swift 3 func << <T>(array: [T], offset: Int) -> [T] { return array.shiftedLeft(by: offset) } func >> <T>(array: [T], offset: Int) -> [T] { return array.shiftedRight(by: offset) } func <<= <T>(array: inout [T], offset: Int) { return array.shiftLeft(by: offset) } func >>= <T>(array: inout [T], offset: Int) { return array.shiftRight(by: offset) } /*// Swift 2.2 func << <T>(array: [T], offset: Int) -> [T] { return array.shiftedLeft(by: offset) } func >> <T>(array: [T], offset: Int) -> [T] { return array.shiftedRight(by: offset) } func <<= <T>(inout array: [T], offset: Int) { return array.shiftLeft(by: offset) } func >>= <T>(inout array: [T], offset: Int) { return array.shiftRight(by: offset) }*/ 

Vous pouvez le voir en action ici .

Voici une solution plus générale, qui implémente paresseusement cette fonctionnalité pour tout type qui répond aux exigences:

 extension RandomAccessCollection where Self: RangeReplaceableCollection, Self.Index == Int, Self.IndexDistance == Int { func shiftedLeft(by rawOffset: Int = 1) -> RangeReplaceableSlice<Self> { let clampedAmount = rawOffset % count let offset = clampedAmount < 0 ? count + clampedAmount : clampedAmount return self[offset ..< count] + self[0 ..< offset] } func shiftedRight(by rawOffset: Int = 1) -> RangeReplaceableSlice<Self> { return self.shiftedLeft(by: -rawOffset) } mutating func shiftLeft(by rawOffset: Int = 1) { self = Self.init(self.shiftedLeft(by: rawOffset)) } mutating func shiftRight(by rawOffset: Int = 1) { self = Self.init(self.shiftedRight(by: rawOffset)) } //Swift 3 static func << (c: Self, offset: Int) -> RangeReplaceableSlice<Self> { return c.shiftedLeft(by: offset) } static func >> (c: Self, offset: Int) -> RangeReplaceableSlice<Self> { return c.shiftedRight(by: offset) } static func <<= (c: inout Self, offset: Int) { return c.shiftLeft(by: offset) } static func >>= (c: inout Self, offset: Int) { return c.shiftRight(by: offset) } } 

Suite aux réponses de Nate Cook , je dois aussi décaler un tableau returnnant l'ordre inverse, donc j'ai fait:

 //MARK: - Array extension Array { func shiftRight( amount: Int = 1) -> [Element] { var amountMutable = amount assert(-count...count ~= amountMutable, "Shift amount out of bounds") if amountMutable < 0 { amountMutable += count } // this needs to be >= 0 return Array(self[amountMutable ..< count] + self[0 ..< amountMutable]) } func reverseShift( amount: Int = 1) -> [Element] { var amountMutable = amount amountMutable = count-amountMutable-1 let a: [Element] = self.reverse() return a.shiftRight(amountMutable) } mutating func shiftRightInPlace(amount: Int = 1) { self = shiftRight(amount) } mutating func reverseShiftInPlace(amount: Int = 1) { self = reverseShift(amount) } } 

Nous avons par exemple:

 Array(1...10).shiftRight() // [2, 3, 4, 5, 6, 7, 8, 9, 10, 1] Array(1...10).shiftRight(7) // [8, 9, 10, 1, 2, 3, 4, 5, 6, 7] Array(1...10).reverseShift() // [2, 1, 10, 9, 8, 7, 6, 5, 4, 3] Array(1...10).reverseShift(7) // [8, 7, 6, 5, 4, 3, 2, 1, 10, 9] 

Voici une implémentation fonctionnelle pour la rotation «en place» qui ne nécessite pas de memory supplémentaire ni de variable temporaire et qui n'effectue pas plus d'un échange par élément.

 extension Array { mutating func rotateLeft(by rotations:Int) { let _ = // silence warnings (1..<Swift.max(1,count*((rotations+1)%(count+1)%1))) // will do zero or count - 1 swaps .reduce((i:0,r:count+rotations%count)) // i: swap index r:effective offset { s,_ in let j = (s.i+sr)%count // j: index of value for position i swap(&self[j],&self[si]) // swap to place value at rotated index return (j,sr) // continue with next index to place } } } 

Il supporte de façon optimale des rotations nulles, positives et négatives ainsi que des rotations de plus grande amplitude que la taille du tableau et la rotation d'un tableau vide (c'est-à-dire qu'il ne peut pas échouer).

Utilise des valeurs négatives pour tourner dans l'autre sens (vers la droite).

Faire pivoter un tableau de 3 éléments par 10 est comme le faire tourner de 1, les neuf rotations de poing le ramèneront à son état initial (mais nous ne voulons pas déplacer les éléments plus d'une fois).

Faire tourner un tableau à 5 éléments vers la droite de 3, c'est-à-dire rotateLeft (par: -3) est équivalent à rotateLeft (par: 2). Le "décalage effectif" de la fonction en tient count.

Dans l'objective C, vous pouvez simplement get un tableau décalé à gauche comme ceci:

 - (NSMutableArray *)shiftedArrayWithOffset:(NSInteger)offset { NSMutableArray *bufferArray = [[NSMutableArray alloc] initWithArray:originalArray]; for (int i = 0; i < offset; i++) { id object = [bufferArray firstObject]; [bufferArray removeObjectAtIndex:0]; [bufferArray addObject:object]; } return bufferArray; } 

Le moyen le plus rapide est (mais prend double memory!):

consortingbution:

 var arr = [1,2,3,4,5] let k = 1 (num steps to rotate) let n = arr.count ( a little but faster ) 

rotation GAUCHE :

  var temp = arr for i in 0..<n { arr[(n-i+k)%n] = temp[i] } result: [2, 1, 4, 3, 5] 

rotation DROITE :

  var temp = arr for i in 0..<n { arr[(i+k)%n] = temp[i] } result: [4, 1, 2, 3, 5]