融合元组以查找等价类

假设我们有一个包含 k 个元素的有限域 D={d1,..dk}。

我们认为 S 是 D^n 的子集，即一组 形式的元组，其中 ai 在 D 中。

我们希望使用 S' 2^D^n 的子集（即一组 形式的元组，其中 Ai 是 D 的子集）来（紧凑地）表示它。这意味着对于任何元组 s ' in S' Ai 叉积中的所有元素都存在于 S 中。

例如，考虑 D={a,b,c}，因此 k=3，n=2，并且元组 S=+++。

我们可以用S'=来表示S。

这个单例解也是最小的，S'=+也是一个解，但它更大，因此不太理想。

在具体实例中，我们需要处理一些大小：域 D 中的 k ~ 1000 个元素，n 10^6 的大值。

一种朴素的方法包括首先将 S 放入 S' 2^D^n 的域中，然后使用以下测试，两两，S' 中的两个元组 s1,s2 可以融合以形成 S' 中的单个元组，当且仅当。它们仅在一个组件上有所不同。

e.g.
+ -> （第二个组件不同）

+ -> （第二个组件不同）

+ -> （第一个组件不同）

现在可能有几个最小的 S'，我们有兴趣找到任何一个，并且某种最小化的近似也是可以的，只要它们不会给出错误的结果（即，即使 S' 没有那么小） ，但我们很快就能得到结果）。

朴素算法必须处理这样一个事实：任何新引入的“融合”元组都可能与其他元组匹配，因此即使 n 保持较低，它在大型输入集上的扩展性也非常糟糕。您需要 |S'|^2 比较来确保收敛，并且每当您融合两个元素时，我目前正在重新测试每一对（我该如何改进？）。

很多效率取决于迭代顺序，因此以某种方式对集合进行排序可能是一种选择，或者可能使用哈希进行索引，但我不确定如何做到这一点。

命令式伪代码是理想的选择，或者将问题重新表述为我可以运行求解器的指针会真正有帮助。

这是一些伪代码（我尚未测试过的 C# 代码），它演示了您的S'=+方法。除了空间要求外，当对元素使用整数索引时，空间要求可以忽略不计；添加和测试元组的整体效率和速度应该非常快。如果您想要一个实用的解决方案，那么您已经有了一个，只需使用正确的 ADT。

ElementType[] domain = new ElementType[]; // a simple array of domain elements
  FillDomain(domain); // insert all domain elements
  SortArray(domain); // sort the domain elements  K log K time
SortedDictionary<int, HashSet<int>> subsets; // int's are index/ref into domain
subsets = new SortedDictionary<int, HashSet<int>>();
//
void AddTuple(SortedDictionary<int, HashSet<int>> tuples, ElementType[] domain, ElementType first, elementType second) {
    int a = BinarySearch(domain, first); // log K time (binary search)
    int b = BinarySearch(domain, second); // log K time (binary search)
    if(tuples.ContainsKey(a)) { // log N time (binary search on sorted keys)
        if(!tuples[a].Contains(b)) { // constant time (hash lookup)
            tuples[a].Add(b); // constant time (hash add)
        }         
    } else { // constant time (instance + hash add)
        tuples[a] = new HashSet<in>();
        tuples[a].Add(b);
    }
}
//
bool ContainsTuple(SortedDictionary<int, HashSet<int>> tuples, ElementType[] domain, ElementType first, ElementType second) {
    int a = BinarySearch(domain, first); // log K time (binary search)
    int b = BinarySearch(domain, second); // log K time (binary search)
    if(tuples.ContainsKey(a)) { // log N time (binary search on sorted keys)
        if(tuples[a].Contains(b)) { // constant time (hash test)
            return true;
        }
    }
    return false;
}

优化元组子集 S' 所节省的空间不会超过优化过程本身的减慢。对于大小优化（如果您知道 K 将小于 65536，您可以在 SortedDictionary 和 HashSet 中使用短整数而不是整数。但即使是 5000 万个整数，每个 32 位整数也只占用 4 个字节 * 5000 万 ~= 200 MB 。

EDIT这是另一种方法，通过将元组编码/映射到字符串，您可以利用二进制字符串比较以及 UTF-16 / UTF-8 编码非常节省空间的事实。同样，这仍然没有达到您想要的合并优化，但速度和效率会相当不错。

这是 JavaScript 中的一些快速伪代码。

Array.prototype.binarySearch = function(elm) {
  var l = 0, h = this.length - 1, i; 
  while(l <= h) { 
    i = (l + h) >> 1; 
    if(this[i] < elm) l = ++i; 
    else if(this[i] > elm) h = --i; 
    else return i; 
  } 
  return -(++l); 
};
// map your ordered domain elements to characters 
// For example JavaScript's UTF-16 should be fine
// UTF-8 would work as well
var domain = {
  "a": String.fromCharCode(1),
  "b": String.fromCharCode(2),
  "c": String.fromCharCode(3),
  "d": String.fromCharCode(4)
}
var tupleStrings = [];
// map your tuple to the string encoding
function map(tuple) {
  var str = "";
  for(var i=0; i<tuple.length; i++) {
    str += domain[tuple[i]];
  }
  return str;
}
function add(tuple) {
  var str = map(tuple);
  // binary search
  var index = tupleStrings.binarySearch(str);
  if(index < 0) index = ~index;
  // insert depends on tupleString's type implementation
  tupleStrings.splice(index, 0, str);
}
function contains(tuple) {
  var str = map(tuple);
  // binary search 
  return tupleString.binarySearch(str) >= 0;
}

add(["a","b"]);
add(["a","c"]);
add(["b","b"]);
add(["b","c"]);
add(["c","c"]);
add(["d","a"]);
alert(contains(["a","a"]));
alert(contains(["d","a"]));
alert(JSON.stringify(tupleStrings, null, "\n"));