source: branches/FitnessLandscapeAnalysis/HeuristicLab.Analysis.FitnessLandscape/Exhaustive/PermutationEnumerationManipulator.cs @ 13042

#region License Information
/* HeuristicLab
 * Copyright (C) 2002-2010 Heuristic and Evolutionary Algorithms Laboratory (HEAL)
 *
 * This file is part of HeuristicLab.
 *
 * HeuristicLab is free software: you can redistribute it and/or modify
 * it under the terms of the GNU General Public License as published by
 * the Free Software Foundation, either version 3 of the License, or
 * (at your option) any later version.
 *
 * HeuristicLab is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 * GNU General Public License for more details.
 *
 * You should have received a copy of the GNU General Public License
 * along with HeuristicLab. If not, see <http://www.gnu.org/licenses/>.
 */
#endregion

using System;
using HeuristicLab.Common;
using HeuristicLab.Core;
using HeuristicLab.Data;
using HeuristicLab.Encodings.PermutationEncoding;
using HeuristicLab.Parameters;
using HeuristicLab.Persistence.Default.CompositeSerializers.Storable;

namespace HeuristicLab.Analysis.FitnessLandscape {

  [Item("PermutationEnumerationManipulator", "An operator that generates the next permutation based on lexicographic ordering.")]
  [StorableClass]
  public class PermutationEnumerationManipulator : PermutationManipulator {

    public ValueLookupParameter<IntValue> NrOfStepsParameter {
      get { return (ValueLookupParameter<IntValue>)Parameters["NrOfSteps"]; }
    }

    [StorableConstructor]
    protected PermutationEnumerationManipulator(bool deserializing) : base(deserializing) { }
    protected PermutationEnumerationManipulator(PermutationEnumerationManipulator original, Cloner cloner) : base(original, cloner) { }
    public PermutationEnumerationManipulator() {
      Parameters.Add(new ValueLookupParameter<IntValue>("NrOfSteps", "The number of steps to advance the permutation.", new IntValue(1)));
    }
    [StorableHook(HookType.AfterDeserialization)]
    private void EnsureParameterExists() {
      if (!Parameters.ContainsKey("NrOfSteps"))
        Parameters.Add(new ValueLookupParameter<IntValue>("NrOfSteps", "The number of steps to advance the permutation.", new IntValue(1)));
    }

    public override IDeepCloneable Clone(Cloner cloner) {
      return new PermutationEnumerationManipulator(this, cloner);
    }

    protected override void Manipulate(IRandom random, Permutation permutation) {
      int steps = NrOfStepsParameter.ActualValue.Value;
      if (steps < 0)
        steps = random.Next(-steps)+1;
      for (int i=0; i<steps; i++)
        Advance(permutation);
    }

    public void Advance(Permutation p) {
      Advance(p, 0, new bool[p.Length]);
    }

    public bool Advance(Permutation perm, int index, bool[] used) {
      // cannot mutate length 1 permutations
      if (index >= perm.Length)
        return false;

      // try to swap the last two positions
      if (index == perm.Length - 2) {
        if (perm[index] < perm[index + 1]) {
          Swap(perm, index, index+1);
          return true;
        } else
          return false;
      }
      used[perm[index]] = true;
      if (Advance(perm, index + 1, used)) // try to advance later digits
        return true;
      used[perm[index]] = false;
      for (int i = perm[index] + 1; i < perm.Length; i++) { // try to advance this digit
        if (!used[i]) {
          perm[index] = i;
          used[i] = true;
          Fill(perm, index + 1, used);
          return true;
        }
      }
      if (index == 0) { // wrap around
        Fill(perm, 0, new bool[perm.Length]);
        return true;
      }
      return false;
    }

    public static void Swap(Permutation p, int i, int j) {
      int t = p[j];
      p[j] = p[i];
      p[i] = t;
    }

    private void Fill(Permutation perm, int startIndex, bool[] used) {
      int j = 0;
      for (int i = startIndex; i < perm.Length; i++) {
        for (; j < used.Length; j++) {
          if (!used[j]) {
            perm[i] = j;
            used[j] = true;
            goto Done;
          }
        }
        throw new InvalidOperationException("not enough elements left");
      Done: ;
      }
    }
  }
}