# Help speedup a brute-force solution
**URL:** https://discourse.julialang.org/t/help-speedup-a-brute-force-solution/62894
**Category:** Performance
**Tags:** combinatorics
**Created:** [June 14, 2021, 3:28pm UTC](https://discourse.julialang.org/t/help-speedup-a-brute-force-solution/62894 "2021-06-14T15:28:27Z")
**Posts on this page:** 14
**Page:** 1
### Author:  [@Seif\_Shebl](https://discourse.julialang.org/u/Seif_Shebl)
#### Post date: [June 14, 2021, 3:28pm UTC](https://discourse.julialang.org/t/help-speedup-a-brute-force-solution/62894/1 "2021-06-14T15:28:28Z")
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.
```julia
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
```
---
### Author:  [@gbaraldi](https://discourse.julialang.org/u/gbaraldi)
#### Post date: [June 14, 2021, 5:44pm UTC](https://discourse.julialang.org/t/help-speedup-a-brute-force-solution/62894/2 "2021-06-14T17:44:39Z")
Can you use views?
---
### Author:  [@Seif\_Shebl](https://discourse.julialang.org/u/Seif_Shebl)
#### Post date: [June 14, 2021, 6:13pm UTC](https://discourse.julialang.org/t/help-speedup-a-brute-force-solution/62894/3 "2021-06-14T18:13:59Z")
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.
---
### Author:  [@gbaraldi](https://discourse.julialang.org/u/gbaraldi)
#### Post date: [June 14, 2021, 6:16pm UTC](https://discourse.julialang.org/t/help-speedup-a-brute-force-solution/62894/4 "2021-06-14T18:16:04Z")
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
---
### Author:  [@Skoffer](https://discourse.julialang.org/u/Skoffer)
#### Post date: [June 14, 2021, 6:25pm UTC](https://discourse.julialang.org/t/help-speedup-a-brute-force-solution/62894/5 "2021-06-14T18:25:58Z")
`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)
---
### Author:  [@xiaodai](https://discourse.julialang.org/u/xiaodai)
#### Post date: [June 16, 2021, 5:29am UTC](https://discourse.julialang.org/t/help-speedup-a-brute-force-solution/62894/6 "2021-06-16T05:29:42Z")
> [@Seif\_Shebl](#):
>
> `n` such that all subsets are primes
don’t get what this is saying, i think it’s not precise
---
### Author:  [@Jean\_Michel](https://discourse.julialang.org/u/Jean_Michel)
#### Post date: [June 16, 2021, 7:04am UTC](https://discourse.julialang.org/t/help-speedup-a-brute-force-solution/62894/7 "2021-06-16T07:04:28Z")
to make slightly more clear what you are doing, your `mprime` is
`mprime(k)=isprime(evalpoly(10,k))`
---
### Author:  [@Jean\_Michel](https://discourse.julialang.org/u/Jean_Michel)
#### Post date: [June 16, 2021, 7:17am UTC](https://discourse.julialang.org/t/help-speedup-a-brute-force-solution/62894/8 "2021-06-16T07:17:27Z")
and thus your code could be
```julia
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
```
---
### Author:  [@etienne\_dg](https://discourse.julialang.org/u/etienne_dg)
#### Post date: [June 16, 2021, 8:20am UTC](https://discourse.julialang.org/t/help-speedup-a-brute-force-solution/62894/9 "2021-06-16T08:20:21Z")
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)
---
### Author:  [@Seif\_Shebl](https://discourse.julialang.org/u/Seif_Shebl)
#### Post date: [June 17, 2021, 6:25pm UTC](https://discourse.julialang.org/t/help-speedup-a-brute-force-solution/62894/10 "2021-06-17T18:25:42Z")
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?
```julia
function partition(collection::AbstractVector{T}) where T
length(collection) == 1 && return [[collection]]
result = Vector{Vector{Vector{T}}}(undef,0)
first = collection[1]
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]]
[[1], [2, 3]]
[[1, 2], [3]]
[[2], [1, 3]]
[[1], [2], [3]]
```
---
### Author:  [@Seif\_Shebl](https://discourse.julialang.org/u/Seif_Shebl)
#### Post date: [June 17, 2021, 6:29pm UTC](https://discourse.julialang.org/t/help-speedup-a-brute-force-solution/62894/11 "2021-06-17T18:29:24Z")
> [@Jean\_Michel](#):
>
> `s =[sort(j) for i in r, j in i if all(mprime,j)]`
This is very nice and terse, but the comprehension complains about `i is not defined`.
---
### Author:  [@Seif\_Shebl](https://discourse.julialang.org/u/Seif_Shebl)
#### Post date: [June 17, 2021, 9:15pm UTC](https://discourse.julialang.org/t/help-speedup-a-brute-force-solution/62894/12 "2021-06-17T21:15:12Z")
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.
```julia
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
```
---
### Author:  [@Jean\_Michel](https://discourse.julialang.org/u/Jean_Michel)
#### Post date: [June 17, 2021, 9:54pm UTC](https://discourse.julialang.org/t/help-speedup-a-brute-force-solution/62894/13 "2021-06-17T21:54:44Z")
Sorry, it should have been
`s =[sort(j) for i in r for j in i if all(mprime,j)]`
---
### Author:  [@etienne\_dg](https://discourse.julialang.org/u/etienne_dg)
#### Post date: [June 18, 2021, 8:50am UTC](https://discourse.julialang.org/t/help-speedup-a-brute-force-solution/62894/14 "2021-06-18T08:50:36Z")
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!=[3]`, 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[1]) )`
**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).