Сначала несколько определений:
- Учитывая
n
иk
, рассмотрим отсортированный список мультимножеств , где для каждого мультимножества мы выбираемk
числа{0, 1, ..., n-1}
с повторениями.
Например, для n=5
и k=3
мы имеем:
[(0, 0, 0), (0, 0, 1), (0, 0, 2), (0, 0, 3), (0, 0, 4), (0, 1, 1), ( 0, 1, 2), (0, 1, 3), (0, 1, 4), (0, 2, 2), (0, 2, 3), (0, 2, 4), (0, 3, 3), (0, 3, 4), (0, 4, 4), (1, 1, 1), (1, 1, 2), (1, 1, 3), (1, 1, 4), (1, 2, 2), (1, 2, 3), (1, 2, 4), (1, 3, 3), (1, 3, 4), (1, 4, 4) , (2, 2, 2), (2, 2, 3), (2, 2, 4), (2, 3, 3), (2, 3, 4), (2, 4, 4), ( 3, 3, 3), (3, 3, 4), (3, 4, 4), (4, 4, 4)]
- Часть представляет собой список мультимножеств с тем свойством , что размер пересечения всех мультимножеств в части, по меньшей мере
k-1
. То есть мы берем все мультимножества и пересекаем их (используя пересечение мультимножеств) одновременно. В качестве примеров,[(1, 2, 2), (1, 2, 3), (1, 2, 4)]
является частью, поскольку ее пересечение имеет размер 2, но[(1, 1, 3),(1, 2, 3),(1, 2, 4)]
это не так, потому что его пересечение имеет размер 1.
задача
Ваш код должен принимать два аргумента n
и k
. Затем он должен жадно пройти через эти мультимножества в отсортированном порядке и вывести части списка. Для случая n=5, k=3
правильное разбиение:
(0, 0, 0), (0, 0, 1), (0, 0, 2), (0, 0, 3), (0, 0, 4)
(0, 1, 1), (0, 1, 2), (0, 1, 3), (0, 1, 4)
(0, 2, 2), (0, 2, 3), (0, 2, 4)
(0, 3, 3), (0, 3, 4)
(0, 4, 4)
(1, 1, 1), (1, 1, 2), (1, 1, 3), (1, 1, 4)
(1, 2, 2), (1, 2, 3), (1, 2, 4)
(1, 3, 3), (1, 3, 4)
(1, 4, 4)
(2, 2, 2), (2, 2, 3), (2, 2, 4)
(2, 3, 3), (2, 3, 4)
(2, 4, 4)
(3, 3, 3), (3, 3, 4)
(3, 4, 4), (4, 4, 4)
Вот еще один пример для n = 4, k = 4
.
(0, 0, 0, 0), (0, 0, 0, 1), (0, 0, 0, 2), (0, 0, 0, 3)
(0, 0, 1, 1), (0, 0, 1, 2), (0, 0, 1, 3)
(0, 0, 2, 2), (0, 0, 2, 3)
(0, 0, 3, 3)
(0, 1, 1, 1), (0, 1, 1, 2), (0, 1, 1, 3)
(0, 1, 2, 2), (0, 1, 2, 3)
(0, 1, 3, 3)
(0, 2, 2, 2), (0, 2, 2, 3)
(0, 2, 3, 3), (0, 3, 3, 3)
(1, 1, 1, 1), (1, 1, 1, 2), (1, 1, 1, 3)
(1, 1, 2, 2), (1, 1, 2, 3)
(1, 1, 3, 3)
(1, 2, 2, 2), (1, 2, 2, 3)
(1, 2, 3, 3), (1, 3, 3, 3)
(2, 2, 2, 2), (2, 2, 2, 3)
(2, 2, 3, 3), (2, 3, 3, 3)
(3, 3, 3, 3)
Разъяснение того, что означает жадность: для каждого мультимножества, в свою очередь, мы смотрим, можно ли добавить его к существующей части. Если это возможно, мы можем добавить это. Если это невозможно, мы начинаем новую часть. Мы рассмотрим мультимножества в отсортированном порядке, как в примере, приведенном выше.
Вывод
Вы можете вывести разделение в любом удобном для вас формате. Однако мультимножества должны быть написаны горизонтально в одну строку. То есть отдельный мультимножество не должно быть написано вертикально или разбито на несколько строк. Вы можете выбрать способ разделения представления деталей на выходе.
Предположения
Мы можем предположить это n >= k > 0
.
источник
(0, 4, 4)
само по себе? Учитывая ваше описание, я думаю, что его "часть" будет(0, 4, 4), (1, 4, 4), (2, 4, 4), (3, 4, 4), (4, 4, 4)
. Аналогично для(0, 0, 3, 3)
второго контрольного примера.Ответы:
Желе ,
2625 байтПолная программа, которая печатает представление списка списков, каждый список является частью, например, для n = 5, k = 3:
Примечание: используемое представление удаляет лишние
[
и]
вокруг списки длины 1.Попробуйте онлайн! или посмотрите красивую версию для печати (стоимость 3 байта)
Как?
источник
MATLAB, 272 байта
Вывод:
Две пустые строки между разными частями.
Ungolfed:
Объяснение:
Сначала мы находим все мультимножества с грубой силой:
repmat(0:n-1, 1, k)
повторяет вектор значений от0
доn-1
k
.nchoosek(x, k)
возвращает матрицу, содержащую все k-комбинации повторяющегося вектора.sort(x, 2)
сортирует все k-комбинации, а затемunique(x, 'rows')
удаляет все дубликаты.p=zeros(0,k);
создает пустую матрицу соk
столбцами. Мы будем использовать его в качестве стека. На каждой итерации самого внешнегоfor
цикла мы сначала добавляем текущий мультимножество в указанный стек:p=[p;l(i,:)];
.Затем мы проверяем, является ли пересечение всех мультимножеств в стеке, по крайней мере,
k-1
длинным с помощью следующего кода (мы не можем использоватьintersect
команду MATLAB для проверки пересечений, потому что она возвращает набор, но нам нужен мультимножество):Теперь, если пересечение достаточно длинное
a == 0
, иначеa == 1
.Если пересечение недостаточно длинное, мы печатаем новую строку и очищаем стек:
Затем мы просто печатаем текущий мультимножество:
источник
MATL , 34 байта
Части разделены линией, содержащей пробелы.
Попробуйте онлайн!
объяснение
Отказ от ответственности: кажется, что этот метод работает (и он работает в тестовых случаях), но у меня нет доказательств того, что он всегда работает
Мультимножества сортируются как внутри (т. Е. Каждый мультимножество имеет неубывающие записи), так и внешне (т. Е. Мультимножество M предшествует мультимножеству N, если M предшествует N лексикографически).
Чтобы вычислить пересечение мультимножества, отсортированные мультимножества располагаются в виде строк матрицы, и последовательные разности вычисляются вдоль каждого столбца. Если все столбцы, кроме одного, имеют все различия, равные нулю, мультимножества принадлежат одной и той же части.
Этот тест дал бы ложноотрицательный результат для мультимножеств, таких как
(1,2,3)
и(2,3,4)
: даже если2
,3
общие данные, они не будут обнаружен , как таковые , потому что они находятся в несовпадающих столбцах.Тем не менее, это не проблема, по крайней мере, в тестовых случаях. Похоже, что тест между мультимножествами, подобный
1,2,3
и2,3,4
никогда не выполняемый на самом деле, потому что некоторые промежуточные мультимножества дали отрицательный результат, и поэтому они уже находятся в разных частях. Если это действительно так, то причина, несомненно, связана с тем, что мультимножества отсортированы.У меня нет доказательства этого, хотя. Кажется, это работает.
источник
n=k=4
случае, когда у нас начинается новая деталь(0, 0, 3, 3)
, векторизованная последовательная разница между этим и предыдущим множеством(0, 0, 2, 3)
имеет только одно отличие, так как же «деталь до сих пор» делает эту работу? (или, что эквивалентно, какой результат предыдущего шага был использован вместо(0, 0, 2, 3)
?)PHP, 245 байт
Попробуйте онлайн!
расширенный
Вывести в виде строки
n> 15 для большей точности
источник
0
для(16**16-1)%16
и длинная версия работает только с точностью, которая необходима дляn>15
bcmod(bcsub(bcpow(16,16),1),16)
является15
php.net/manual/en/ref.bc.php