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

Question

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 code-golf, 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.

Answer 1

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 }

Answer 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.

Answer 3

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!

Answer 4

Vyxal, 18 bytes

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

Try it Online!

Answer 5

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

Answer 6

Python 3.8, 130 115 99 85 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.

Answer 7

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

Answer 8

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

Answer 9

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

Answer 10

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

Answer 11

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!

Answer 12

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.)

Answer 13

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.

Answer 14

Perl 5 List::Util, 140 bytes

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!

Answer 15

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!

Answer 16

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!

Answer 17

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.