Помните, что набор неупорядочен без дубликатов.
Определение N -uniquely аддитивная S , длина которой К представляет собой набор таким образом, что все N -длина подмножества S суммы к различным номерам. Другими словами, суммы всех N- длинных подмножеств S все различны.
Цель. Задавая массив / набор в качестве входных данных и число N
для функции или для полной программы в любом приемлемом формате, найдите и верните или выведите истинное значение или значение Falsey (допустимо ошибочное значение Falsey), обозначающее, является ли ввод 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
. Вот все возможные суммы длины четыре:
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
источник
N <= K
?falsey
?Ответы:
MATL , 7 байт
Попробуйте онлайн!
Возвращает
true
(отображается как1
) илиfalse
(отображается как0
).источник
Желе, 7 байт
Попробуйте онлайн!
Возвращает положительное число для истины и ноль для фальси.
источник
Matlab, 78 байт
Эта функция возвращает положительное значение (фактически
n
) для правдивого и возвращает ошибку в виде ложного ответа (действителен согласно этому комментарию )Объяснение:
источник
k
. PS: подсветка синтаксиса Matlab наконец работает !!!n
!Pyth, 8 байт
Тестирование.
источник
splat
значит?Q
в конце.Haskell, 69 байт
Пример использования:
6 # [3,4,7,9,12,16,18]
->True
.Непосредственная реализация определения: составьте список сумм всех подпоследовательностей длины n и проверьте, совпадает ли он с удаленными дубликатами.
источник
JavaScript (ES6), 132 байта
Создает аддитивные списки от 1 до n, а затем проверяет последний на уникальность.
источник
Брахилог , 20 байт
Ожидается список, содержащий список, а затем целое число как входной, а не выходной, например
run_from_atom(':{[L:I]hs.lI}f:+aLdL', [[1:2:3:5]:2]).
.объяснение
Главный предикат
Предикат 1: Найти все упорядоченные подмножества фиксированной длины списка
источник
Юлия,
4641 байтПопробуйте онлайн!
Как это работает
Это (пере) определяет бинарный оператор
\
для аргументов Array / Int.combinations(x,n)
возвращает все массивы ровно n различных элементов x . Мы отображаемsum
эти массивы и сохраняем результат в t .t∪t
выполняет объединение множества массива t с самим собой, чтоunique
в этом случае работает дольше .Наконец, мы сравниваем t с дедуплицированным t , возвращая,
true
если и только если все суммы разные.источник
Python, 89 байт
Проверьте это на Ideone .
Как это работает
c(s,n)
перечисляет все n -комбинации s , т. е. все списки из n различных элементов s . Мы отображаемsum
полученные списки, таким образом вычисляя все возможные суммы подсписков длины n .После подопечных мы используем
c(...,2)
для создания всех пар полученные суммы. Если любые две суммы x и y равны,x^y
вернет 0 иall
вернет False . И наоборот, если все суммы уникальны,x^y
всегда будут правдивыми иany
вернут True .источник
J, 34 байта
Прямой подход, требует только
stats
надстройки дляcomb
функции. Возвращает0
за ложь и1
за истину.В качестве альтернативы использованию
comb
встроенного, существует 38-байтовое решение, которое генерирует набор мощности и выбирает подмножества размера n .Применение
источник
stats
модуле. Очень хорошо!Рубин , 50 байт
Попробуйте онлайн!
Если все элементы уникальны,
uniq!
возвращаетсяnil
. Отрицание этого результата, как в,!(...).uniq!
делает хороший тест на уникальность.Этот вопрос был опубликован за несколько недель до выпуска Ruby 2.4.0-preview1
Enumerable#sum
, в котором было бы сэкономлено 9 байт.41 байт (Ruby 2.4+)
Попробуйте онлайн!
источник
R , 41 байт
Суммирует все n-длина подмножеств s и проверяет, все ли значения в таблице сопряженности этих сумм равны 1 (все суммы уникальны).
Попробуйте онлайн!
источник