all subset of a se in julia

user_8417332 0
Viewed 1385

would you please help me? How can I do a code which can find all subset of a set

for example

I want to code this constraint in Julia. It is a subtour constraint. But I don't know how I can find all subsets of S set.

enter image description here

@constraint(ILRP,
            c7[k in totalK, t in totalH],
            sum(x[i,j,k,t] for i=1:totalS, j=1:totalS)<=size(S)-1);

Thanks very much

julia-jump julia
2 Answers

You can get it using powerset function from the Combinatorics.jl package, e.g.:

julia> using Combinatorics

julia> x = [1:5;]
5-element Array{Int64,1}:
 1
 2
 3
 4
 5

julia> powerset(x)
Base.Iterators.Flatten{Array{Combinatorics.Combinations{Array{Int64,1}},1}}(Combinatorics.Combinations{Array{Int64,1}}[Combinations{Array{Int64,1}}([1, 2, 3, 4, 5], 0), Combinations{Array{Int64,1}}([1, 2, 3, 4, 5], 1), Combinations{Array{Int64,1}}([1, 2, 3, 4, 5], 2), Combinations{Array{Int64,1}}([1, 2, 3, 4, 5], 3), Combinations{Array{Int64,1}}([1, 2, 3, 4, 5], 4), Combinations{Array{Int64,1}}([1, 2, 3, 4, 5], 5)])

julia> collect(powerset(x))
32-element Array{Array{Int64,1},1}:
 []
 [1]
 [2]
 [3]
 [4]
 [5]
 [1, 2]
 [1, 3]
 [1, 4]
 [1, 5]
 [2, 3]
 [2, 4]
 [2, 5]
 [3, 4]
 [3, 5]
 [4, 5]
 [1, 2, 3]
 [1, 2, 4]
 [1, 2, 5]
 [1, 3, 4]
 [1, 3, 5]
 [1, 4, 5]
 [2, 3, 4]
 [2, 3, 5]
 [2, 4, 5]
 [3, 4, 5]
 [1, 2, 3, 4]
 [1, 2, 3, 5]
 [1, 2, 4, 5]
 [1, 3, 4, 5]
 [2, 3, 4, 5]
 [1, 2, 3, 4, 5]

Note that by default powerset returns an iterator to avoid allocating all subsets. Also you can pass a second and third positional argument to powerset to limit minimum and maximum size of the returned subset, e.g.:

julia> collect(powerset(x, 2, 3))
20-element Array{Array{Int64,1},1}:
 [1, 2]
 [1, 3]
 [1, 4]
 [1, 5]
 [2, 3]
 [2, 4]
 [2, 5]
 [3, 4]
 [3, 5]
 [4, 5]
 [1, 2, 3]
 [1, 2, 4]
 [1, 2, 5]
 [1, 3, 4]
 [1, 3, 5]
 [1, 4, 5]
 [2, 3, 4]
 [2, 3, 5]
 [2, 4, 5]
 [3, 4, 5]
user_12695670

Don't know whether this is what you seek:

using Combinatorics

   function subsets(A::AbstractArray,r::Union{AbstractArray,Integer})
  o= Array{Array{eltype(A),1},1}(undef,0)         
  if typeof(r)<:Integer
      r>length(A) && (r=[length(A)])
      r=[r...]
  elseif typeof(r)<:UnitRange
      r[end]>length(A) && (r=1:r[length(A)])
  else
      !issubset(r,1:length(A)) && (r=intersect(r,1:length(A)))
  end
  for n = r
      a=combinations(A,n)
      for i in a     
          push!(o,i)
      end
  end
  return o
end

subsets(A::AbstractArray) = subsets(A,1:length(A))

It can List all Subsets or Subsets up to a certain limit (length): eg:

 julia> subsets(1:3)
 7-element Array{Array{Int64,1},1}:
  [1]
  [2]
  [3]
  [1, 2]
  [1, 3]
  [2, 3]
  [1, 2, 3]
  julia> subsets(1:3,2)
  3-element Array{Array{Int64,1},1}:
  [1, 2]
  [1, 3]
  [2, 3]
user_99366470
Related