Search code examples
algorithmmathcombinationscombinatoricspartition

How to find all partitions of k positive numbers that sum to n with all permutations


For k=4 and n=6, we have

1 + 1 + 1 + 3 = 6
1 + 1 + 2 + 2 = 6

which can be obtained from the Triangle of partition numbers.

But for 1 + 1 + 1 + 3 we can have 3 more permutations (4 in total) as follows:

1 + 1 + 1 + 3
1 + 1 + 3 + 1
1 + 3 + 1 + 1
3 + 1 + 1 + 1

and for 1 + 1 + 2 + 2 we can also have 5 more permutations (6 in total) as follows:

1 + 1 + 2 + 2
1 + 2 + 1 + 2
1 + 2 + 2 + 1
2 + 1 + 2 + 1
2 + 1 + 1 + 2
2 + 2 + 1 + 1

which I think in general, binomial(n, n - k) for every possible partition.

How to find all these partitions in Python or in Julia?

In Julia, my attempt is the following, which is I think correct but not optimal since I am generating all permutations and then applying unique to remove the duplicate ones.

using Combinatorics
n, k = 6, 4
comb = []
for partition in partitions(n, k)
    permuted_partition = permutations(partition)
    unique_permuted_partition = unique(permuted_partition)
    append!(comb, unique_permuted_partition)
end

Solution

  • In Julia, the following answers the question but I think it is not optimal since I am generating all permutations and then applying unique to remove the duplicate ones.

    using Combinatorics
    n, k = 6, 4
    comb = []
    for partition in partitions(n, k)
        permuted_partition = permutations(partition)
        unique_permuted_partition = unique(permuted_partition)
        append!(comb, unique_permuted_partition)
    end