用于存储排列的 C# 容器

Question

我正在寻找一个不寻常的 c# 容器库，用于调度搜索算法。搜索算法评估解决方案通过不同的排列来识别并寻找它能找到的最佳解决方案寻找。作为算法的一部分，它需要事先记住“访问”解决方案，因此可以避免陷入循环。因此我需要一个由排列索引的容器。排列是一个大小为 N 的数组，以“随机”方式保存值 0 到 N-1订单。

容器只需要存储一个 bool 值，表示位置有被访问过。它需要快速查找，它需要使有效利用内存。

我怀疑一棵树可能是最优的......但前提是存在一个现有的图书馆，因为这个问题也受到我实现它的可用时间的限制。

最好的问候

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