# Constrained partitions of 1:K

i’m trying to find all partitions of 1:K that satisfy some criteria:
take all partitions so that there are n subsets of size 2, h subsets of size 3, and all other subsets singletons.
I can probably come up with something that runs very slowly, but wanted to ask here first in case there is a known function that could do it? I’ve looked into Combinatorics package but it doesn’t seem to have that.
Thanks!

This would not be calling `filter` (or using a `for` with an `if` inside) over the return of `powerset`?

1 Like

Using Henrique_Becker’s tip, I came up with a bit of a messy solution that works for my purposes:

``````using Combinatorics

function is_conset(subs)
#checks if given set is connected when integer elemnents
if length(subs) > 1
for i in 1:length(subs)-1
if subs[i+1] - subs[i] != 1
return false
end
end
end
return true
end

function is_connected_partition(partition)
#doesnt really ask for partitions, but checks whether all elements of collection are connected
for subset in partition
if !is_conset(subset)
return false
end
end
return true
end

function is_partition(parti)
#doesnt really ask for partition, but checks if all elements of collection have empty intersection
T = length(parti)
for (ind,subs) in enumerate(parti)
for j in (ind+1):T
if !isempty(intersect(subs,parti[j]))
return false
end
end
end
return true
end

function gen_parti(pt::Vector{Vector{Int64}},n::Int64)
#for collection of subsets pt, take all combinations of n elements and include them if they have empty intersection
T = length(pt)
parti_set = []
for indset in combinations(1:T,n)
if is_partition(pt[indset])
push!(parti_set,pt[indset])
end
end
return parti_set
end

function connected_partitions(K::Int64, n1::Int64, k1::Int64, n2::Int64, k2::Int64, n3::Int64, k3::Int64)
#generate partitions of numbers 1:K formed by connected subsets that satisfy: n_i subsets of size k_i, i=1,2,3
partitions = []
for part3 in combinations(1:K, k3*n3)
remaining3 = setdiff(1:K, part3)
for part2 in combinations(remaining3, k2*n2)
remaining2 = setdiff(remaining3, part2)
for part1 in combinations(remaining2, k1*n1)
remaining1 = setdiff(remaining2, part1)
singletons = [[s] for s in collect(remaining1)]
p1set = filter(is_conset,collect(powerset(part1,k1,k1))) #all connected subsets of size k1 of part1
p2set = filter(is_conset,collect(powerset(part2,k2,k2))) #all connected subsets of size k2 of part2
p3set = filter(is_conset,collect(powerset(part3,k3,k3))) #all connected subsets of size k3 of part3
for partset1 in gen_parti(p1set,n1)
for partset2 in gen_parti(p2set,n2)
for partset3 in gen_parti(p3set,n3)
partition = union(partset1,partset2,partset3,singletons)
push!(partitions, partition)
end
end
end
end
end
end
return partitions
end

``````