0

给定一个包含 20 个数字的数组，我想提取两组的所有可能组合，每组有 10 个数字，顺序并不重要。

combinations([1, 2, 3], 2)

in Julia 会给我从数组中提取的两个数字的所有可能组合，但我还需要那些未绘制的数字......

4

3 回答 3

1

在玩了一会儿之后，我想出了这个代码，它似乎有效。我相信它可以写得更优雅，等等。

function removeall!(remove::Array, a::Array)
    for i in remove
        if in(i, a)
            splice!(a, indexin([i], a)[1])
        end
    end
end

function combinationgroups(a::Array, count::Integer)
    result = {}
    for i in combinations(a, count)
        all = copy(a)
        removeall!(i, all)
        push!(result, { i; all } )
    end
    result
end

combinationgroups([1,2,3,4],2)

6-element Array{Any,1}:
 {[1,2],[3,4]}
 {[1,3],[2,4]}
 {[1,4],[2,3]}
 {[2,3],[1,4]}
 {[2,4],[1,3]}
 {[3,4],[1,2]}
于 2013-10-04T16:09:12.563 回答
1

您可以使用setdiff来确定任何向量中缺少的项目，例如，

y = setdiff(1:5, [2,4])

产量[1,3,5]。

于 2013-10-04T09:46:00.280 回答
0

基于@tholy关于而不是使用实际数字的评论，我可以使用位置（以避免数字不唯一的问题）和 setdiff 来获得“其他组”（未选择的数字），我想出了以下. 第一个函数根据索引从数组中获取值（即 arraybyindex([11,12,13,14,15], [2,4]) => [12,14]）。这似乎可能是标准库的一部分（我确实寻找过它，但可能错过了它）。

第二个函数执行组合组在上面所做的工作，创建一定大小的所有组及其互补项。它可以自己调用，也可以通过第三个函数调用，该函数提取所有可能大小的组。有可能这一切都可以写得更快，更惯用。

function arraybyindex(a::Array, indx::Array)
    res = {}
    for e in indx
        push!(res, a[e])
    end

    res
end
function combinationsbypos(a::Array, n::Integer)
    res = {}
    positions = 1:length(a)
    for e in combinations(positions, n)          
        push!(res, { arraybyindex(a, e) ; arraybyindex(a, setdiff(positions, e)) })
    end
    res
end

function allcombinationgroups(a::Array)
    maxsplit = floor(length(a) / 2)
    res = {}
    for e in 1:5
        println("Calculating for $e, so far $(length(res)) groups calculated")
        push!(res, combinationsbypos(a, e))
    end
    res
end

在 3 岁的 MacBook Pro 上在 IJulia 中运行它

@time c=allcombinationgroups([1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20])
println(length(c))
c

Calculating for 1, so far 0 groups calculated
Calculating for 2, so far 20 groups calculated
Calculating for 3, so far 210 groups calculated
Calculating for 4, so far 1350 groups calculated
Calculating for 5, so far 6195 groups calculated
Calculating for 6, so far 21699 groups calculated
Calculating for 7, so far 60459 groups calculated
Calculating for 8, so far 137979 groups calculated
Calculating for 9, so far 263949 groups calculated
Calculating for 10, so far 431909 groups calculated
elapsed time: 11.565218719 seconds (1894698956 bytes allocated)
Out[49]:
616665

616665-element Array{Any,1}:
 {{1},{2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20}}
 {{2},{1,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20}}
  ⋮                                                       
 {{10,12,13,14,15,16,17,18,19,20},{1,2,3,4,5,6,7,8,9,11}}
 {{11,12,13,14,15,16,17,18,19,20},{1,2,3,4,5,6,7,8,9,10}}

IE。每秒计算 53,334 个组。

相比之下，使用相同的外部 allcombinationgroups 函数，但是用对 combinationgroups 的调用替换对 combinationbypos 的调用（参见上一个答案），速度要慢 10 倍。

然后，我按照@tholy 的建议，使用 true 或 false 标志按索引组重写了数组（我不知道如何使用 [] 使其工作，所以我明确地使用了 setindex！，并将其移动到一个函数中。另外 10 倍加速！1 秒内 616,665 组！

最终代码（到目前为止）：

function combinationsbypos(a::Array, n::Integer)
    res = {}
    positions = 1:length(a)
    emptyflags = falses(length(a))
    for e in combinations(positions, n)       
        flag = copy(emptyflags)
        setindex!(flag, true, e)
        push!(res, {a[flag] ; a[!flag]} )
    end
    res
end

function allcombinationgroups(a::Array)
    maxsplit = floor(length(a) / 2)
    res = {}
    for e in 1:maxsplit
        res = vcat(res, combinationsbypos(a, e))
    end
    res
end
于 2013-10-06T23:56:16.623 回答