Generate all subsets of a set

General Usage
,
1

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?

2
4 Likes
3

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

Specifically, https://github.com/JuliaMath/Combinatorics.jl/blob/60a2343af0dfc54ab01af6bb2f21d0b5a51fb729/src/combinations.jl#L268-L280

2 Likes
5

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
6

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

7

Thanks for your help!

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?

8 
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
9

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
10

Great! This was the fastest response ever. Thanks!

11

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?

12

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

13

I went to Introduction · IterTools 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

14

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]