Получение всех комбинаций разбиения массива на две группы с одинаковым размером в Julia

Question

Учитывая массив из 20 чисел, я хотел бы извлечь все возможные комбинации из двух групп с десятью числами в каждом, порядок не важен.

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

в Джулии даст мне все возможные комбинации двух чисел, взятых из массива, но мне нужны те, которые не были нарисованные ...

Answer 1

Вы можете использовать setdiff для определения элементов отсутствует в любом векторе, например

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

дает [1,3,5].

Answer 2

Поиграв немного, я придумал этот код, который, похоже, работает. Я уверен, что это могло быть написано гораздо более элегантно, и т.д.

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

Answer 3

на основе @ Толи своего комментария о вместо использования фактических цифр, я мог бы использовать позиции (чтобы избежать проблем с цифрой не является уникальной) и 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 

Запуск этого в IJulia на 3-летний MacBook Pro дает

@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}} 

т.е.. 53,334 группы, рассчитанных в секунду.

В отличие от этого, используя ту же внешнюю функцию allcombinationgroups, но заменяя вызов комбинациям bypos с вызовом в комбинированные группы (см. Предыдущий ответ), в 10 раз медленнее.

Затем я переписал массив по группам индексов с использованием флагов истины или флагов, предложенных @tholy (я не мог понять, как заставить его работать с помощью [], поэтому я использовал setindex! Явным образом и переместил его в один функция Другой 10x убыстрения 616,665 группы в 1 секунду

Заключительного коде (пока).!

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