Pamiętaj, że zestaw jest nieuporządkowany bez duplikatów.

Definicja N -uniquely dodatkowy zestaw S , którego długość jest K jest ustawione tak, że wszystkie N podzbiorów -długość w S sumy różnych numerów. Innymi słowy, sumy wszystkich podzbiorów N długości S są różne.

Cel Biorąc pod uwagę tablicę / zestaw jako dane wejściowe i liczbę Ndla funkcji lub pełnego programu w dowolnym rozsądnym formacie, znajdź i zwróć lub wyślij prawdziwą lub falsey wartość (błąd dla falsey jest w porządku) oznaczający, czy wejście jest N - wyjątkowo addytywny.

Możesz założyć, że każdy element pojawia się najwyżej raz i że każda liczba mieści się w rodzimym typie danych twojego języka. W razie potrzeby można również założyć, że dane wejściowe są posortowane. Na koniec możesz to założyć 0 < N <= K.

Przykłady

Rozważmy zestaw S = {1, 2, 3, 5}i N = 2. Oto wszystkie sumy wszystkich unikalnych par S(dla unikalnych są jedyne interesujące dla sum):

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

Widzimy, że w danych wyjściowych nie ma duplikatów, więc S jest 2-unikatowo addytywny.

Rozważmy teraz zestaw T = {12, 17, 44, 80, 82, 90}i N = 4. Oto wszystkie możliwe sumy długości czterech:

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

Wszystkie są wyjątkowe, a zatem T jest 4-wyjątkowo addytywny.

Przypadki testowe

[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 bajtów

XN!sSdA

Wypróbuj online!

Zwraca true(wyświetlane jako 1) lub false(wyświetlane jako 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)

Galaretka, 7 bajtów

œcS€ṢIP

Wypróbuj online!

Zwraca liczbę dodatnią dla prawdy i zero dla 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 bajtów

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

Ta funkcja zwraca wartość prawdy (w rzeczywistości n) dla prawdy i zwraca błąd jako odpowiedź falsey (poprawna zgodnie z tym komentarzem )

Wyjaśnienie:

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 bajtów

{IsM.cFQ

Zestaw testowy.

       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 bajtów

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

Przykład użycia: 6 # [3,4,7,9,12,16,18]-> True.

Bezpośrednia implementacja definicji: zrób listę sum wszystkich podsekwencji o długości n i sprawdź, czy jest ona równa z usuniętymi duplikatami.

JavaScript (ES6), 132 bajty

(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

Tworzy listy dodatków od 1 do n, a następnie sprawdza ostatnią z nich pod kątem wyjątkowości.

Brachylog , 20 bajtów

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

Oczekuje, że lista zawiera listę, a następnie liczbę całkowitą jako dane wejściowe, a nie dane wyjściowe, np run_from_atom(':{[L:I]hs.lI}f:+aLdL', [[1:2:3:5]:2]). .

Wyjaśnienie

• Główny predykat

             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
  

• Predykat 1: Znajdź wszystkie uporządkowane podzbiory o stałej długości listy

  [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 bajtów

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

Wypróbuj online!

Jak to działa

To (ponownie) definiuje operator binarny \ dla argumentów Array / Int.

combinations(x,n)zwraca wszystkie tablice dokładnie n różnych elementów x . Mamy map sumponad te tablice i zapisać wynik w t .

t∪twykonuje zestaw unii tablicy t ze sobą, co działa jak dłużejunique w tym przypadku .

Na koniec porównujemy t z deduplikowanym t , zwracając truewtedy i tylko wtedy, gdy wszystkie sumy są różne.

Python, 89 bajtów

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

Przetestuj na Ideone .

Jak to działa

c(s,n)wyświetla wszystkie n- kombinacje s , tj. wszystkie listy n różnych elementów s . Mapujemy sumpowstałe listy, obliczając w ten sposób wszystkie możliwe sumy podlist o długości n .

Po totemach c(...,2)tworzymy wszystkie pary sum wynikowych. Jeśli jakieś dwie sumy x i y są równe, x^ypowróci 0 i allzwróci fałsz . I odwrotnie, jeśli wszystkie kwoty są unikalne, x^yzawsze będą zgodne z prawdą i anyzwrócą wartość True .

J, 34 bajty

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

Proste podejście wymaga tylko statsdodatku do combfunkcji. Zwraca 0za false i 1za true.

Alternatywą dla użycia combwbudowanego jest rozwiązanie 38-bajtowe , które generuje zestaw mocy i wybiera podzbiory o rozmiarze n .

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

Stosowanie

   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

Rubinowy , 50 bajtów

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

Wypróbuj online!

Jeśli wszystkie elementy są unikalne, uniq!zwraca nil. Negowanie tego wyniku, podobnie jak w, !(...).uniq!stanowi niezły test wyjątkowości.

To pytanie zostało opublikowane na kilka tygodni przed Ruby 2.4.0-Preview1, które wprowadziło Enumerable#sum, co pozwoliłoby zaoszczędzić tutaj 9 bajtów.

41 bajtów (Ruby 2.4+)

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

Wypróbuj online!

R , 41 bajtów

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

Sumuje wszystkie podzbiory s długości n i sprawdza, czy wszystkie wartości w tabeli awaryjnej tych sum wynoszą 1 (wszystkie sumy są unikalne).

Wypróbuj online!