N'oubliez pas qu'un ensemble n'est pas ordonné sans doublons.

Définition Un ensemble N à additif unique S dont la longueur est K est un ensemble tel que tous les sous-ensembles de longueur N dans S totalisent des nombres différents. En d'autres termes, les sommes de tous les sous-ensembles de longueur N de S sont toutes distinctes.

Objectif Étant donné un tableau / ensemble en entrée et un numéro Npour une fonction ou un programme complet dans n'importe quel format raisonnable, rechercher et renvoyer ou sortir une valeur véridique ou falsey (l'erreur pour falsey est correcte) indiquant si l'entrée est N ou non - additif unique.

Vous pouvez supposer que chaque élément n'apparaît qu'une seule fois et que chaque numéro se trouve dans le type de données natif de votre langue. Si nécessaire, vous pouvez également supposer que l'entrée est triée. Enfin, vous pouvez supposer cela 0 < N <= K.

Exemples

Considérons l'ensemble S = {1, 2, 3, 5}et N = 2. Voici toutes les sommes de toutes les paires uniques S(car les seules sont les seules intéressantes pour les sommes):

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

Nous pouvons voir qu'il n'y a pas de doublons en sortie, donc S est 2-uniquement additif.

Considérons maintenant l'ensemble T = {12, 17, 44, 80, 82, 90}et N = 4. Voici toutes les sommes possibles de longueur quatre:

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

Ils sont tous uniques, et T est donc un additif 4-unique.

Cas de test

[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

MATL , 7 octets

XN!sSdA

Essayez-le en ligne!

Renvoie true(affiché comme 1) ou false(affiché comme 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)

Gelée, 7 octets

œcS€ṢIP

Essayez-le en ligne!

Renvoie un nombre positif pour true et zéro pour 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

Matlab, 78 octets

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

Cette fonction renvoie une valeur positive (en fait n) pour véridique et renvoie une erreur en tant que réponse falsey (valide selon ce commentaire )

Explication:

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

Pyth, 8 octets

{IsM.cFQ

Suite de tests.

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

Haskell, 69 octets

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

Exemple d'utilisation: 6 # [3,4,7,9,12,16,18]-> True.

Implémentation directe de la définition: faites une liste des sommes de toutes les sous-séquences de longueur n et vérifiez si elle est égale aux doublons supprimés.

JavaScript (ES6), 132 octets

(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

Construit les listes d'additifs de 1 à n, puis vérifie l'unicité de la dernière.

Brachylog , 20 octets

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

Attend une liste contenant la liste, puis l'entier comme entrée et aucune sortie, par exemple run_from_atom(':{[L:I]hs.lI}f:+aLdL', [[1:2:3:5]:2]). .

Explication

• Prédicat principal

             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
  

• Prédicat 1: rechercher tous les sous-ensembles ordonnés de longueur fixe d'une liste

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

Julia, 46 41 octets

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

Essayez-le en ligne!

Comment ça fonctionne

Ceci (re) définit l'opérateur binaire \pour les arguments Array / Int.

combinations(x,n)renvoie tous les tableaux d'exactement n éléments différents de x . Nous cartographions sumces tableaux et stockons le résultat dans t .

t∪teffectue l'union d'ensemble du tableau t avec lui-même, ce qui fonctionne comme le plus long uniquedans ce cas.

Enfin, nous comparons t avec le t dédupliqué , en retournant truesi et seulement si toutes les sommes sont différentes.

Python, 89 octets

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

Testez-le sur Ideone .

Comment ça fonctionne

c(s,n)liste toutes les n -combinaisons de s , c'est-à-dire toutes les listes de n éléments différents de s . Nous cartographions sumles listes résultantes, calculant ainsi toutes les sommes possibles de sous-listes de longueur n .

Après les quartiers, nous utilisons c(...,2)pour créer toutes les paires des sommes résultantes. Si deux sommes x et y sont égales, x^yrenvoie 0 et allrenvoie False . Inversement, si toutes les sommes sont uniques, elles x^yseront toujours véridiques et anyreviendront Vrai .

J, 34 octets

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

Approche simple, ne nécessite que le statsmodule complémentaire pour la combfonction. Renvoie 0pour faux et 1pour vrai.

Comme alternative à l'utilisation de la fonction combintégrée, il existe une solution de 38 octets qui génère l'ensemble d'alimentation et choisit les sous-ensembles de taille 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

Rubis , 50 octets

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

Essayez-le en ligne!

Si tous les éléments sont uniques, uniq!retourne nil. Nier ce résultat, comme dans!(...).uniq! fait un bon test d'unicité.

Cette question a été publiée quelques semaines avant Ruby 2.4.0-preview1, qui a introduitEnumerable#sum , ce qui permettrait d'économiser 9 octets ici.

41 octets (Ruby 2.4+)

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

Essayez-le en ligne!

R , 41 octets

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

Additionne tous les sous-ensembles de n longueurs de s et vérifie si toutes les valeurs dans une table de contingence de ces sommes sont 1 (toutes les sommes sont uniques).

Essayez-le en ligne!