Partition -Based on a Number X Find the set of N distinct elements that the sum equals the number X

[luthius]

Hey guys
I have the following problem involving partitions.
I have the number X as input.
I would like to find the set of N integer of distinct elements that the sum equal the number X (my input).

Example:
X=15
N=5
Sets of N distinct elements: {5;4;3;2;1} because if we sum each element it results in X
From all the possibilities (with and without repetitions), the algorithm will extract only those formed by distinct numbers.

[AlexisW]

There is something missing: in your example for X=15, I can also answer N=1, for the set {15} because if we sum the single element we obtain X (and similarly there is an N=2 for {14;1} etc). So I guess you're looking for the highest N satisfying this?

One brute-force approach is to take every possible value of N smaller than X, compute all combinations of length N, and see if any of them has the right sum. If so, we can simply keep the highest:

X <- 15

N_match <- logical(X-1)

for(N in 1:(X-1)){
  N_match[[N]] <- any(colSums(combn(X,N)) == X)
}

max(which(N_match))
#> [1] 5

^{Created on 2021-12-18 by the reprex package (v2.0.1)}

There are probably more clever ways, this one will rapidly become impractical when X is bigger.

[luthius]

Thanks for your feedback but my intentios is to indentify the set or sub set of numbers based in my inputs.
I don't need to find the highest N, I will just specify the size of my sub set by using N as input.
I thought to find a way to use the following:

library(gtools)
combinations(X,N,repeats=FALSE)

[nirgrahamuk]

I would attempt to adapt from

Generating all distinct partitions of a number

[AlexisW]

Otherwise, the {partitions} package can be useful.

[luthius]

Looks like it can help me. But I'm a novice in R Language. Can you please advice me?

[AlexisW]

I see 3 approaches:

1. List all combinations of length N with utils::combn() or gtools::combinations(), and only keep the one(s) that sum to X. That can be done changing a bit my code above.
2. List all partitions using partitions::parts(), and only keep the one(s) with no repetition.
3. The above solutions are inefficient in that they compute more than needed. For big X, that's a lot of partitions/combinations that you're not interested in. You can instead rewrite an algorithm yourself taking inspiration from nirgrahamuk's link, so that you stop computations as soon as you find a satisfying partition, thus saving a lot of computations.

So, for 1:

X <- 15
N <- 5

# find all combinations
all_combns <- combn(X,N,simplify = FALSE)

# compute sums
all_sums <- sapply(all_combns, sum)

# is it a partition?
is_partition <- all_sums == X

# extract the satisfying partition(s)
all_combns[is_partition]

And for 2:

# find all partitions that have the right number of elements
all_partitions <- partitions::restrictedparts(X,N,
                                              include.zero = FALSE)

# find partitions with no duplicate
nb_duplicates <- apply(all_partitions, 2, anyDuplicated)
has_no_duplicate <- nb_duplicates == 0

# extract values
all_partitions[,has_no_duplicate]

The first code gives all these partitions as a list, the second one as a matrix with one column per partition, for example for X=15, N=4:

> all_combns[is_partition]
[[1]]
[1] 1 2 3 9

[[2]]
[1] 1 2 4 8

[[3]]
[1] 1 2 5 7

[[4]]
[1] 1 3 4 7

[[5]]
[1] 1 3 5 6

[[6]]
[1] 2 3 4 6

> all_partitions[,has_no_duplicate]
     [,1] [,2] [,3] [,4] [,5] [,6]
[1,]    9    8    7    7    6    6
[2,]    3    4    5    4    5    4
[3,]    2    2    2    3    3    3
[4,]    1    1    1    1    1    2

[luthius]

@AlexisW

# find all partitions that have the right number of elements
all_partitions <- partitions::restrictedparts(X,N,
                                              include.zero = FALSE)

# find partitions with no duplicate
nb_duplicates <- apply(all_partitions, 2, anyDuplicated)
has_no_duplicate <- nb_duplicates == 0

# extract values
all_partitions[,has_no_duplicate]

It is marvelous. It works perfectly. Thank you very much for your time and your knowledge sharing.
Thank you all guys, I hope to have a good knowledge in R language so I can help others as well.