Создание функции для построения определенного набора комбинаций

Question

Я пытаюсь сделать функцию f такой, чтобы

f(1) == ((1,),)
f(2) == ((1,), (2,), (1,2))
f(3) == ((1,), (2,), (3,), (1,2), (1,3), (2,3), (1,2,3))
f(4) == ((1,), (2,), (3,), (4,), (1,2), (1,3), (1,4), (2,3), (2,4), (3,4), (1,2,3), (1,2,4), (1,3,4), (2,3,4), (1,2,3,4))

и так далее.У кого-нибудь есть какие-нибудь умные идеи о том, как сгенерировать это программно?Я уверен, что есть какое-то причудливое название для этой операции, но я не уверен, что это такое.

Answer 1

Пакет комбинаторики имеет следующее:

using Combinatorics

combinations(1:n) # iterator of all combinations

Например,

julia> collect(combinations(1:3))
7-element Array{Array{Int64,1},1}:
 [1]      
 [2]      
 [3]      
 [1, 2]   
 [1, 3]   
 [2, 3]   
 [1, 2, 3]

Обратите внимание, что комбинации - это итератор, вы можете использовать его в цикле for

for c in combinations(1:n)
    ...
end

без создания всех комбинаций в памяти сразу (вы создаете их, только если вы collect итератор).combinations возвращает Vector вместо кортежа, так что тип c не меняется от итерации к итерации.

Существует некоторая дополнительная информация в https://discourse.julialang.org/t/generate-all-subsets-of-a-set/12810/10.

Answer 2

Два ответа, которые были предложены мне на провисании julialang:

using Combinatorics

f(n) = unique(sort.(vcat([collect(permutations(1:n, i)) for i in 1:n]...)))

jointuple(x,y) = (x...,y...)
function f(x) 
    if x == 0
        []
    elseif x == 1
        [(1,);]
    else 
        a = f(x-1) 
        vcat(a,(x,),map(z->jointuple(z,x),a)) 
    end 
end