CODEWITHSUNDEEP
juliacombinatorics
Mason
Mason

Reputation: 3051

Making a function to build a particular set of combinations

I'm trying to make a function f such that

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

and so on. Anyone have any clever ideas on how to generate this programmatically? I'm sure there's some fancy name for this operation but I'm not sure what it is.

Upvotes: 2

Views: 107

Answers (2)

Mason
Mason

Reputation: 3051

Two answers which were suggested to me on the julialang slack:

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

Upvotes: 1

Moritz Schauer
Moritz Schauer

Reputation: 1417

The combinatorics package has this:

using Combinatorics

combinations(1:n) # iterator of all combinations

For example

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

Note that combinations is an iterator, you can use it in a for loop

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

without creating all combinations in memory at once (you only create them if you collect the iterator). combinations returns a Vector instead of a tuple so that the type of c does not change from iteration to iteration.

There is some additional information at https://discourse.julialang.org/t/generate-all-subsets-of-a-set/12810/10.

Upvotes: 5

Related Questions