Calculating all possible combinations

General Usage Performance
1

Hello.
I’m having trouble finding an efficient way to calculate all possible combinations from a set of vectors.
When they are small using kron[a,b,c] where a,b and c are vectors yields good results but the problem occurs when the vectors get big or there are simply more of them resulting in overflow.

Simple example for the problem is calculating all possible multiplications of primes lower than 6 up to 100.
Another example: all possible multiples from set of vectors [1,2,3] , [5,2,7] , [2,4,8,16]

Those problems are easy to brute force but when you scale them up it proved to be sort of a problem to me. so I’m open for suggestion about useful algorithms. And thanks :smiley:

1 Like
2

Maybe the package Combinatorics.jl has what you need.

Particularly, the function combinations produces an iterator on the original collection of elements that you want to combine, so that you don’t need a large copy of all the possible combinations.

1 Like
3

I tried it, It returns the number of combinations and not the actual result or indices.
Though maybe I just couldn’t use it properly, I’m new to Julia.

4

No, it returns an iterator over the possible combinations:

julia> using Combinatorics

julia> x = [[1,2,3], [4,5,6], [7,8,9]]
3-element Array{Array{Int64,1},1}:
 [1, 2, 3]
 [4, 5, 6]
 [7, 8, 9]

julia> combinations_x = combinations(x);

julia> for c in combinations_x
       println(c)
       end
Array{Int64,1}[[1, 2, 3]]
Array{Int64,1}[[4, 5, 6]]
Array{Int64,1}[[7, 8, 9]]
Array{Int64,1}[[1, 2, 3], [4, 5, 6]]
Array{Int64,1}[[1, 2, 3], [7, 8, 9]]
Array{Int64,1}[[4, 5, 6], [7, 8, 9]]
Array{Int64,1}[[1, 2, 3], [4, 5, 6], [7, 8, 9]]

(Or use combinations(x, 2) if you only want the pairs, etc.)

4 Likes
5

Thanks, I really almost pulled some hairs from my head.

6

There is also the built-in function Iterators.product:

help?> Iterators.product
  product(iters...)

  Return an iterator over the product of several iterators. Each generated element is a tuple whose ith element comes from the ith argument iterator. The first iterator changes the fastest.

  Examples
  ≡≡≡≡≡≡≡≡≡≡

  julia> collect(Iterators.product(1:2, 3:5))
  2×3 Array{Tuple{Int64,Int64},2}:
   (1, 3)  (1, 4)  (1, 5)
   (2, 3)  (2, 4)  (2, 5)

julia>
10 Likes
7

Mind helping me a bit with the syntax?
I wrote a code and I’m trying to generalize it for future uses but the syntax keeps fighting me.
my problem is with this line (val is an array of arrays, so val[i] is an array):
check2 = collect(Iterators.product(val[1],val[2],val[3]))
That line works but it’s too specific to be generalized. What I mean is that I got an array of arrays of different sizes and I want to write something like that:
check2 = collect(Iterators.product(val))

1 Like
8

You want to splat: Iterators.product(val...)

6 Likes
9

Damn, never thought it will be that simple. Thanks man! :ok_hand:

1 Like