# Minimum difference between cartesian product of 3 elements that add up to a certain number

Let's say I've got a list (or array) of:

l = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]


I want to get the third Cartesian power of the above list, where we take every possible triple of elements from l.

Then I want to filter and only keep the sublists where the sum of that sublist equal to the maximum value of the list.

Then I only want one sublist, which is the sublist where the difference of the three numbers that add up to the maximum value is the smallest.

The algorithm to see the smallest difference could be something like (in Python):

max(v1,v2,v3) - min(v1,v2,v3)


So the expected output for this case would be:

(3, 3, 4)


The order of the elements within the output could be in any order.

## Test cases:

l = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
-> (3, 3, 4)

l = [1, 2, 3, 4, 5]
-> (1, 2, 2)

l = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 44, 45, 46, 47, 48, 49, 50, 51, 52, 53, 54, 55, 56, 57, 58, 59, 60, 61, 62, 63, 64, 65, 66, 67, 68, 69, 70, 71, 72, 73, 74, 75, 76, 77, 78, 79, 80, 81, 82, 83, 84, 85, 86, 87, 88, 89, 90, 91, 92, 93, 94, 95, 96, 97, 98, 99, 100]
-> (33, 33, 34)

l = [1, 4, 5, 2, 3, 9, 8, 7, 10, 6]
-> (3, 3, 4)

l = [1, 4, 8, 12, 13, 16, 20, 24, 27]
-> (1, 13, 13)


This is tagged with , so the shortest code in bytes wins!

There will always be an output, never would be a case where no 3 elements would add up to the maximum value.

• suggest [1, 3, 6, 7, 13] -> (3, 3, 7)
– att
Dec 28, 2021 at 7:02
• So this is some kind of an approximation to "1/3 * max number"? Dec 30, 2021 at 0:33

# Factor + math.combinatorics math.unicode, 83 bytes

[ dup supremum swap 3 selections [ Σ = ] with filter [ minmax - abs ] infimum-by ]


Try it online!

## Explanation

                            ! { 1 2 3 4 5 }
dup                         ! { 1 2 3 4 5 } { 1 2 3 4 5 }
supremum                    ! { 1 2 3 4 5 } 5
swap                        ! 5 { 1 2 3 4 5 }
3 selections                ! 5 { { 1 1 1 } { 1 1 2 } ... }
[ Σ = ] with filter         ! { { 1 1 3 } { 1 2 2 } ... }
[ minmax - abs ] infimum-by ! { 1 2 2 }


# Wolfram Language (Mathematica), 39 55 bytes

l#&@@SortBy[l~Tuples~3,Abs[Max@l-Tr@#]|Max@#-Min@#&]


Try it online!

Slow for larger input lists.

# R, 105 96 bytes

(or 89 bytes in R≥4.1 by using \ for function)

Edit: -9 bytes thanks to pajonk

function(l,a=expand.grid(l,l,l),b=apply(a[rowSums(a)==max(l),],1,sort))b[,order(b[3,]-b[1,])[1]]


Try it online!

• Try expand.grid without rep! Dec 28, 2021 at 11:46
• @pajonk - I saw it in your answer, and was just editing it in, but it seemed sneaky... Dec 28, 2021 at 11:47
• @DominicvanEssen Wow! First R answer here! Thanks. Dec 28, 2021 at 11:50
• I've deleted my longer straightforward boring answer after seeing yours. Dec 28, 2021 at 11:50
• @U12-Forward - I'll edit to mention it. Generally, though, I don't use it where it doesn't achieve better than the trivial 7-byte saving (especially because it's convenient to be able to directly compare answers on 'Try it online', which doesn't support R version 4.1). Dec 28, 2021 at 12:01

# Vyxal, 18 bytes

3ÞẊ'∑?G=;µ÷Ȯε^ε+;h


Try it Online!

# Vyxal, 16 bytes

3ÞẊ'∑?G=;µ₌Gg-;h


Try it Online!

-2 thanks to Bubbler's insight.

3ÞẊ              # Combinations of input of length 3
'    ;        # Filter by...
∑  =         # Sum equals
?G          # Maximum of input
µ    ;h # Minimum by...
₌Gg-   # Difference of min + max


# Python 3.8, 1301159985 80 bytes:

-14 Thanks to @tsh
-5 Thanks again to @tsh

lambda l:max([((z:=max(l)-x-y)in l,x<=y<=z,x-z,x,y,z)for x in l for y in l])[3:]


Try it Online!

Get's the Cartesian Product by looping the list 3 times, and summing it up.

• 85: lambda l:min([(x>y,y>z,x+y+z!=max(l),z-x,x,y,z)for x in l for y in l for z in l])[4:]
– tsh
Dec 28, 2021 at 5:37
• @tsh Woo, why didn't I think of that! Edited my answer. Dec 28, 2021 at 5:39
• 80: lambda l:max([((z:=max(l)-x-y)in l,x<=y<=z,x-z,x,y,z)for x in l for y in l])[3:]
– tsh
Dec 28, 2021 at 5:43
• @tsh Edited, wow!! Dec 28, 2021 at 5:46

# Jelly (fork), 11 bytes

ṗ3SƘṀṀ_ṂƊÞḢ


Try it online! (this is the equivalent in normal Jelly)

This uses my fork of Jelly which includes the Ƙ (keep-like) quick to replace the commonly used <link>⁼¥Ƈ pattern. You can see this in the TIO link.

## How it works

ṗ3SƘṀṀ_ṂƊÞḢ - Main link. Takes a list L on the left
ṗ3          - Cartesian Cube
Ṁ       - Maximum of L
Ƙ        - Keep triples whose     is like the maximum
S         -                    sum
ƊÞ  - Sort the remaining triples by:
Ṁ      -   maximum
_     -   minus
Ṃ    -   minimum
Ḣ - Take the first


# Husk, 14 13 bytes

-1 byte thanks to Dominic van Essen

◄§-▼▲fo=▲¹Σπ3


Try it online!

### Explanation

◄§-▼▲fo=▲¹Σπ3
π3     cartesian product of 3 * input
fo          filter by composed function
=▲¹Σ      max of input equals sum
◄§               min by composed binary function
-▼▲            max - min

• -1 byte by changing ΠR3 (cartesian product of 3 copies of input) to π3 (cartesian power of 3 of input) Dec 28, 2021 at 13:53
• Unfortunately, Jonathan's trick fails for [1,2,5,7,11] Dec 30, 2021 at 13:35
• thanks, reverted Dec 30, 2021 at 21:28

# APL+WIN, 53 bytes

Prompts for list

↑((⌊/m)=m←(⌈/¨l)-⌊/¨l)/l←((⌈/i)=+/¨l)/l←,i∘.,,i∘.,i←⎕


Try it online! Thanks to Dyalog Classic

# Python/NumPy, 77 bytes

lambda l:min(l[argwhere(sum(ix_(l,l,l))==max(l))],key=ptp)
from numpy import*

Attempt This Online!

Takes and returns numpy arrays. Approach is straightforward. ix_(l,l,l) is essentially the cartesian product. This is then summed over coordinates and compared to the maximum. argwhere extracts the coordinates where the comparison succeeds and these are used to index back into l. It remains to select a triplet that minimises the spread (difference between min and max). Rather conveniently, numpy has a function for the spread: ptp

# Ruby, 73 72 68 61 bytes

->l{l.product(l,l).min_by{|x|[(l.max-x.sum)**2,x.max-x.min]}}


Try it online!

# MATL, 28 25 bytes

3Z^!tsGX>=Z)ttX<-X>&S1)Z)


Try it online!

3Z^     % Third Cartesian power

!ts     % Sum of each sublist

GX> =   % See which ones' sums equal input's maximum

Z)      % Filter to keep only those

ttX<-   % Subtract from each sublist its Minimum

X>      % Maximum of each. Effectively this is (Max - Min)

&S      % Get the indices that would sort this result

1)      % Get the first index of those i.e. the argmin

Z)      % Extract the sublist at that index


(Equivalently, perhaps slightly more clearly, 3Z^!tsGX>=Z)tX>yX<-&S1)Z) - instead of "effectively" doing max - min, just explicitly does max - min.)

# Charcoal, 38 bytes

ＦθＦθＦθ⊞υ⟦ικλ⟧≔Φυ⁼Σι⌈θυ≔Ｅυ⁻⌈ι⌊ιθＩ§υ⌕θ⌊θ


Try it online! Link is to verbose version of code. Explanation:

ＦθＦθＦθ⊞υ⟦ικλ⟧


Create the Cartesian product of three copies of the list.

≔Φυ⁼Σι⌈θυ


Extract those triples that sum to the maximum of the original list.

≔Ｅυ⁻⌈ι⌊ιθ


For each triple, find the difference between its largest and smallest entries.

Ｉ§υ⌕θ⌊θ


Output the first triple with the smallest difference.

sub{$"=',';my$m;($d=max(@$_)-min@$_)<($m//9e9)and($m,@r)=($d,@$_)for grep max(@_)==sum(@$_),map[split$"],glob"{@_},{@_},{@_}";sort{$a-$b}@r}  Try it online! # Scala, 85 bytes a=>(for{x<-a;y<-a;z<-a if x+y+z==a.max}yield Seq(x,y,z)).minBy(l=>l.max-l.min).sorted  Try it online! # Haskell, 97 bytes import Data.List f x=head$sortOn(\t->m t-minimum t)$filter((==m x).sum)$sequence[x,x,x]
m=maximum


Try it online!

• 92 bytes Dec 29, 2021 at 13:21
• 74 bytes Dec 29, 2021 at 13:27
• a Wizard you are indeed. I knew my solution was clunky, I didn't know it was that clunky Dec 29, 2021 at 13:51
• The main issue is just the import really. If you weren't burdened by it all 3 versions would be roughly comparable. Dec 29, 2021 at 13:58

# C++ (gcc), 280 $$\\cdots\$$ 211 210 bytes

#import<regex>
#define S(v)std::sort(&v[0],&*end(v))
using V=std::vector<int>;int f(V&v){V r=v,x;S(v);int m=v.back(),n=m,t;for(int a:r)for(int b:r)for(int c:r)x={a,b,c},S(x),t=x[2]-x[0],v=t<m&a+b+c==n?m=t,x:v;}


Try it online!

Saved 3 4 bytes thanks to ceilingcat!!!

Inputs a vector of integers.
Replaces the input vector with the cartesian product of 3 elements of the input vector that add up to the maximum of the input vector and that have the minimum difference between the smallest and the largest element from all of the cartesian products.

• See att's comment on Jonathan's (now deleted) answer: [1,2,5,7,11] should output [1,5,5] (difference 4), not [2,7,7] (difference 5). Dec 29, 2021 at 15:27
• @DominicvanEssen Reverted back to my original solution - thanks! :D Dec 29, 2021 at 18:04