用于存储排列的 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