# Generate all subsets of a set

Hi, I’m very new in Julia, & I really need help to generate all subsets of a set.
For example: I have a set [1, 2, 3, 4, 5], then I need to generate all subsets from it, such [[1,2], [1,3], [2,3],…[2,3,4], …[2,3,4,5], etc]. Is there any suggestion about it?

4 Likes

Or if you’re bored:

``````cur_input_list = [1,2,3,4,5]

function foo(cur_input_list, cur_output_list=[], cur_set_lists=[])
for (cur_index, cur_value) in enumerate(cur_input_list)
tmp_input_list = cur_input_list[cur_index+1:end]
tmp_output_list = deepcopy(cur_output_list)
push!(tmp_output_list, cur_value)

push!(cur_set_lists, tmp_output_list)
foo(tmp_input_list, tmp_output_list, cur_set_lists)
end

cur_set_lists
end

foo(cur_input_list)
``````
2 Likes

This is called the “powerset”. Google Julia powerset and you’ll get several results in addition to `Combinatorics.jl`.

Here is the Julia entry from rosettacode.org:

``````function powerset(x::Vector{T}) where T
result = Vector{T}[[]]
for elem in x, j in eachindex(result)
push!(result, [result[j] ; elem])
end
result
end
``````
3 Likes

Thank you so much for all of your kindly helps! Really help me as a new beginner.

But I still have a problem with function powerset. Here is what I get for powerset([1,2,3,4],2):

IterTools.Chain{Tuple{Combinatorics.Combinations{Array{Int64,1}},Combinatorics.Combinations{Array{Int64,1}},Combinatorics.Combinations{Array{Int64,1}}}}((Combinatorics.Combinations{Array{Int64,1}}([1, 2, 3, 4], 2), Combinatorics.Combinations{Array{Int64,1}}([1, 2, 3, 4], 3), Combinatorics.Combinations{Array{Int64,1}}([1, 2, 3, 4], 4)))

How is the user supposed to obtain the subsets out of this?

``````julia> using Combinatorics
julia> collect(powerset([:a, :b, :c]))
8-element Array{Array{Symbol,1},1}:
[]
[:a]
[:b]
[:c]
[:a, :b]
[:a, :c]
[:b, :c]
[:a, :b, :c]
``````
3 Likes

Note that in most cases where you’re subsequently iterating over that set of subsets you don’t need to `collect` but rather you can use the result of `powerset` directly.

4 Likes

Great! This was the fastest response ever. Thanks!

How to use IterTools ? does this still work in Julia? I was using JuliaBox and I added Pkg.(“IterTool”)
But could not use subsets the error was subset not defined?

What exactly didn’t work?
Btw. The function `powerset` comes from the package “Combinatorics.jl” and still works on Julia 1.2.

I went to https://juliacollections.github.io/IterTools.jl/latest/ and copied `Pkg.add("IterTools")`
and copied
for i in subsets([1, 2, 3])
@show i
end
and an error code stated could not find subsets

Did you also `using` IterTools ?

``````(v1.4) pkg> add IterTools
Updating registry at `~/.julia/registries/General`
Updating git-repo `https://github.com/JuliaRegistries/General.git`
Resolving package versions...
Installed Compat ────── v2.2.0
Installed Polynomials ─ v0.5.3
Updating `~/.julia/environments/v1.4/Project.toml`
[c8e1da08] + IterTools v1.2.0
Updating `~/.julia/environments/v1.4/Manifest.toml`
[34da2185] ↑ Compat v2.1.0 ⇒ v2.2.0
[c8e1da08] + IterTools v1.2.0
[f27b6e38] ↑ Polynomials v0.5.2 ⇒ v0.5.3

julia> using IterTools
[ Info: Precompiling IterTools [c8e1da08-722c-5040-9ed9-7db0dc04731e]

julia> collect(subsets([1,2,3]))
8-element Array{Array{Int64,1},1}:
[]
[1]
[2]
[1, 2]
[3]
[1, 3]
[2, 3]
[1, 2, 3]
``````