Julia -生成2匹配的奇集

Question

在Julia中，给定长度大于3的Set{Tuple{Int, Int}}命名为S，例如:

julia> S = Set{Tuple{Int,Int}}([(1, 4), (2, 5), (2, 6), (3, 6)])
Set{Tuple{Int64,Int64}} with 4 elements:
(2, 5)
(3, 6)
(2, 6)
(1, 4)

我想返回S的子集T，其长度大于3，并且奇数(3,5,7，…)，使得元组的所有第一个值都是唯一的。例如，我不能有(2,5)和(2,6)因为第一个值2不是唯一的。这同样适用于第二个值，这意味着我不能有(2,6)和(3,6)。

如果不可能，返回一个空的Set of Tuple也可以。

最后，对于上面的最小示例，代码应该返回:

julia> T = Set{Tuple{Int,Int}}([(1, 4), (2, 5), (3, 6)])
Set{Tuple{Int64,Int64}} with 3 elements:
(2, 5)
(3, 6)
(1, 4)

如果你认为它比Set{Tuple{Int, Int}}更好，我真的愿意接受任何其他类型的结构:)

我知道怎么用整数编程。然而，我将在大型实例中运行多次，我想知道是否有更好的方法，因为我深深地认为它可以在多项式时间内完成，也许在Julia中使用聪明的map或其他有效的函数!

Answer 1

您需要的是一种过滤集合中成员的可能组合的方法。创建一个过滤函数。如果这部分是关于奇数[3,5,7…]您提到的]序列适用于这里，不知何故，您可能需要将其添加到下面的过滤器逻辑:

using Combinatorics
allunique(a) = length(a) == length(unique(a))
slice(tuples, position) = [t[position] for t in tuples]
uniqueslice(tuples, position) = allunique(slice(tuples, position))
is_with_all_positions_unique(tuples) = all(n -> uniqueslice(tuples, n), 1:length(first(tuples)))

现在你可以找到组合了。有了大的集合，这些会爆炸的数量，所以一定要退出，当你有足够的。你可以用Lazy。这里的Jl，或者只是一个函数:

function tcombinations(tuples, len, needed)
printed = 0
for combo in combinations(collect(tuples), len)
if is_with_all_positions_unique(combo)
printed += 1
println(combo)
printed >= needed && break
end
end
end
tcombinations(tuples, 3, 4)
[(2, 5), (4, 8), (3, 6)]
[(2, 5), (4, 8), (1, 4)]
[(2, 5), (4, 8), (5, 6)]
[(2, 5), (3, 6), (1, 4)]