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 N
a 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
fuente
N <= K
?falsey
?Respuestas:
MATL , 7 bytes
Pruébalo en línea!
Devuelve
true
(se muestra como1
) ofalse
(se muestra como0
).fuente
Jalea, 7 bytes
Pruébalo en línea!
Devuelve un número positivo para verdadero y cero para falsey.
fuente
Matlab, 78 bytes
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:
fuente
k
. PD: ¡El resaltado de sintaxis de Matlab finalmente funciona!n
!Pyth, 8 bytes
Banco de pruebas.
fuente
splat
significaQ
al final.Haskell, 69 bytes
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.
fuente
JavaScript (ES6), 132 bytes
Construye las listas de aditivos de 1 a n y luego comprueba la última para la unicidad.
fuente
Brachylog , 20 bytes
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
Predicado 1: Encuentre todos los subconjuntos ordenados de longitud fija de una lista
fuente
Julia,
4641 bytesPrué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 . Mapeamossum
sobre estas matrices y almacenamos el resultado en t .t∪t
realiza la unión de conjunto de la matriz t consigo misma, que funciona como la más largaunique
en este caso.Finalmente, comparamos t con la t deduplicada , devolviendo
true
si y solo si todas las sumas son diferentes.fuente
Python, 89 bytes
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 . Mapeamossum
las 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^y
devolverá 0 yall
devolverá False . Por el contrario, si todas las sumas son únicas,x^y
siempre serán verdaderas yany
devolverán Verdadero .fuente
J, 34 bytes
Enfoque directo, solo requiere el
stats
complemento para lacomb
función. Devuelve0
falso y1
verdadero.Como alternativa al uso de la función
comb
incorporada, hay una solución de 38 bytes que genera el conjunto de potencia y elige los subconjuntos de tamaño n .Uso
fuente
stats
módulo. ¡Muy agradable!Rubí , 50 bytes.
Pruébalo en línea!
Si todos los elementos son únicos,
uniq!
devuelvenil
. 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+)
Pruébalo en línea!
fuente
R , 41 bytes
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!
fuente