Julia

Question

在 Julia 中，给定一个名为 S 且长度大于 3 的 Set{Tuple{Int, Int}}，例如：

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)

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

如果不可能，return一个空的元组集就可以了。

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

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)]

Julia - 生成 2 个匹配的奇数集

Julia - Generate 2-matching odd Set

optimization

graph

set

time-complexity