Conjuntos de aditivos exclusivos N

10

Lembre-se de que um conjunto não é ordenado sem duplicatas.

Definição Um conjunto N- aditivo exclusivo S, cujo comprimento é K, é um conjunto tal que todos os subconjuntos de comprimento N em S somam números diferentes. Em outras palavras, as somas de todos os subconjuntos de comprimento N de S são todas distintas.

Objetivo Dado um array / conjunto como entrada e um número Npara uma função ou para um programa completo em qualquer formato razoável, encontre e retorne ou produza um valor de verdade ou falsey (errar para falsey é bom) indicando se a entrada é N ou não - exclusivamente aditivo.

Você pode supor que cada elemento apareça apenas no máximo uma vez e que cada número esteja dentro do tipo de dados nativo do seu idioma. Se necessário, você também pode assumir que a entrada está classificada. Por último, você pode assumir isso 0 < N <= K.

Exemplos

Vamos considerar o conjunto S = {1, 2, 3, 5}e N = 2. Aqui estão todas as somas de todos os pares únicos S(pois os únicos são os únicos de interesse para somas):

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

Podemos ver que não há duplicatas na saída, então S é 2-exclusivamente aditivo.


Vamos agora considerar o conjunto T = {12, 17, 44, 80, 82, 90}e N = 4. Aqui estão todas as somas possíveis de comprimento quatro:

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

Eles são todos únicos e, portanto, T é um aditivo exclusivo de 4.

Casos de teste

[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
Conor O'Brien
fonte
Você quer dizer N <= K?
305 Neil
@ Neil Sim, eu faço. Desculpa!
Conor O'Brien
Um erro conta como algo falsey?
flawr
@flawr Claro, eu aceito isso #
Conor O'Brien

Respostas:

3

MATL , 7 bytes

XN!sSdA

Experimente online!

Retorna true(exibido como 1) ou false(exibido como 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)
Luis Mendo
fonte
4

Geléia, 7 bytes

œcS€ṢIP

Experimente online!

Retorna um número positivo para truthy e zero para 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
Maçaneta da porta
fonte
3

Matlab, 78 bytes

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

Esta função retorna um valor positivo (na verdade n) para truthy e retorna um erro como um Falsey resposta (de acordo válido para este comentário )

Explicação:

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
flawr
fonte
Por que erro?
Conor O'Brien
11
Acabei de adicionar uma explicação. O erro vem da última linha. Isso causa um erro se tivermos duplicatas k. PS: O destaque da sintaxe do Matlab finalmente funciona !!!
flawr
Boa idéia para retornar o mesmo n!
Luis Mendo
2

Pitão, 8 bytes

{IsM.cFQ

Suíte de teste.

       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)?
Maçaneta da porta
fonte
O que splatsignifica isso ?
Conor O'Brien
@ CᴏɴᴏʀO'Bʀɪᴇɴ O mesmo que significa em qualquer outra linguagem: use uma matriz como argumento para uma função.
Maçaneta
Oh, bem, eu sou burro: p graças
Conor O'Brien
2
em todas as outras línguas que realmente tem esta função
flawr
2
Corrigi o bug que exigia isso Qno final.
Isaacg
2

Haskell, 69 bytes

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

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

Implementação direta da definição: faça uma lista de somas de todas as subsequências de comprimento n e verifique se é igual a duplicatas removidas.

nimi
fonte
2

JavaScript (ES6), 132 bytes

(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

Constrói as listas de aditivos de 1 a ne verifica a última quanto à exclusividade.

Neil
fonte
2

Braquilog , 20 bytes

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

Espera uma lista contendo a lista e, em seguida, o número inteiro como Entrada, e sem Saída, por exemplo run_from_atom(':{[L:I]hs.lI}f:+aLdL', [[1:2:3:5]:2])..

Explicação

  • Predicado 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
    
  • Predicado 1: encontre todos os subconjuntos ordenados de comprimento fixo de uma lista

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

Julia, 46 41 bytes

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

Experimente online!

Como funciona

Isso (re) define o operador binário \para os argumentos Array / Int.

combinations(x,n)retorna todas as matrizes de exatamente n elementos diferentes de x . Mapeamos sumsobre essas matrizes e armazenar o resultado em t .

t∪trealiza a união do conjunto t com ele próprio, que funciona como o mais longo uniqueneste caso.

Por fim, comparamos t com deduplicado t , retornando truese e somente se todas as somas forem diferentes.

Dennis
fonte
2

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

Teste em Ideone .

Como funciona

c(s,n)lista todas as n combinações de s , ou seja, todas as listas de n elementos diferentes de s . Mapeamos sumas listas resultantes, calculando assim todas as somas possíveis de sublistas de comprimento n .

Após as alas, usamos c(...,2)para criar todos os pares das somas resultantes. Se quaisquer duas somas x e y forem iguais, x^yretornará 0 e allretornará False . Por outro lado, se todas as somas forem únicas, x^ysempre anyserão verdadeiras e retornarão True .

Dennis
fonte
1

J, 34 bytes

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

Abordagem direta, requer apenas o statscomplemento para a combfunção. Retorna 0para false e 1true.

Como alternativa ao uso combinterno, existe uma solução de 38 bytes que gera o conjunto de energia e escolhe os subconjuntos de tamanho n .

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

Uso

   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
milhas
fonte
Uau, não sabia sobre o statsmódulo. Muito agradável!
Conor O'Brien
Acabei de descobrir sobre isso também, eu realmente não mergulhei muito nos complementos do J. Se eu fosse mais corajoso, tentaria os complementos gráficos.
milhas
0

Ruby , 50 bytes

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

Experimente online!

Se todos os elementos forem exclusivos, uniq!retornará nil. Negar esse resultado, como !(...).uniq!faz um bom teste de exclusividade.

Esta questão foi publicada algumas semanas antes do Ruby 2.4.0-preview1, que foi introduzido Enumerable#sum, o que salvaria 9 bytes aqui.

41 bytes (Ruby 2.4 ou superior)

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

Experimente online!

benj2240
fonte
0

R , 41 bytes

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

Soma todos os subconjuntos n de comprimento de se verifica se todos os valores em uma tabela de contingência dessas somas são 1 (todas as somas são únicas).

Experimente online!

Robert Hacken
fonte