In what format does the "permutations" command in the Combinatorics library compute the permutations?

General Usage
,
1

I’m talking about this command: [Docstrings · Combinatorics.jl], Combinatorics version is 1.0.2, Julia version is 1.7.1

I want to see if the digits in a number (except one digit, called dig) add up to dig. My plan is to create all the permutations of the digits without dig and then add each digit together in each permutation so that is looks something like this (For the number 65231, and dig is 6):

First permutation - 5231, 5+2 is bigger than 6, so it continues to the next permutation
2nd - 2315, 2+3 = 5, 2+3+1 = 6 so it stops the for loop

My question is what format does the permutation command return the permutatations as (I can’t just print it because the command knows permutations get big or something). I’m guessing it’s something like this:

[[5, 2, 3, 1], [2, 3, 1, 5]...]

Thankyou for your time

2

permutations returns an iterator as documented:

julia> using Combinatorics

julia> permutations(digits(1235))
Combinatorics.Permutations{Vector{Int64}}([5, 3, 2, 1], 4)

That’s just how iterators print - they can’t give you all their contents, as that would mean actually accessing the contents of the iterator, which would run counter to the reason for returning an iterator in the first place (namely that you don’t have to access all its elements at once).

You can see what’s in your iterator by collecting it (and you’ll see it’s not that big in this case):

julia> collect(permutations(digits(1235)))
24-element Vector{Vector{Int64}}:
 [5, 3, 2, 1]
 [5, 3, 1, 2]
 [5, 2, 3, 1]
 [5, 2, 1, 3]
 [5, 1, 3, 2]
 [5, 1, 2, 3]
 [3, 5, 2, 1]
 [3, 5, 1, 2]
 [3, 2, 5, 1]
 [3, 2, 1, 5]
 [3, 1, 5, 2]
 [3, 1, 2, 5]
 [2, 5, 3, 1]
 [2, 5, 1, 3]
 [2, 3, 5, 1]
 [2, 3, 1, 5]
 [2, 1, 5, 3]
 [2, 1, 3, 5]
 [1, 5, 3, 2]
 [1, 5, 2, 3]
 [1, 3, 5, 2]
 [1, 3, 2, 5]
 [1, 2, 5, 3]
 [1, 2, 3, 5]

I would also note that generating all permutations here seems a bit wasteful, you might be interested in combinations instead:

julia> collect(combinations(digits(1235)))
15-element Vector{Vector{Int64}}:
 [5]
 [3]
 [2]
 [1]
 [5, 3]
 [5, 2]
 [5, 1]
 [3, 2]
 [3, 1]
 [2, 1]
 [5, 3, 2]
 [5, 3, 1]
 [5, 2, 1]
 [3, 2, 1]
 [5, 3, 2, 1]

then your whole problem reduces to

julia> any(x -> sum(x) == 6, combinations(digits(1235)))
true

Note that this still isn’t the most efficient thing you can do, as some sums are still evaluated multiple times here, and the problem in general has more structure that you might be able to exploit for a more efficient solution.

1 Like
3

I forgot that recursion existed and that’s a much better idea than using permutations