Жадно разделить список комбинаций с повторением

10

Сначала несколько определений:

  • Учитывая 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.

Джонатан Аллан
источник
@ LuisMendo Я только что сделал ошибку. Я имел в виду, что мультимножества должны быть написаны горизонтально на одной строке.
В первом тестовом случае, почему это (0, 4, 4)само по себе? Учитывая ваше описание, я думаю, что его "часть" будет (0, 4, 4), (1, 4, 4), (2, 4, 4), (3, 4, 4), (4, 4, 4). Аналогично для (0, 0, 3, 3)второго контрольного примера.
Грег Мартин,
@GregMartin Из-за жадности метода. Вы правы в том, что это в целом будет неоптимальным. Минимальное количество деталей, которое вы можете получить не жадным методом, - интересный, если и сложный вопрос,
О, вы буквально имеете в виду, что как только следующий термин не соответствует «активной» части, эта часть закрывается навсегда. Хорошо.
Грег Мартин

Ответы:

4

Желе , 26 25 байт

œ&µL‘<⁴ȧ⁹ȯ
œċµç\L€=⁴œṗµḊ’

Полная программа, которая печатает представление списка списков, каждый список является частью, например, для 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]]]

Примечание: используемое представление удаляет лишние [ и ] вокруг списки длины 1.

Попробуйте онлайн! или посмотрите красивую версию для печати (стоимость 3 байта)

Как?

œ&µL‘<⁴ȧ⁹ȯ - Link 1, conditional multi-set intersection: list x, list y
œ&         - multi-set intersection(x, y)
  µ        - monadic chain separation (call that i)
   L       - length(i)
    ‘      - increment
     <     - less than?:
      ⁴    -     2nd program input, k
       ȧ   - logical and with:
        ⁹  -     link's right argument, y (y if i is too short, else 0)
         ȯ - logical or (y if i is too short, else i)

œċµç\L€=⁴œṗµḊ’ - Main link: n, k
œċ             - combinations with replacement(n, k) (sorted since n implies [1,n])
  µ            - monadic chain separation (call that w)
         œṗ    - partition w at truthy indexes of:
   ç\          -     reduce w with last link (1) as a dyad
     L€        -     length of €ach
        ⁴      -     2nd program input, k
       =       -     equal (vectorises)
           µ   - monadic chain separation
            Ḋ  - dequeue (since the result will always start with an empty list)
             ’ - decrement (vectorises) (since the Natural numbers were used by œċ)
Джонатан Аллан
источник
Это замечательно. Спасибо.
3

MATLAB, 272 байта

function g(n,k);l=unique(sort(nchoosek(repmat(0:n-1,1,k),k),2),'rows');p=zeros(0,k);for i=1:size(l,1)p=[p;l(i,:)];a=0;for j=1:size(p,1)for m=1:size(p,1)b=0;for h=1:k if(p(j,h)==p(m,h))b=b+1;end;end;if(b<k-1)a=1;end;end;end;if(a)fprintf('\n');p=l(i,:);end;disp(l(i,:));end;

Вывод:

>> g(5,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

>> g(4,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

Две пустые строки между разными частями.

Ungolfed:

function g(n,k);
l=unique(sort(nchoosek(repmat(0:n-1,1,k),k),2),'rows');
p=zeros(0,k);
for i=1:size(l,1)
    p=[p;l(i,:)];
    a=0;
    for j=1:size(p,1)
        for m=1:size(p,1)
            b=0;
            for h=1:k
                if(p(j,h)==p(m,h))
                    b=b+1;
                end;
            end;
                if(b<k-1)
                    a=1;
                end;
        end;
    end;
    if(a)
        fprintf('\n');
        p=l(i,:);
    end;
    disp(l(i,:));
end;

Объяснение:

Сначала мы находим все мультимножества с грубой силой:

l=unique(sort(nchoosek(repmat(0:n-1,1,k),k),2),'rows');

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;
for j=1:size(p,1)
    for m=1:size(p,1)
        b=0;
        for h=1:k 
            if(p(j,h)==p(m,h))
                b=b+1;
            end;
        end;
        if(b<k-1)
            a=1;
        end;
    end;
end;

Теперь, если пересечение достаточно длинное a == 0, иначеa == 1 .

Если пересечение недостаточно длинное, мы печатаем новую строку и очищаем стек:

if(a)
    fprintf('\n');
    p=l(i,:); % Only the current multiset will be left in the stack.
end;

Затем мы просто печатаем текущий мультимножество:

disp(l(i,:));
Steadybox
источник
Похоже, вы взломали его! Не могли бы вы объяснить свой метод?
@Lembik Я добавил объяснение.
Steadybox
3

MATL , 34 байта

vi:qiZ^!S!Xu!"@!&vt1&dXasq?0&Y)0cb

Части разделены линией, содержащей пробелы.

Попробуйте онлайн!

объяснение

Отказ от ответственности: кажется, что этот метод работает (и он работает в тестовых случаях), но у меня нет доказательств того, что он всегда работает

Мультимножества сортируются как внутри (т. Е. Каждый мультимножество имеет неубывающие записи), так и внешне (т. Е. Мультимножество M предшествует мультимножеству N, если M предшествует N лексикографически).

Чтобы вычислить пересечение мультимножества, отсортированные мультимножества располагаются в виде строк матрицы, и последовательные разности вычисляются вдоль каждого столбца. Если все столбцы, кроме одного, имеют все различия, равные нулю, мультимножества принадлежат одной и той же части.

Этот тест дал бы ложноотрицательный результат для мультимножеств, таких как (1,2,3)и (2,3,4): даже если 2,3 общие данные, они не будут обнаружен , как таковые , потому что они находятся в несовпадающих столбцах.

Тем не менее, это не проблема, по крайней мере, в тестовых случаях. Похоже, что тест между мультимножествами, подобный 1,2,3и 2,3,4никогда не выполняемый на самом деле, потому что некоторые промежуточные мультимножества дали отрицательный результат, и поэтому они уже находятся в разных частях. Если это действительно так, то причина, несомненно, связана с тем, что мультимножества отсортированы.

У меня нет доказательства этого, хотя. Кажется, это работает.

v           % Concatenate stack vertically: gives an empty array. This will
            % grow into the first part
i:q         % Input n. Push [0 1 ... n-1]
i           % Input k
Z^          % Cartesian power. Each Cartesian tuple is on a row
!S!         % Sort each row
Xu          % Unique rows. This gives all multisets, sorted, each on a row
!           % Transpose
"           % For each column
  @!        %   Push current multiset as a row
  &v        %   Vertically concatenate with the part so far
  t         %   Duplicate
  1&d       %   Consecutive differences along each column
  Xas       %   Number of columns that contain at least one non-zero entry
  q?        %   If that number is not 1 (this means that the current 
            %   multiset should begin a new part)
    0&Y)    %     Push last row, then the array with the remaining rows.
            %     Said array is a part, which we now know is complete
    0c      %     Push character 0. This will be shown as a line containing 
            %     a space. This is used as a separator between parts.
    b       %     Bubble up. This moves the loose row to the top. This row 
            %     is the beginning of a new part
            %   Implicitly end if
            % Implicitly end for
            % Implicitly display
Луис Мендо
источник
Это очень впечатляет.
Я пытаюсь понять, будет ли метод, который вы описали, всегда работать. Я вижу в этом то, что в n=k=4случае, когда у нас начинается новая деталь (0, 0, 3, 3), векторизованная последовательная разница между этим и предыдущим множеством (0, 0, 2, 3)имеет только одно отличие, так как же «деталь до сих пор» делает эту работу? (или, что эквивалентно, какой результат предыдущего шага был использован вместо (0, 0, 2, 3)?)
Джонатан Аллан
Ах, я вижу, вы выполняете последовательную разницу. Да, это всегда должно работать! Вы буквально ищете точки, в которых изменяется более одного элемента, а не пересечение с несколькими наборами, просто векторизованное пересечение - которое будет работать, так как начальные сортировки сортируются с самого начала.
Джонатан Аллан
@JonathanAllan Да, это последовательная разница, а не пересечение. Я до сих пор не вижу ясности, что это всегда будет работать, но если вы так говорите ... :-)
Луис Мендо
1

PHP, 245 байт

for(;$i<($n=$argv[1])**$m=$argv[2];$i++){for($a=[],$v=$i;$v|count($a)<$m;$v=$v/$n^0)array_unshift($a,$v%$n);sort($a);in_array($a,$r)?:$r[]=$a;}foreach($r as$k=>$v)$k&&count(array_diff_assoc($x[$c][0],$v))<2?$x[$c][]=$v:$x[++$c][]=$v;print_r($x);

Попробуйте онлайн!

расширенный

for(;$i<($n=$argv[1])**$m=$argv[2];$i++){ # loop till $argv[1]**$argv[2]
    for($a=[],$v=$i;$v|count($a)<$m;$v=$v/$n^0) 
    array_unshift($a,$v%$n); # create base n array
    sort($a); #sort array
    in_array($a,$r)?:$r[]=$a; # if sorted array is not in result add it
}    
foreach($r as$k=>$v)
    $k&& # > first item and
    count(array_diff_assoc($x[$c][0],$v))<2 # if difference is only 1 item between actual item and first item in last storage item
    ?$x[$c][]=$v # add item in last storage array
    :$x[++$c][]=$v; # make a new last storage array
print_r($x); # Output as array

Вывести в виде строки

foreach($x as$y){$p=[];
foreach($y as$z){$p[]=$o="(".join(",",$z).")";}
    echo join(", ",$p)."\n";
}

n> 15 для большей точности

for($i=0;$i<bcpow($argv[1],$argv[2]);$i=bcadd($i,1)){
    for($a=[],$v=$i;$v|count($a)<$argv[2];$v=bcdiv($v,$argv[1]))
    array_unshift($a,bcmod($v,$argv[1]));
    sort($a);
    in_array($a,$r)?:$r[]=$a;
}
Йорг Хюльсерманн
источник
Кажется, это работает! Но что вы подразумеваете под большей точностью?
@Lembik короткая версия возвращает 0для (16**16-1)%16и длинная версия работает только с точностью, которая необходима для n>15 bcmod(bcsub(bcpow(16,16),1),16)является 15 php.net/manual/en/ref.bc.php
Йорг Hülsermann