세트는 중복없이 순서가 정렬되지 않습니다.

정의 N -uniquely 첨가제 세트 S 는 길이 인 K가 세트 등이다 모두 N 의 서브 세트 – 길이 S의 상이한 수에 합. 다시 말해, S 의 모든 N- 길이 부분 집합의 합 은 모두 구별된다.

목적 입력으로 배열 / 설정 및 N함수 나 전체 프로그램에 적절한 형식으로 숫자가 주어지면 입력이 N 인지 여부를 나타내는 진실 또는 거짓 값 (거짓 오류는 괜찮습니다)을 찾아서 반환하거나 출력합니다 – 독창적 인 첨가제.

각 요소는 최대 한 번만 나타나고 각 숫자가 언어의 기본 데이터 유형 내에 있다고 가정 할 수 있습니다. 필요한 경우 입력이 정렬되었다고 가정 할 수도 있습니다. 마지막으로을 가정 할 수 있습니다 0 < N <= K.

예

의이 세트를 생각해 보자 S = {1, 2, 3, 5}하고 N = 2. 다음은 모든 고유 한 쌍의 합계입니다 S(유일한 것이 합에 대한 유일한 것이므로).

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

출력에 중복이 없다는 것을 알 수 있으므로 S 는 2 고유 첨가제입니다.

의 현재 세트를 생각해 보자 T = {12, 17, 44, 80, 82, 90}하고 N = 4. 길이 4의 가능한 모든 합계는 다음과 같습니다.

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

그것들은 모두 독특하기 때문에 T 는 4 고유 첨가제입니다.

테스트 사례

[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

답변

XN!sSdA

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)

œcS€ṢIP

œ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

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

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

{IsM.cFQ

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

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

(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

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