Context Navigation

Manipulators

Timestamp:

02/11/17 00:27:04 (8 years ago)

Author:

abeham

Message:

#2731: Added better performing manipulation methods to Permutation and adapted the manipulators to use them

Location:

Files:

-                      r14185
+                      r14662
     /// <param name="permutation">The permutation to manipulate.</param>
     public static void Apply(IRandom random, Permutation permutation) {
       Permutation original = (Permutation)permutation.Clone();
       int cutIndex, insertIndex, number;
+      var cutIndex = random.Next(permutation.Length);
+      var insertIndex = random.Next(permutation.Length);
+      cutIndex = random.Next(original.Length);
+      insertIndex = random.Next(original.Length);
+      number = original[cutIndex];
+      if (cutIndex == insertIndex) return;
+      int i = 0;  // index in new permutation
+      int j = 0;  // index in old permutation
+      while (i < original.Length) {
+        if (j == cutIndex) {
+          j++;
+        }
+        if (i == insertIndex) {
+          permutation[i] = number;
+          i++;
+        }
+        if ((i < original.Length) && (j < original.Length)) {
+          permutation[i] = original[j];
+          i++;
+          j++;
+        }
+      }
+      permutation.Move(cutIndex, cutIndex, insertIndex);
+    }

-                      r14185
+                      r14662
     public static void Apply(Permutation permutation, int breakPoint1, int breakPoint2) {
+      for (int i = 0; i <= (breakPoint2 - breakPoint1) / 2; i++) {  // invert permutation between breakpoints
+        int temp = permutation[breakPoint1 + i];
+        permutation[breakPoint1 + i] = permutation[breakPoint2 - i];
+        permutation[breakPoint2 - i] = temp;
+      }
+      permutation.Reverse(breakPoint1, breakPoint2 - breakPoint1 + 1);
+    }

-                      r14185
+                      r14662
 #endregion
+using System.Linq;
 using HeuristicLab.Common;
 using HeuristicLab.Core;
 …
       breakPoint2 = random.Next(breakPoint1 + 1, permutation.Length);
+      // TODO: Use Fisher-Yates-Shuffle rather than complicated code below
+      // scrambledIndices = Enumerable.Range(0, breakPoint2 - breakPoint1 + 1).Shuffle(random).ToArray();
+      // Also, it would be more memory-efficient to change here and Apply(Permutation, int, int[]) below to interpret scrambleArray as values, not indices
+      // Don't forget the move generator
+      // BackwardsCompatibility3.3
+      #region This whole code should be replaced by above line when going for 3.4
       scrambledIndices = new int[breakPoint2 - breakPoint1 + 1];
       remainingIndices = new int[breakPoint2 - breakPoint1 + 1];
 …
+        }
+      }
+      #endregion
       Apply(permutation, breakPoint1, scrambledIndices);
 …
     public static void Apply(Permutation permutation, int startIndex, int[] scrambleArray) {
+      Permutation original = (Permutation)permutation.Clone();
+      for (int i = 0; i < scrambleArray.Length; i++) {  // scramble permutation between breakpoints
+        permutation[startIndex + i] = original[startIndex + scrambleArray[i]];
+      }
+      permutation.Replace(startIndex, scrambleArray.Select(x => permutation[startIndex + x]).ToArray());
+    }

-                      r14185
+                      r14662
     public static void Apply(Permutation permutation, int index1, int index2) {
+      int temp = permutation[index1];
+      permutation[index1] = permutation[index2];
+      permutation[index2] = temp;
+      permutation.Swap(index1, index2);
+    }

-                      r14185
+                      r14662
     public static void Apply(IRandom random, Permutation permutation) {
       if (permutation.Length < 3) throw new ArgumentException("Swap3Manipulator: The permutation must be at least of size 3.", "permutation");
       int index1, index2, index3, temp;
+      int index1, index2, index3;
       do {
 …
       } while (index1 == index2 || index2 == index3 || index1 == index3);
+      // swap positions 1 and 2
+      temp = permutation[index1];
+      permutation[index1] = permutation[index2];
+      permutation[index2] = temp;
+      // swap positions 2 and 3
+      temp = permutation[index2];
+      permutation[index2] = permutation[index3];
+      permutation[index3] = temp;
+      permutation.Swap(index1, index2);
+      permutation.Swap(index2, index3);
+    }

-                      r14185
+                      r14662
     public static void Apply(Permutation permutation, int breakPoint1, int breakPoint2, int insertPoint) {
+      Permutation original = (Permutation)permutation.Clone();
+      int i = 0;  // index in new permutation
+      int j = 0;  // index in old permutation
+      while (i < original.Length) {
+        if (i == insertPoint) {  // copy translocated area
+          for (int k = breakPoint1; k <= breakPoint2; k++) {
+            permutation[i] = original[k];
+            i++;
+          }
+        }
+        if (j == breakPoint1) {  // skip area between breakpoints
+          j = breakPoint2 + 1;
+        }
+        if ((i < original.Length) && (j < original.Length)) {
+          permutation[i] = original[j];
+          i++;
+          j++;
+        }
+      }
+      permutation.Move(breakPoint1, breakPoint2, insertPoint);
+    }

Note: See TracChangeset for help on using the changeset viewer.