# Help speedup a brute-force solution

The following function calculates all possible subsets of a set `1:n` such that all subsets are primes. This is only a brute-force algorithm to test a solution, so it’s too slow as expected. The number of allocations is huge because of too many short vectors generated from partitioning of an n-element vector. How can I improve upon this a bit? I tried multithreading and got a best-case of 2X speedup because this seems memory bound.

``````using Primes
using Combinatorics

function mprime(k)
v = 1
n = 0
for i in k
n += v*i
v *= 10
end
isprime(n)
end

function brute118(n)
p = permutations(1:n)
r = partitions.(p)
s = Set{Vector{Vector{Int64}}}()
for i in r
for j in i
valid = true
for k in j
mprime(k) || (valid = false; break)
end
valid && push!(s,sort(j))
end
end
length(s)
end

n = 7
@time brute118(n)
2.086856 seconds (45.65 M allocations: 2.937 GiB, 16.69% gc time)
1205
``````

Can you use views?

Yes, I tried views, but it made no difference. I guess because the vectors are short (many are of length 1 already), the view is no lighter than the vector itself. I’m thinking of writing a version of `partition` that returns a vector of numbers directly instead of vector of vectors, it would be much faster.

1 Like

I would try to find where are these allocations and if they are in the functions maybe modify them to use views and other non-allocating paradigms

2 Likes

`partitions` generate new vectors on each iteration, so there is no way to avoid allocations. You can try to rewrite algorithm without using `partitions` (roll out your own allocation free implementation)

don’t get what this is saying, i think it’s not precise

to make slightly more clear what you are doing, your `mprime` is

`mprime(k)=isprime(evalpoly(10,k))`

and thus your code could be

``````mprime(k)=isprime(evalpoly(10,k))

function brute118(n)
p = permutations(1:n)
r = partitions.(p)
s =[sort(j) for i in r, j in i if all(mprime,j)]
length(s)
end
``````

I would suggest to directly write a backtrack algorithm to generate your partitions. Like this, you can avoid allocations, and you can easily add pruning. (Whenever you build a subset of your partition, you can already check if it is prime, this will prune a significant portion of the search space).
Looking at your definition of mprime, you can also prune if the first element of your subset is 5 or an even number (if your subset contain more than 1 element)

2 Likes

I wrote my version of `partition` using recursion which is quite slow. But the problem is not speed here because I thought I will be able to generate significantly fewer candidates which are all primes. It turns out to be extremely difficult to intervene in the algorithm below because the subsets are built recursively and I can’t predict which subset will end up not being prime. Any ideas?

``````function partition(collection::AbstractVector{T}) where T
length(collection) == 1 && return [[collection]]
result = Vector{Vector{Vector{T}}}(undef,0)
first = collection
for smaller in partition(collection[2:end])
# insert `first` in each of the subpartition's subsets
for n in eachindex(smaller)
push!(result, [smaller[1:n-1]..., [first; smaller[n]], smaller[n+1:end]...])
end
# put `first` in its own subset
push!(result, [[first],smaller...])
end
return result
end

println.(partition(1:3))
[[1, 2, 3]]
[, [2, 3]]
[[1, 2], ]
[, [1, 3]]
[, , ]
``````

This is very nice and terse, but the comprehension complains about `i is not defined`.

Well, thank you all for your contributions, I learned from this a lot. Now when I think about it again, I realize that I was doing too many permutations prior to partitioning which resulted in too many repeated sets, most of them are not prime. Here I reversed that order and permuted only needed subsets. It is significantly faster now with few allocations.

``````using Primes
using Combinatorics

mprime(k) = isprime(evalpoly(10,k))

function brute1180(n)
total = 0
for i in partitions(1:n)
mul = 1
for j in i
mul *= sum(mprime, permutations(j))
mul == 0 && break
end
total += mul
end
total
end

@btime brute1180(7)
4.647 ms (77712 allocations: 6.37 MiB)
1205
``````
1 Like

Sorry, it should have been

`s =[sort(j) for i in r for j in i if all(mprime,j)]`

3 Likes

You can still gain more time with good pruning rules.
Consider the following property (in base 10) :
if `sum(k) = 0 mod 3` and `k!=`, then `mprime(permutation(k)) = false` for all `permutation(k)`
For the generation of partitions, if one of the subsets have this property, then you don’t need to generate all the partitions containing this subset. You can make your own algorithm for generating partitions or maybe adapt the ones from Combinatorics.
You can also prune a subset `k` of a partition if `gcd(k) != 0 && ( length(k)>1 || !isprime(k) )`
Edit : When you have generated a subset of your partition, after checking the two previous conditions, you can also already list the prime permutations. Like this, if there is none, you can already prune this subset.

For the generation of the permutations, you can prune the permutations where the first element is 5 or an even number (in base 10).

2 Likes