10
\$\begingroup\$

Remember that a set is unordered without duplicates.

Definition An N-uniquely additive set S whose length is K is a set such that all N-length subsets in S sum to different numbers. In other words, the sums of all the N-length subsets of S are all distinct.

Objective Given an array/set as input and a number N to a function or to a full program in any reasonable format, find and return or output a truthy or falsey value (erroring for falsey is okay) denoting whether or not the input is N-uniquely additive.

You may assume that each element only appears at most once and that each number is within your language's native datatype. If need be, you may also assume that the input is sorted. Last, you may assume that 0 < N <= K.

Examples

Let's consider the set S = {1, 2, 3, 5} and N = 2. Here are all the sums of all unique pairs over S (for the unique ones are the only ones of interest for sums):

1 + 2 = 3
1 + 3 = 4
1 + 5 = 6
2 + 3 = 5
2 + 5 = 7
3 + 5 = 8

We can see that there are no duplicates in output, so S is 2-uniquely additive.


Let's now consider the set T = {12, 17, 44, 80, 82, 90} and N = 4. Here are all the possible sums of length four:

12 + 17 + 44 + 80 = 153
12 + 17 + 44 + 82 = 155
12 + 17 + 44 + 90 = 163
12 + 17 + 80 + 82 = 191
12 + 17 + 80 + 90 = 199
12 + 17 + 82 + 90 = 201
12 + 44 + 80 + 82 = 218
12 + 44 + 80 + 90 = 226
12 + 44 + 82 + 90 = 228
12 + 80 + 82 + 90 = 264
17 + 44 + 80 + 82 = 223
17 + 44 + 80 + 90 = 231
17 + 44 + 82 + 90 = 233
17 + 80 + 82 + 90 = 269
44 + 80 + 82 + 90 = 296

They are all unique, and so T is 4-uniquely additive.

Test Cases

[members], N => output
[1, 4, 8], 1 => true
[1, 10, 42], 1 => true                ; all sets trivially satisfy N = 1
[1, 2, 3, 4], 3 => true
[1, 2, 3, 4, 5], 5 => true
[1, 2, 3, 5, 8], 3 => true
[1, 2, 3, 4, 5], 2 => false           ;  1 +  4       =  5 =        2 + 3
[-2, -1, 0, 1, 2], 3 => false         ; -2 + -1 + 2   = -1 =   -2 + 0 + 1
[1, 2, 3, 5, 8, 13], 3 => false       ;  1 +  2 + 13  = 16 =    3 + 5 + 8
[1, 2, 4, 8, 16, 32], 3 => true
[1, 2, 4, 8, 16, 32], 4 => true
[1, 2, 4, 8, 16, 32], 5 => true
[1, 2, 4, 8, 16, 32], 6 => true
[3, 4, 7, 9, 12, 16, 18], 6 => true
[3, 4, 7, 9, 12, 16, 18], 3 => false  ; 3 + 4 + 12 = 19 = 3 + 7 + 9
\$\endgroup\$
  • \$\begingroup\$ You mean N <= K? \$\endgroup\$ – Neil Jun 3 '16 at 22:34
  • \$\begingroup\$ @Neil Yes, I do. Sorry! \$\endgroup\$ – Conor O'Brien Jun 3 '16 at 22:35
  • \$\begingroup\$ Does an error count as something falsey? \$\endgroup\$ – flawr Jun 3 '16 at 22:49
  • \$\begingroup\$ @flawr Sure, I'll accept that \$\endgroup\$ – Conor O'Brien Jun 3 '16 at 22:50

12 Answers 12

3
\$\begingroup\$

MATL, 7 bytes

XN!sSdA

Try it online!

Returns true (displayed as 1) or false (displayed as 0).

XN   % Take array S and number N. Generate all combinations of elements from S 
     % taken N at a time. Gives a 2D array where each combination is a row
!    % Transpose. Each combination is now a column
s    % Sum of each column: gives a row array. If N=1 computes the sum of
     % the only row, and so gives a number
S    % Sort vector
d    % Array of consecutive differences. For a single number gives an empty array
A    % True if all elements of the input array are nonzero (for an empty array
     % it also gives true)
\$\endgroup\$
4
\$\begingroup\$

Jelly, 7 bytes

œcS€ṢIP

Try it online!

Returns a positive number for truthy and zero for falsey.

œc       find combinations
  S€     sum each combination
    Ṣ    sort the sums
     I   find the difference between each pair of sums 
           iff any sums are the same, this returns a list containing 0
      P  product of the elements of the resulting list
\$\endgroup\$
3
\$\begingroup\$

Matlab, 78 bytes

function n=f(s,n);p=perms(s);k=sum(unique(sort(p(:,1:n)),'rows')');unique(k)-k

This function returns a positive value (in fact n) for truthy and returns an error as a falsey answer (valid according to this comment)

Explanation:

function n=f(s,n);
p=perms(s); %create all permutations of the set

k=sum(unique(sort(p(:,1:n)),'rows')');
                  %just take the first n entries of each permutation
             %sort those entries and
      %filter out all duplicates (we sorted as the order should NOT matter)
  %then sum each of those candidates

unique(k)-k
%if all those sums are distinct, unique(k) will have the same size 
% as k itself, and therefore we can subtract, otherwise it will throw 
% an error as we try to subtract vectors of different sizes
\$\endgroup\$
  • \$\begingroup\$ Why does it error? \$\endgroup\$ – Conor O'Brien Jun 3 '16 at 22:57
  • 1
    \$\begingroup\$ I just added an explanation. The error comes from the last line. It causes an error if we have duplicates in k. PS: Matlab syntax highlighting finally works!!! \$\endgroup\$ – flawr Jun 3 '16 at 23:02
  • \$\begingroup\$ Good idea to return the same n! \$\endgroup\$ – Luis Mendo Jun 3 '16 at 23:24
2
\$\begingroup\$

Pyth, 8 bytes

{IsM.cFQ

Test suite.

       Q   eval input (provided as a 2-element array)
    .cF    splat over combination
  sM       sum each combination
{I         is the result invariant under { (dedup/uniq)?
\$\endgroup\$
  • \$\begingroup\$ What does splat mean? \$\endgroup\$ – Conor O'Brien Jun 3 '16 at 22:40
  • \$\begingroup\$ @CᴏɴᴏʀO'Bʀɪᴇɴ Same thing it means in every other language: use an array as the arguments to a function. \$\endgroup\$ – Doorknob Jun 3 '16 at 22:40
  • \$\begingroup\$ Oh, right, I'm dumb :p thanks \$\endgroup\$ – Conor O'Brien Jun 3 '16 at 22:41
  • 2
    \$\begingroup\$ in every other language that actually has this function \$\endgroup\$ – flawr Jun 3 '16 at 23:13
  • 2
    \$\begingroup\$ I fixed the bug that required that Q at the end. \$\endgroup\$ – isaacg Jun 4 '16 at 2:55
2
\$\begingroup\$

Haskell, 69 bytes

import Data.List
n#s=(==)=<<nub$[sum x|x<-subsequences s,length x==n]

Usage example: 6 # [3,4,7,9,12,16,18] -> True.

Direct implementation of the definition: make a list of sums of all subsequences of length n and check if it equals itself with duplicates removed.

\$\endgroup\$
2
\$\begingroup\$

JavaScript (ES6), 132 bytes

(a,n)=>a.map(m=>{for(i=n;i--;)s[i].map(k=>s[i+1].push(m+k))},s=[...Array(n+1)].map(_=>[]),s[0]=[0])&&new Set(s[n]).size==s[n].length

Builds up the additive lists from 1 to n and then checks the last one for uniqueness.

\$\endgroup\$
2
\$\begingroup\$

Brachylog, 20 bytes

:1f:+aLdL
[L:I]hs.lI

Expects a list containing the list and then the integer as Input, and no Output, e.g. run_from_atom(':{[L:I]hs.lI}f:+aLdL', [[1:2:3:5]:2])..

Explanation

  • Main Predicate

               Input = [A:I]
    :1f        Find all ordered subsets of A of length I
       :+aL    Apply summing to each element of that list of subsets. Call that L
           dL  True if L minus all duplicate elements is still L
    
  • Predicate 1: Find all ordered subsets of fixed length of a list

    [L:I]      Input = [L:I]
         hs.   Unify Output with an ordered subset of L
            lI True if I is the length of Output
    
\$\endgroup\$
2
\$\begingroup\$

Julia, 46 41 bytes

x\n=(t=map(sum,combinations(x,n)))==t∪t

Try it online!

How it works

This (re)defines the binary operator \ for Array/Int arguments.

combinations(x,n) returns all arrays of exactly n different elements of x. We map sum over these arrays and store the result in t.

t∪t performs the set union of the array t with itself, which works like the longer unique in this case.

Finally, we compare t with the deduplicated t, returning true if and only if all sums are different.

\$\endgroup\$
2
\$\begingroup\$

Python, 89 bytes

from itertools import*
lambda s,n,c=combinations:all(x^y for x,y in c(map(sum,c(s,n)),2))

Test it on Ideone.

How it works

c(s,n) lists all n-combinations of s, i.e., all lists of n different elements of s. We map sum over the resulting lists, thus computing all possible sums of sublists of length n.

After wards, we use c(...,2) to create all pairs of the resulting sums. If any two sums x and y are equal, x^y will return 0 and all will return False. Conversely, if all sums are unique, x^y will always be truthy, and any will return True.

\$\endgroup\$
1
\$\begingroup\$

J, 34 bytes

load'stats'
[:*/@~:[:+/"1(comb#){]

Straight-forward approach, only requires the stats add-on for the comb function. Returns 0 for false and 1 for true.

As an alternative to using the comb builtin, there is a 38 byte solution that generates the power set and chooses the subsets of size n.

[:*/@~:(>@{[:(</.~+/"1)2#:@i.@^#)+/@#]

Usage

   f =: [:*/@~:[:+/"1(comb#){]
   2 f 1 2 3 5
1
   4 f 12 17 44 80 82 90
1
   3 f _2 _1 0 1 2
0
   6 f 3 4 7 9 12 16 18
1
   3 f 3 4 7 9 12 16 18
0
\$\endgroup\$
  • \$\begingroup\$ Wow, didn't know about the stats module. Very nice! \$\endgroup\$ – Conor O'Brien Jun 4 '16 at 0:50
  • \$\begingroup\$ I just found out about it too, I haven't really delved much into the add-ons in J. If I was more brave, I'd attempt the graphics add-ons. \$\endgroup\$ – miles Jun 4 '16 at 0:59
0
\$\begingroup\$

Ruby, 50 bytes

->s,n{!s.combination(n).map{|c|c.inject :+}.uniq!}

Try it online!

If all elements are unique, uniq! returns nil. Negating that result, as in !(...).uniq! makes for a nice uniqueness test.

This question was posted a few weeks before Ruby 2.4.0-preview1, which introduced Enumerable#sum, which would save 9 bytes here.

41 bytes (Ruby 2.4+)

->s,n{!s.combination(n).map(&:sum).uniq!}

Try it online!

\$\endgroup\$
0
\$\begingroup\$

R, 41 bytes

function(s,n)max(table(combn(s,n,sum)))<2

Sums all n-length subsets of s and checks if all values in a contingency table of these sums are 1 (all sums are unique).

Try it online!

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.