세트는 중복없이 순서가 정렬되지 않습니다.
정의 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
답변
MATL , 7 바이트
XN!sSdA
true
(으로 표시 1
) 또는 false
(으로 표시 )을 반환 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)
답변
젤리, 7 바이트
œcS€ṢIP
진리의 경우 양수를, 거짓의 경우 0을 반환합니다.
œ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 바이트
function n=f(s,n);p=perms(s);k=sum(unique(sort(p(:,1:n)),'rows')');unique(k)-k
이 함수는 양의 값을 (사실 반환 n
에 대한) truthy 반환 A와 오류 falsey의 (에 유효한있어서, 대답 이 댓글 )
설명:
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 바이트
{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)?
답변
하스켈, 69 바이트
import Data.List
n#s=(==)=<<nub$[sum x|x<-subsequences s,length x==n]
사용 예 : 6 # [3,4,7,9,12,16,18]
-> True
.
정의의 직접 구현 : 길이 n의 모든 서브 시퀀스의 합계 목록을 작성하고 중복이 제거 된 것과 동일한 지 점검하십시오.
답변
자바 스크립트 (ES6), 132 바이트
(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
추가 목록을 1에서 n까지 쌓은 다음 마지막 목록에서 고유성을 검사합니다.
답변
Brachylog , 20 바이트
:1f:+aLdL
[L:I]hs.lI
목록을 포함하는 목록을 예상 한 다음 정수를 입력으로, 출력은 출력하지 않습니다 (예 🙂 run_from_atom(':{[L:I]hs.lI}f:+aLdL', [[1:2:3:5]:2]).
.
설명
-
주요 술어
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
-
술어 1 :리스트의 고정 길이의 모든 정렬 된 서브 세트 찾기
[L:I] Input = [L:I] hs. Unify Output with an ordered subset of L lI True if I is the length of Output