更有效的算法来找到两个集合的或
More efficient algorithm to find OR of two sets
给定一个n行和m列的矩阵1和0，需要找出对的数量可以选择使其 OR 为 11111....m times.
的行
示例：
1 0 1 0 1
0 1 0 0 1
1 1 1 1 0
答案：
2 ---> OR of row number [1,3] and [2,3]
鉴于 n 和 m 最多可以是 <= 3000 个命令，如何有效地解决这个问题？
PS：我已经尝试过一种天真的 O(n*n*m) 方法。我在想一个更好的解决方案。
1.简单的解决方案
简单的算法（您已经发现但没有 post）是获取 n 行的所有（n 选择 2）组合，或它们，并查看它是否有效。这是O(n^2 * m)。编码看起来像：
for (i = 0; i < n; ++i)
for (j=i+1; j < n; ++ j) {
try OR of row[i] with row[j] to see if it works, if so record (i,j)
}
2。恒定加速
您可以通过将位打包到字中来将 运行 时间缩短为字大小的一个因子。这仍然给出相同的渐近，但实际上是 64 位机器上的 64 位加速因子。这已在上面的评论中指出。
3。启发式加速
我们可以做启发式来进一步改进实践中的时间，但不能保证渐近。考虑按汉明权重对行进行排序，前面的汉明权重最小，最后的汉明权重最大（运行 时间 O(m * n * log m )）。然后你只需要比较低权重行和高权重行：具体来说，权重需要是>= m。然后搜索看起来像这样：
for (i = 0; i < n; ++i)
for (j=n-1; j > i; --j) /* go backwards to take advantage of hmwt */
{
if ( (hmwt(row[i]) + hmwt(row[j])) < m)
break;
try OR of row[i] with row[j] to see if it works, if so record (i,j)
}
4.走向更好的方法
另一种可能提供更好 returns 的方法是选择低汉明权重的列。然后将这些行组合成两组：该列中为 1 的行（A 组）和该列中为 0 的行（B 组）。然后你只需要考虑行的组合，其中一个来自组 A，另一个来自组 B，或者都来自组 A（感谢 @ruakh 发现了我的疏忽）。这些方面的东西应该会有很大帮助。但同样，这仍然是渐近相同的更坏情况，但在实践中应该更快（假设我们不是在所有组合都是答案的情况下）。
5.能做的事情的极限
构建有效向量对数量为 O(n^2) 的示例很容易，因此感觉很难击败 O(m*n^2) 更糟糕的情况。我们应该寻求的是一种与有效对数有某种关联的解决方案。上面的启发式正在朝这个方向发展。如果有一个汉明权重较小的列 h，则上面的第 4 点将 运行 时间降低到 O(h*n*m + h^2*m)。如果 h 明显小于 n，那么你会得到很大的改进。
扩展 TheGreatContini 的想法：
先试试
让我们将其视为查找属于 AxB 的组合，其中包含 A 组行和 B 组行。这些组合必须满足 or 条件，但我们还假设 a 的汉明权重至少与 b 一样大（以避免重复）。
现在将 A 拆分为 A0（以 0 开头的行）和 A1（以 1 开头的行）。对 B 做同样的事情。我们现在已经将问题简化为三个更小的问题：A0xB1、A1xB1 和 A1xB0。如果A和B相同，A0xB1和A1xB0也相同，所以我们只需要做一个。不仅这三个子问题加起来比第一个小，而且我们也完全检查了第一列，从现在开始可以忽略它。
为了解决这些子问题，我们可以使用相同的方法，但现在是第 2、3 列……在某些时候，我们要么检查所有列，要么#A 和#B 为 1。
根据实施情况，越早停止可能效率越高。那时我们可以对剩余的组合进行详尽的检查。请记住，如果我们已经检查了 k 列，那么每个组合的成本仅为 m-k。
更好的专栏selection
正如 TheGreatContini 所建议的，我们可以 select 可以 select 导致最小子问题的列，而不是 select 第一列。在每个步骤中找到该列的成本相当高，但权重可以在开始时计算一次，然后用作最佳列的估计。然后我们可以像往常一样使用算法重新排列列，完成后，再次重新排列它们。
确切的最佳列是 A 中零的数量乘以 B 中零的数量最大的列。
汉明权重p运行ing
我们知道a和b的汉明权重之和至少要有m。因为我们假设 a 是最高的汉明权重，所以我们可以删除 a 的所有汉明权重小于 m/2 的值。 （这提供的加速可能可以忽略不计，我不确定）。计算所有汉明权重的成本为 O(m*n)。
高效拆分
如果我们对行进行排序，使用二分算法可以更快地完成分组。这也可以导致集合在内存中的有效表示。我们可以只指定最小和最大行。排序可以在 O(n*m*log(n)) 中完成。然后可以在大约 log(n).
内完成拆分
这里有一些代码无法编译，但应该给出正确的想法。
private List<Row> rows;
public int findFirstOne(int column, int start, int end){
if(rows.get(start).get(column) == 1) return start;
if(rows.get(end).get(column) == 0) return -1;
while(start < end){
int mid = (start+end)/2;
if(rows.get(mid).get(column) == 0){
start = mid+1;
}else{
end = mid;
}
}
return start;
}
复杂度
在下面的计算中，更好的列 selection 的影响被忽略，因为它对最坏情况下的效率几乎没有改善。但是，在一般情况下，它可以通过尽快减少搜索 space 从而使其他检查更快来提供巨大的改进。
算法 运行 时间受 n²m 限制。
然而，我发现的最糟糕的例子都是 O(n*log(n)*m).
首先，矩阵的行排序为 O(n*log(n)*m)，可选地，列排序为 O(n*m + m*log(m))。
然后，子问题的创建。让我们先高估一下。我们最多需要细分 m 次，深度 i 的完整级别细分的成本可能被高估为 log(n)*3^i（每次细分的成本乘以细分数）。这导致总共 O(log(n)*3^m)。
它还必须满足 3^i <= n²/2，因为这是可能的最大组合数，因此对于大 m，它的上限为 O(n²*log(n)*m)。不过，我很难找到一个实际行为像这样的例子。
我认为假设许多子问题很早就变得微不足道是合理的。导致 O(log(n)*m*n)（如果有人想检查这个，我不太确定）。
这是一个现成的想法，可能具有更糟糕的渐近（或什至平均）行为——但它以一种有趣的方式概括，并且至少提供了一种不同的方法。这个问题可以看成一个exact cover problem。 n 行中的每一行都包含来自集合 {1,2,...,m} 的一组值 S，对应于该行具有值 1 的列索引。问题的任务是找到一个集合行的集合形成 {1,2,...m} 的不相交分区。当在一个精确的封面中只有两行这样的行时，这些行是您要查找的那种二元对立的行。但是，可能有更复杂的精确覆盖，例如涉及三行的覆盖：
0 1 0 0 1
1 0 0 0 0
0 0 1 1 0
精确覆盖问题寻找所有个这样的精确覆盖，是一个NP完全问题。规范解是 Algorithm X，由 Donald Knuth 创建。
如果我没记错的话，下面应该是O(n*m):
- 对于每一列，计算在该列中具有“1”的行的索引集，并将其存储为从列索引到行索引集的映射
- 对于每一行，计算可以 "complete" 该行的行索引集（通过添加“1"s in the columns where the row has a "0”）。这可以通过计算在步骤 1 中为相应列计算的集合的交集来完成
- 计算完成的行索引
以你的例子为例：
1 0 1 0 1
0 1 0 0 1
1 1 1 1 0
每列为“1”的行的索引是
- 第 0 列：[0, 2]
- 第 1 列：[1, 2]
- 第 2 列：[0, 2]
- 第 3 列：[2]
- 第 4 列：[0, 1]
用于"filling"每一行的所有索引集合的并集是
- 第 0 行：[2]
- 第 1 行：[2]
- 第 2 行：[]
一共2个
人们对 运行 时间争论不休的主要原因是计算最大 n 的 m 集的交集可以被认为是是 O(m*n)，但我认为这些集合的大小将受到限制：条目要么是 1，要么是 0，当有很多 1 时（并且大小很大），那么相交的集合较少，反之亦然 - 但我没有在这里做严格的证明...
一个基于 Java 的实现，我用来玩这个（以及一些基本的 "tests"）：
import java.util.ArrayList;
import java.util.Arrays;
import java.util.LinkedHashMap;
import java.util.LinkedHashSet;
import java.util.List;
import java.util.Map;
import java.util.Random;
import java.util.Set;
public class SetOrCombinations
{
public static void main(String[] args)
{
List<Integer> row0 = Arrays.asList(1, 0, 1, 0, 1);
List<Integer> row1 = Arrays.asList(1, 1, 0, 0, 1);
List<Integer> row2 = Arrays.asList(1, 1, 1, 1, 0);
List<Integer> row3 = Arrays.asList(0, 0, 1, 1, 1);
List<List<Integer>> rows = Arrays.asList(row0, row1, row2, row3);
run(rows);
for (int m = 2; m < 10; m++)
{
for (int n = 2; n < 10; n++)
{
run(generateRandomInput(m, n));
}
}
}
private static void run(List<List<Integer>> rows)
{
int m = rows.get(0).size();
int n = rows.size();
// For each column i:
// Compute the set of rows that "fill" this column with a "1"
Map<Integer, List<Integer>> fillers =
new LinkedHashMap<Integer, List<Integer>>();
for (int i = 0; i < m; i++)
{
for (int j = 0; j < n; j++)
{
List<Integer> row = rows.get(j);
List<Integer> list =
fillers.computeIfAbsent(i, k -> new ArrayList<Integer>());
if (row.get(i) == 1)
{
list.add(j);
}
}
}
// For each row, compute the set of rows that could "complete"
// the row (by adding "1"s in the columns where the row has
// a "0").
int count = 0;
Set<Integer> processedRows = new LinkedHashSet<Integer>();
for (int j = 0; j < n; j++)
{
processedRows.add(j);
List<Integer> row = rows.get(j);
Set<Integer> completers = new LinkedHashSet<Integer>();
for (int i = 0; i < n; i++)
{
completers.add(i);
}
for (int i = 0; i < m; i++)
{
if (row.get(i) == 0)
{
completers.retainAll(fillers.get(i));
}
}
completers.removeAll(processedRows);
count += completers.size();
}
System.out.println("Count "+count);
System.out.println("Ref. "+bruteForceCount(rows));
}
// Brute force
private static int bruteForceCount(List<List<Integer>> lists)
{
int count = 0;
int n = lists.size();
for (int i = 0; i < n; i++)
{
for (int j = i + 1; j < n; j++)
{
List<Integer> list0 = lists.get(i);
List<Integer> list1 = lists.get(j);
if (areOne(list0, list1))
{
count++;
}
}
}
return count;
}
private static boolean areOne(List<Integer> list0, List<Integer> list1)
{
int n = list0.size();
for (int i=0; i<n; i++)
{
int v0 = list0.get(i);
int v1 = list1.get(i);
if (v0 == 0 && v1 == 0)
{
return false;
}
}
return true;
}
// For testing
private static Random random = new Random(0);
private static List<List<Integer>> generateRandomInput(int m, int n)
{
List<List<Integer>> rows = new ArrayList<List<Integer>>();
for (int i=0; i<n; i++)
{
List<Integer> row = new ArrayList<Integer>();
for (int j=0; j<m; j++)
{
row.add(random.nextInt(2));
}
rows.add(row);
}
return rows;
}
}
这是一种算法，它利用了以下知识：在同一列中具有零的两行将被自动取消作为合作伙伴的资格。当前行中的零越少，我们访问其他行的次数就越少；而且总体上我们拥有的零越多，我们访问其他行的次数就越少。
create two sets, one with a list of indexes of all rows, and the other empty
assign a variable, total = 0
从右到左、从底行到顶部遍历每一行（也可以按其他顺序；我只是这样想象的）。
while row i is not the first row:
call the non-empty set A and the empty set dont_match
remove i, the index of the current row, from A
traverse row i:
if A is empty:
stop the traversal
if a zero is encountered:
traverse up that column, visiting only rows listed in A:
if a zero is encountered:
move that row index from A to dont_match
the remaining indexes in A point to row partners to row i
add their count to total and move the elements from the
shorter of A and dont_match to the other set
return total
给定一个n行和m列的矩阵1和0，需要找出对的数量可以选择使其 OR 为 11111....m times.
示例：
1 0 1 0 1
0 1 0 0 1
1 1 1 1 0
答案：
2 ---> OR of row number [1,3] and [2,3]
鉴于 n 和 m 最多可以是 <= 3000 个命令，如何有效地解决这个问题？
PS：我已经尝试过一种天真的 O(n*n*m) 方法。我在想一个更好的解决方案。
1.简单的解决方案
简单的算法（您已经发现但没有 post）是获取 n 行的所有（n 选择 2）组合，或它们，并查看它是否有效。这是O(n^2 * m)。编码看起来像：
for (i = 0; i < n; ++i)
for (j=i+1; j < n; ++ j) {
try OR of row[i] with row[j] to see if it works, if so record (i,j)
}
2。恒定加速 您可以通过将位打包到字中来将 运行 时间缩短为字大小的一个因子。这仍然给出相同的渐近，但实际上是 64 位机器上的 64 位加速因子。这已在上面的评论中指出。
3。启发式加速
我们可以做启发式来进一步改进实践中的时间，但不能保证渐近。考虑按汉明权重对行进行排序，前面的汉明权重最小，最后的汉明权重最大（运行 时间 O(m * n * log m )）。然后你只需要比较低权重行和高权重行：具体来说，权重需要是>= m。然后搜索看起来像这样：
for (i = 0; i < n; ++i)
for (j=n-1; j > i; --j) /* go backwards to take advantage of hmwt */
{
if ( (hmwt(row[i]) + hmwt(row[j])) < m)
break;
try OR of row[i] with row[j] to see if it works, if so record (i,j)
}
4.走向更好的方法 另一种可能提供更好 returns 的方法是选择低汉明权重的列。然后将这些行组合成两组：该列中为 1 的行（A 组）和该列中为 0 的行（B 组）。然后你只需要考虑行的组合，其中一个来自组 A，另一个来自组 B，或者都来自组 A（感谢 @ruakh 发现了我的疏忽）。这些方面的东西应该会有很大帮助。但同样，这仍然是渐近相同的更坏情况，但在实践中应该更快（假设我们不是在所有组合都是答案的情况下）。
5.能做的事情的极限
构建有效向量对数量为 O(n^2) 的示例很容易，因此感觉很难击败 O(m*n^2) 更糟糕的情况。我们应该寻求的是一种与有效对数有某种关联的解决方案。上面的启发式正在朝这个方向发展。如果有一个汉明权重较小的列 h，则上面的第 4 点将 运行 时间降低到 O(h*n*m + h^2*m)。如果 h 明显小于 n，那么你会得到很大的改进。
扩展 TheGreatContini 的想法：
先试试
让我们将其视为查找属于 AxB 的组合，其中包含 A 组行和 B 组行。这些组合必须满足 or 条件，但我们还假设 a 的汉明权重至少与 b 一样大（以避免重复）。
现在将 A 拆分为 A0（以 0 开头的行）和 A1（以 1 开头的行）。对 B 做同样的事情。我们现在已经将问题简化为三个更小的问题：A0xB1、A1xB1 和 A1xB0。如果A和B相同，A0xB1和A1xB0也相同，所以我们只需要做一个。不仅这三个子问题加起来比第一个小，而且我们也完全检查了第一列，从现在开始可以忽略它。
为了解决这些子问题，我们可以使用相同的方法，但现在是第 2、3 列……在某些时候，我们要么检查所有列，要么#A 和#B 为 1。
根据实施情况，越早停止可能效率越高。那时我们可以对剩余的组合进行详尽的检查。请记住，如果我们已经检查了 k 列，那么每个组合的成本仅为 m-k。
更好的专栏selection
正如 TheGreatContini 所建议的，我们可以 select 可以 select 导致最小子问题的列，而不是 select 第一列。在每个步骤中找到该列的成本相当高，但权重可以在开始时计算一次，然后用作最佳列的估计。然后我们可以像往常一样使用算法重新排列列，完成后，再次重新排列它们。
确切的最佳列是 A 中零的数量乘以 B 中零的数量最大的列。
汉明权重p运行ing
我们知道a和b的汉明权重之和至少要有m。因为我们假设 a 是最高的汉明权重，所以我们可以删除 a 的所有汉明权重小于 m/2 的值。 （这提供的加速可能可以忽略不计，我不确定）。计算所有汉明权重的成本为 O(m*n)。
高效拆分
如果我们对行进行排序，使用二分算法可以更快地完成分组。这也可以导致集合在内存中的有效表示。我们可以只指定最小和最大行。排序可以在 O(n*m*log(n)) 中完成。然后可以在大约 log(n).
内完成拆分这里有一些代码无法编译，但应该给出正确的想法。
private List<Row> rows;
public int findFirstOne(int column, int start, int end){
if(rows.get(start).get(column) == 1) return start;
if(rows.get(end).get(column) == 0) return -1;
while(start < end){
int mid = (start+end)/2;
if(rows.get(mid).get(column) == 0){
start = mid+1;
}else{
end = mid;
}
}
return start;
}
复杂度
在下面的计算中，更好的列 selection 的影响被忽略，因为它对最坏情况下的效率几乎没有改善。但是，在一般情况下，它可以通过尽快减少搜索 space 从而使其他检查更快来提供巨大的改进。
算法 运行 时间受 n²m 限制。 然而，我发现的最糟糕的例子都是 O(n*log(n)*m).
首先，矩阵的行排序为 O(n*log(n)*m)，可选地，列排序为 O(n*m + m*log(m))。
然后，子问题的创建。让我们先高估一下。我们最多需要细分 m 次，深度 i 的完整级别细分的成本可能被高估为 log(n)*3^i（每次细分的成本乘以细分数）。这导致总共 O(log(n)*3^m)。
它还必须满足 3^i <= n²/2，因为这是可能的最大组合数，因此对于大 m，它的上限为 O(n²*log(n)*m)。不过，我很难找到一个实际行为像这样的例子。
我认为假设许多子问题很早就变得微不足道是合理的。导致 O(log(n)*m*n)（如果有人想检查这个，我不太确定）。
这是一个现成的想法，可能具有更糟糕的渐近（或什至平均）行为——但它以一种有趣的方式概括，并且至少提供了一种不同的方法。这个问题可以看成一个exact cover problem。 n 行中的每一行都包含来自集合 {1,2,...,m} 的一组值 S，对应于该行具有值 1 的列索引。问题的任务是找到一个集合行的集合形成 {1,2,...m} 的不相交分区。当在一个精确的封面中只有两行这样的行时，这些行是您要查找的那种二元对立的行。但是，可能有更复杂的精确覆盖，例如涉及三行的覆盖：
0 1 0 0 1
1 0 0 0 0
0 0 1 1 0
精确覆盖问题寻找所有个这样的精确覆盖，是一个NP完全问题。规范解是 Algorithm X，由 Donald Knuth 创建。
如果我没记错的话，下面应该是O(n*m):
- 对于每一列，计算在该列中具有“1”的行的索引集，并将其存储为从列索引到行索引集的映射
- 对于每一行，计算可以 "complete" 该行的行索引集（通过添加“1"s in the columns where the row has a "0”）。这可以通过计算在步骤 1 中为相应列计算的集合的交集来完成
- 计算完成的行索引
以你的例子为例：
1 0 1 0 1
0 1 0 0 1
1 1 1 1 0
每列为“1”的行的索引是
- 第 0 列：[0, 2]
- 第 1 列：[1, 2]
- 第 2 列：[0, 2]
- 第 3 列：[2]
- 第 4 列：[0, 1]
用于"filling"每一行的所有索引集合的并集是
- 第 0 行：[2]
- 第 1 行：[2]
- 第 2 行：[]
一共2个
人们对 运行 时间争论不休的主要原因是计算最大 n 的 m 集的交集可以被认为是是 O(m*n)，但我认为这些集合的大小将受到限制：条目要么是 1，要么是 0，当有很多 1 时（并且大小很大），那么相交的集合较少，反之亦然 - 但我没有在这里做严格的证明...
一个基于 Java 的实现，我用来玩这个（以及一些基本的 "tests"）：
import java.util.ArrayList;
import java.util.Arrays;
import java.util.LinkedHashMap;
import java.util.LinkedHashSet;
import java.util.List;
import java.util.Map;
import java.util.Random;
import java.util.Set;
public class SetOrCombinations
{
public static void main(String[] args)
{
List<Integer> row0 = Arrays.asList(1, 0, 1, 0, 1);
List<Integer> row1 = Arrays.asList(1, 1, 0, 0, 1);
List<Integer> row2 = Arrays.asList(1, 1, 1, 1, 0);
List<Integer> row3 = Arrays.asList(0, 0, 1, 1, 1);
List<List<Integer>> rows = Arrays.asList(row0, row1, row2, row3);
run(rows);
for (int m = 2; m < 10; m++)
{
for (int n = 2; n < 10; n++)
{
run(generateRandomInput(m, n));
}
}
}
private static void run(List<List<Integer>> rows)
{
int m = rows.get(0).size();
int n = rows.size();
// For each column i:
// Compute the set of rows that "fill" this column with a "1"
Map<Integer, List<Integer>> fillers =
new LinkedHashMap<Integer, List<Integer>>();
for (int i = 0; i < m; i++)
{
for (int j = 0; j < n; j++)
{
List<Integer> row = rows.get(j);
List<Integer> list =
fillers.computeIfAbsent(i, k -> new ArrayList<Integer>());
if (row.get(i) == 1)
{
list.add(j);
}
}
}
// For each row, compute the set of rows that could "complete"
// the row (by adding "1"s in the columns where the row has
// a "0").
int count = 0;
Set<Integer> processedRows = new LinkedHashSet<Integer>();
for (int j = 0; j < n; j++)
{
processedRows.add(j);
List<Integer> row = rows.get(j);
Set<Integer> completers = new LinkedHashSet<Integer>();
for (int i = 0; i < n; i++)
{
completers.add(i);
}
for (int i = 0; i < m; i++)
{
if (row.get(i) == 0)
{
completers.retainAll(fillers.get(i));
}
}
completers.removeAll(processedRows);
count += completers.size();
}
System.out.println("Count "+count);
System.out.println("Ref. "+bruteForceCount(rows));
}
// Brute force
private static int bruteForceCount(List<List<Integer>> lists)
{
int count = 0;
int n = lists.size();
for (int i = 0; i < n; i++)
{
for (int j = i + 1; j < n; j++)
{
List<Integer> list0 = lists.get(i);
List<Integer> list1 = lists.get(j);
if (areOne(list0, list1))
{
count++;
}
}
}
return count;
}
private static boolean areOne(List<Integer> list0, List<Integer> list1)
{
int n = list0.size();
for (int i=0; i<n; i++)
{
int v0 = list0.get(i);
int v1 = list1.get(i);
if (v0 == 0 && v1 == 0)
{
return false;
}
}
return true;
}
// For testing
private static Random random = new Random(0);
private static List<List<Integer>> generateRandomInput(int m, int n)
{
List<List<Integer>> rows = new ArrayList<List<Integer>>();
for (int i=0; i<n; i++)
{
List<Integer> row = new ArrayList<Integer>();
for (int j=0; j<m; j++)
{
row.add(random.nextInt(2));
}
rows.add(row);
}
return rows;
}
}
这是一种算法，它利用了以下知识：在同一列中具有零的两行将被自动取消作为合作伙伴的资格。当前行中的零越少，我们访问其他行的次数就越少；而且总体上我们拥有的零越多，我们访问其他行的次数就越少。
create two sets, one with a list of indexes of all rows, and the other empty
assign a variable, total = 0
从右到左、从底行到顶部遍历每一行（也可以按其他顺序；我只是这样想象的）。
while row i is not the first row:
call the non-empty set A and the empty set dont_match
remove i, the index of the current row, from A
traverse row i:
if A is empty:
stop the traversal
if a zero is encountered:
traverse up that column, visiting only rows listed in A:
if a zero is encountered:
move that row index from A to dont_match
the remaining indexes in A point to row partners to row i
add their count to total and move the elements from the
shorter of A and dont_match to the other set
return total