C # контейнер для хранения перестановок

Question

Я ищу необычную библиотеку контейнера c # для использования в алгоритме поиска по расписанию.Алгоритм поиска оценивает решения, идентифицированные различными перестановками, и ищет лучшее решение, которое он может найти.Как часть алгоритма, он должен помнить ранее «посещенные» решения, чтобы избежать попадания в круговой цикл.Следовательно, мне нужен контейнер, который индексируется перестановкой.Перестановка представляет собой массив размера N, содержащий значения от 0 до N-1 в «случайном» порядке.

Контейнеру нужно только хранить логическое значение, указывающее, что местоположение было посещено.Это должен быть быстрый поиск, он должен эффективно использовать память.

Я подозреваю, что дерево может быть оптимальным ... Но только если есть существующая библиотека, так как эта проблема также ограничена моими доступнымивремя для его реализации.

С уважением

Answer 1

Вы можете использовать хэш-набор для быстрого поиска перестановок.

Создайте класс для использования в качестве ключа в хэш-наборе и средство сравнения равенства для класса, что-то вроде:

publc class Permutation {

  private int[] _values;

  public Permutation(int[] values) {
    _values = values;
  }

  public class Comparer : IEqualityComparer<Permuation> {

    public int GetHashCode(Permuation x) {
      int code = 0;
      foreach (int value in x._values) {
        code = code * 251 + value;
      }
      return code;
    }

    public bool Equals(Permuation x, Permuation y) {
      if (x._values.Length != y._values.Length) return false;
      for (int i=0; i<x._values.Length; i++) {
        if (x._values[i] != y._values[i]) return false;
      }
      return true;
    }

  }

}

Затем вы можете создать хэш-набор, который использует класс в качестве ключа и его компаратор для оценки равенства:

var permutations = new HashSet<Permutation>(new Permutation.Comparer());

Теперь вы можете создавать объекты перестановок, помещать их в набор и тестировать их:

permuations.Add(new Permuation(new int[]{1,2,3}));

Permutation lookingFor = new Permutation(new int[]{1,2,3});
bool exists = permutations.Contains(lookgFor); // returns true

Permutation lookingFor = new Permutation(new int[]{1,3,2});
bool exists = permutations.Contains(lookgFor); // returns false

Answer 2

Всегда есть компромисс. Это либо скорость, либо память. Перестановки могут быть преобразованы в индексы, как описано здесь , но это дорого. С другой стороны, вам не нужно конвертировать их. Из того, что вы написали, я понимаю, что ваш алгоритм работает на перестановках, поэтому он «знает» их. В этом случае он может просто хранить их (посещенные) как есть (скажем, в списке или хэш-наборе). В этом случае вы не тратите дополнительное время на «сжатие» перестановки в индекс, но вам нужно убедиться, что у вас достаточно памяти.

Еще одно умственное упражнение, которое стоит выполнить, - определение количества различных перестановок, для которых ваш алгоритм должен хранить «посещенное» состояние. Таким образом, вы можете более реалистично решить, нужно ли вам экономить память, или вы можете выбрать более быстрый вариант.

Также несколько раз назад я гуглил "c # permutations" и смог найти ряд комбинаторных библиотек, независимо от того, предоставляют ли они то, что вы хотите, или нет, я не знаю, я предлагаю вам взглянуть на них и посмотреть, могут ли они тебе подходит.

Answer 3

Только мои два цента: посмотрите на этот код

Данная ссылка содержит контейнер перестановок, реализованный в виде дерева, это означает быстрый поиск и справедливое использование памяти.

Возможно, GetPermutations() методы могут быть улучшены с помощью Stack<T>, но это оставлено читателю в качестве упражнения: D

Answer 4

Я думаю хеш-таблица может быть тем, что вы ищете. Время поиска является постоянным, и время добавления нового элемента в контейнер также является постоянным (если вы не «переполняете» его, то для увеличения емкости контейнеров требуется линейное время).