Constrained partitions of 1:K

General Usage
1

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!

2

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

1 Like
3

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