Conjuntos aditivos N-únicos

10

Recuerde que un conjunto no está ordenado sin duplicados.

Definición Un conjunto S aditivo N único cuya longitud es K es un conjunto tal que todos los subconjuntos de longitud N en S suman números diferentes. En otras palabras, las sumas de todos los subconjuntos de longitud N de S son todas distintas.

Objetivo Dado un vector / conjunto como entrada y un número Na una función o un programa completo en cualquier formato razonable, encontrar y retorno o salida de un valor Truthy o Falsey- (erroring para Falsey- está bien) que indica si o no la entrada es N - Exclusivamente aditivo.

Puede suponer que cada elemento aparece como máximo una vez y que cada número está dentro del tipo de datos nativo de su idioma. Si es necesario, también puede suponer que la entrada está ordenada. Por último, puedes asumir eso 0 < N <= K.

Ejemplos

Consideremos el conjunto S = {1, 2, 3, 5}y N = 2. Aquí están todas las sumas de todos los pares únicos S(para los únicos son los únicos de interés para las sumas):

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

Podemos ver que no hay duplicados en la salida, por lo que S es aditivo únicamente en 2.


Consideremos ahora el conjunto T = {12, 17, 44, 80, 82, 90}y N = 4. Aquí están todas las sumas posibles de longitud cuatro:

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

Todos son únicos, por lo que T es 4 aditivos únicos.

Casos de prueba

[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
fuente
Quieres decir N <= K?
Neil
@Neil Sí, lo hago. ¡Lo siento!
Conor O'Brien
¿Un error cuenta como algo falsey?
flawr
@flawr Claro, lo aceptaré
Conor O'Brien el

Respuestas:

3

MATL , 7 bytes

XN!sSdA

Pruébalo en línea!

Devuelve true(se muestra como 1) o false(se muestra 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
fuente
4

Jalea, 7 bytes

œcS€ṢIP

Pruébalo en línea!

Devuelve un número positivo para verdadero y cero 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
Pomo de la puerta
fuente
3

Matlab, 78 bytes

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

Esta función devuelve un valor positivo (de hecho n) para la verdad y devuelve un error como respuesta falsey (válido según este comentario )

Explicación:

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
falla
fuente
¿Por qué error?
Conor O'Brien
1
Acabo de agregar una explicación. El error proviene de la última línea. Causa un error si tenemos duplicados k. PD: ¡El resaltado de sintaxis de Matlab finalmente funciona!
flawr
¡Buena idea devolver lo mismo n!
Luis Mendo
2

Pyth, 8 bytes

{IsM.cFQ

Banco de pruebas.

       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)?
Pomo de la puerta
fuente
Que splatsignifica
Conor O'Brien
@ CᴏɴᴏʀO'Bʀɪᴇɴ Lo mismo que significa en cualquier otro idioma: usar una matriz como argumentos para una función.
Pomo de la puerta
Oh, claro, soy tonto: p gracias
Conor O'Brien
2
en cualquier otro idioma que realmente tenga esta función
flawr
2
Arreglé el error que requería eso Qal final.
isaacg
2

Haskell, 69 bytes

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

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

Implementación directa de la definición: haga una lista de sumas de todas las subsecuencias de longitud n y compruebe si es igual a si se eliminan los duplicados.

nimi
fuente
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

Construye las listas de aditivos de 1 a n y luego comprueba la última para la unicidad.

Neil
fuente
2

Brachylog , 20 bytes

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

Espera una lista que contiene la lista y luego el número entero como Entrada, y no Salida, por ejemplo run_from_atom(':{[L:I]hs.lI}f:+aLdL', [[1:2:3:5]:2])..

Explicación

  • 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: Encuentre todos los subconjuntos ordenados de longitud fija de una 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
fuente
2

Julia, 46 41 bytes

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

Pruébalo en línea!

Cómo funciona

Esto (re) define el operador binario \para los argumentos Array / Int.

combinations(x,n)devuelve todas las matrices de exactamente n elementos diferentes de x . Mapeamos sumsobre estas matrices y almacenamos el resultado en t .

t∪trealiza la unión de conjunto de la matriz t consigo misma, que funciona como la más larga uniqueen este caso.

Finalmente, comparamos t con la t deduplicada , devolviendo truesi y solo si todas las sumas son diferentes.

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

Pruébelo en Ideone .

Cómo funciona

c(s,n)enumera todas las n combinaciones de s , es decir, todas las listas de n elementos diferentes de s . Mapeamos sumlas listas resultantes, calculando así todas las sumas posibles de sublistas de longitud n .

Después de las salas, usamos c(...,2)para crear todos los pares de las sumas resultantes. Si dos sumas x e y son iguales, x^ydevolverá 0 y alldevolverá False . Por el contrario, si todas las sumas son únicas, x^ysiempre serán verdaderas y anydevolverán Verdadero .

Dennis
fuente
1

J, 34 bytes

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

Enfoque directo, solo requiere el statscomplemento para la combfunción. Devuelve 0falso y 1verdadero.

Como alternativa al uso de la función combincorporada, hay una solución de 38 bytes que genera el conjunto de potencia y elige los subconjuntos de tamaño 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
millas
fuente
Wow, no sabía sobre el statsmódulo. ¡Muy agradable!
Conor O'Brien
También me enteré de eso, realmente no he profundizado mucho en los complementos en J. Si fuera más valiente, intentaría los complementos gráficos.
millas
0

Rubí , 50 bytes.

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

Pruébalo en línea!

Si todos los elementos son únicos, uniq!devuelve nil. Negar ese resultado, como en !(...).uniq!hace una buena prueba de singularidad.

Esta pregunta fue publicada unas semanas antes de Ruby 2.4.0-preview1, que introdujo Enumerable#sum, lo que ahorraría 9 bytes aquí.

41 bytes (Ruby 2.4+)

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

Pruébalo en línea!

benj2240
fuente
0

R , 41 bytes

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

Suma todos los subconjuntos de longitud n de sy comprueba si todos los valores en una tabla de contingencia de estas sumas son 1 (todas las sumas son únicas).

Pruébalo en línea!

Robert Hacken
fuente