在矩阵中找到k个不相交的行组

Question

问题陈述：设S为整数的集合，例如 S = {1,2,...,12}。M是一个整数矩阵，其行可以视为S的子集，其长度除以S的元素数量，特别地，M的每一行仅包含不同的元素/整数。我试图编写Matlab代码，可以识别所有不相交行组成的组，其集合论并给出S（即具有固定大小的子集的S的分区），并将每个这样的组作为矩阵返回。

例子：A = [1 2 5 6; 3 4 11 12; 9 10 7 8]是S的一个分区，而B = [1 2 3 4; 5 6 7 8; 9 10 11 12; 1 5 9 12]不是S的分区（因为最后一行与前3行不相交）。

数量级：通常，M将具有约500,000行，S将具有多达100个元素。

迄今为止的方法：让m = size(M,1), n = size(M,2)（分区子集的大小），s = |S|（要分区的集合的大小）和k = s/n（必须不相交的行数以形成分区 - 您可以假设s = 0 mod n，因此问题是明确定义的）。请注意，为了建立这样的分区，仅需检查行的不相交性以及确切地有k个这样的行。

对于j = 1:(m-k+1)，我观察ind = (sum(ismember(M((j+1):m,:),M(j,:)),2)==0)，它给出了与它不相交的M（j，：）之后的行的索引列。然后，通过将M（j，：）与每个这些行组合来创建2 x n矩阵。之后，我想重复ismember()例程，并使用所有这些新的2 x n矩阵重复，直到获得k x n矩阵。这可能很好，但这也是我跌倒的地方，因为首先for-routines的数量取决于k。

问题：如何完成我的方法的代码？

(Q2) 是否有更好的解决此问题的方法（例如更快，矢量化/少用for循环，GPU辅助等），如果有，它们是什么？

- M.G.

---

M通常有多少列，例如n？S是否总是具有唯一的整数集合？ - Divakar

如果我没记错的话，n 不应超过8或9。对于 S，可以假设 S = unique(M)，即 S 中的所有元素已经在 M 中存在。 S 中的所有元素都是不同的，它们的顺序并不重要。希望我对你的第二个问题理解正确。 - M.G.

@July：在你的大多数问题中，“M”是输入矩阵的名称，但在示例中，“M”是可能的解决方案，请在那里重新命名它。至少我们知道你的解决方案的大小为“numel(S)”，这允许尝试近似并在达到此大小时停止。你能提供一个数据集的例子吗？ - Daniel

对于Q2 - 我建议您不要优化，先让一些方法运行起来。“过早的优化是万恶之源”。 - gabe

这涉及检查nchoosek(m,s)行组合，这是_很多_。对于m = 5e5和s = 3，大约有2e16个组合。即使每个组合只有1e-6秒的时间，也需要大约600年。 - Luis Mendo

Answer 1

这个问题是精确覆盖的一个普通案例。如果您在使用C，我建议您使用Knuth's Algorithm X，并用位数组来实现，而不是跳舞链表，因为您关心的实例明显比较密集。我相信MATLAB也可以很好地满足您的需求。

将整数集合{1, 2, 5, 6}表示为2**1 + 2**2 + 2**5 + 2**6。然后两个集合的交集表示为它们表示的按位与，并集则为按位或。空集为0。不幸的是，对于S = 100，您需要使用两个或更多整数，这会使事情变得复杂。在获取集合后，您可以通过矢量化的bitand检测与其他集合的交集。

- David Eisenstat

---

逻辑稀疏矩阵可能是实现它的一种替代方案。 - Daniel

@Daniel 如果按照我的预期实现，那么交集的运行时间将从二次降至线性，但不会利用单词并行性。无论如何，我预计关键的改进在于使用具有良好列顺序的算法X。 - David Eisenstat

感谢您指引我使用Knuth的X算法，至少在理论上，它可以解决我的问题。 - M.G.

Answer 2

这是你想要的吗？ 我假设M中行的顺序很重要（即交换2行是另一个有效的M）。 此示例为您提供了所有具有2列和3行的矩阵，其中元素均不同且在{1,2,3,4,5,6}中。但是，行是{1,2,3,4,5,6}的子集，其中顺序不重要。不确定这是否是您想要的。如果顺序很重要，我们可以添加perms以获取由nchoosek返回的每行的所有可能排列。

我必须使用递归函数，因此您需要将其放入文件中：

function test()
    s = 1:6;
    n = 2;

    M_all = ProcessOneRow(s, n, {}, {});

    disp('All possilbe M:')
    M_all
end

function M_all = ProcessOneRow(s, n, cRows, M_all)

    %// find all possible rows for this level
    possibleRows = nchoosek(1:length(s), n);

    for t=1:size(possibleRows, 1)
        %// keep track of all rows so far
        cRows(end+1) = s(possibleRows(t,:));

        %// get elements remaining (remove this row)
        s_sub = s;
        s_sub(possibleRows(t,:)) = [];

        if isempty(s_sub)
            %// We found a new complete matrix M
            M = [];
            for p = 1:numel(cRows)
                M(p,:) = cRows{p};
            end
            M_all{end+1} = M;
        else
            %// Still not a complete M, so we process the rest
            M_all = ProcessOneRow(s_sub, n, cRows, M_all);
        end
        cRows(end) = [];
    end
end

- nicolas