Denken Sie daran, dass ein Satz ohne Duplikate ungeordnet ist.

Definition Eine N- eindeutig additive Menge S, deren Länge K ist, ist eine Menge, so dass alle N- Längen-Teilmengen in S zu unterschiedlichen Zahlen summieren. Mit anderen Worten, die Summen aller N- Längen-Teilmengen von S sind alle verschieden.

Ziel Wenn ein Array / Set als Eingabe und eine Zahl Nfür eine Funktion oder ein vollständiges Programm in einem vernünftigen Format angegeben ist, können Sie einen Wahrheits- oder False-Wert finden und zurückgeben oder ausgeben (Fehler für False ist in Ordnung), der angibt, ob die Eingabe N - ist oder nicht. einzigartig additiv.

Sie können davon ausgehen, dass jedes Element höchstens einmal angezeigt wird und dass sich jede Zahl im nativen Datentyp Ihrer Sprache befindet. Bei Bedarf können Sie auch davon ausgehen, dass die Eingabe sortiert ist. Zuletzt können Sie das annehmen 0 < N <= K.

Beispiele

Betrachten wir die Menge S = {1, 2, 3, 5}und N = 2. Hier sind alle Summen aller eindeutigen Paare S(für die eindeutigen sind die einzigen, die für Summen von Interesse sind):

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

Wir können sehen, dass es keine Duplikate in der Ausgabe gibt, also ist S 2-eindeutig additiv.

Betrachten wir nun die Menge T = {12, 17, 44, 80, 82, 90}und N = 4. Hier sind alle möglichen Summen der Länge vier:

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

Sie sind alle einzigartig, und so ist T 4-einzigartig additiv.

Testfälle

[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 Bytes

XN!sSdA

Probieren Sie es online aus!

Rückgabe true(angezeigt als 1) oder false(angezeigt als 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)

Gelee, 7 Bytes

œcS€ṢIP

Probieren Sie es online aus!

Gibt eine positive Zahl für wahr und null für falsch zurück.

œ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 Bytes

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

Diese Funktion gibt (tatsächlich n) einen positiven Wert für true zurück und gibt einen Fehler als falsche Antwort zurück (gültig gemäß diesem Kommentar ).

Erläuterung:

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 Bytes

{IsM.cFQ

Testsuite.

       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 Bytes

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

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

Direkte Implementierung der Definition: Erstellen Sie eine Liste der Summen aller Teilsequenzen der Länge n und prüfen Sie, ob sie sich mit entfernten Duplikaten gleichsetzen.

JavaScript (ES6), 132 Byte

(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

Baut die additiven Listen von 1 bis n auf und überprüft dann die letzte auf Eindeutigkeit.

Brachylog , 20 Bytes

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

Erwartet eine Liste, die die Liste und dann die Ganzzahl als Eingabe und keine Ausgabe enthält, z run_from_atom(':{[L:I]hs.lI}f:+aLdL', [[1:2:3:5]:2])..

Erläuterung

• Hauptprädikat

             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ädikat 1: Finden Sie alle geordneten Teilmengen mit fester Länge einer 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 Bytes

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

Probieren Sie es online aus!

Wie es funktioniert

Dies definiert den Binäroperator \für Array / Int-Argumente (neu) .

combinations(x,n)Gibt alle Arrays von genau n verschiedenen Elementen von x zurück . Wir ordnen sumdiese Arrays zu und speichern das Ergebnis in t .

t∪tführt die gesetzte Vereinigung des Arrays t mit sich selbst durch, was uniquein diesem Fall wie die längere funktioniert .

Schließlich haben wir vergleichen t mit der deduplizierten t , Rückkehr , truewenn und nur wenn alle Summen unterschiedlich sind.

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

Testen Sie es auf Ideone .

Wie es funktioniert

c(s,n)listet alle n- Kombinationen von s auf , dh alle Listen von n verschiedenen Elementen von s . Wir ordnen sumdie resultierenden Listen zu und berechnen so alle möglichen Summen von Unterlisten der Länge n .

Nach den Stationen c(...,2)erstellen wir alle Paare der resultierenden Summen. Wenn zwei Summen x und y gleich sind, x^ykehrt 0 und allkehrt Falsch . Umgekehrt, wenn alle Summen einzigartig sind, x^ywird es immer sein truthy, und anywird wieder wahr .

J, 34 Bytes

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

Für den einfachen Ansatz ist nur das statsAdd-On für die combFunktion erforderlich . Gibt 0für false und 1für true zurück.

Als Alternative zur Verwendung des integrierten combGeräts gibt es eine 38-Byte- Lösung, die den Leistungssatz generiert und die Teilmengen der Größe n auswählt .

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

Verwendungszweck

   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

Ruby , 50 Bytes

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

Probieren Sie es online aus!

Wenn alle Elemente eindeutig sind, wird uniq!zurückgegeben nil. Das Negieren dieses Ergebnisses wie in ergibt !(...).uniq!einen schönen Einzigartigkeitstest.

Diese Frage wurde einige Wochen vor der Einführung von Ruby 2.4.0-Preview1 gestellt, wodurch Enumerable#sumhier 9 Bytes eingespart würden.

41 Bytes (Ruby 2.4+)

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

Probieren Sie es online aus!

R 41 Bytes

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

Summiert alle n-Längen-Teilmengen von s und prüft, ob alle Werte in einer Kontingenztabelle dieser Summen 1 sind (alle Summen sind eindeutig).

Probieren Sie es online aus!