Najpierw kilka definicji:

• Biorąc pod uwagę ni k, rozważ posortowaną listę multisetów , gdzie dla każdego multisetu wybieramy kliczby {0, 1, ..., n-1}z powtórzeniami.

Na przykład dla n=5i k=3mamy:

[(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)]

• Częścią jest lista multisets z własności, że wielkość przecięcia wszystkich multisets w części wynosi co najmniej k-1. To znaczy, że bierzemy wszystkie multisety i przecinamy je (używając przecięcia multiset) jednocześnie. Jako przykład, [(1, 2, 2), (1, 2, 3), (1, 2, 4)]jest częścią, ponieważ jej przecięcie ma rozmiar 2, ale [(1, 1, 3),(1, 2, 3),(1, 2, 4)]nie jest, ponieważ jego przecięcie ma rozmiar 1.

Zadanie

Twój kod powinien przyjąć dwa argumenty ni k. Następnie powinien łapczywie przejrzeć te multisety w posortowanej kolejności i wypisać części listy. W takim przypadku n=5, k=3poprawne partycjonowanie to:

(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)

Oto kolejny przykład 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)

Wyjaśnienie, co oznacza chciwość : Z kolei dla każdego zbioru wielosetowego sprawdzamy, czy można go dodać do istniejącej części. Jeśli tak, możemy to dodać. Jeśli nie, zaczniemy nową część. Patrzymy na multisety w posortowanej kolejności, jak w przykładzie podanym powyżej.

Wynik

Możesz wydzielić partycjonowanie w dowolnym rozsądnym formacie, jaki ci się podoba. Jednak multisety powinny być zapisywane poziomo w jednym wierszu. Oznacza to, że pojedynczy multiset nie powinien być zapisywany w pionie ani rozłożony na kilka wierszy. Możesz wybrać sposób oddzielenia reprezentacji części na wyjściu.

Założenia

Możemy to założyć n >= k > 0.

Galaretka , 26 25 bajtów

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

Pełny program, który wyświetla reprezentację listy list, z których każda jest częścią, np. Dla 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]]]

Uwaga: zastosowana reprezentacja usuwa zbędne [ i ] wokół list długości 1.

Wypróbuj online! lub zobacz ładną wersję do wydruku (koszt 3 bajtów)

W jaki sposób?

œ&µ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 œċ)

MATLAB, 272 bajty

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;

Wynik:

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

Dwie puste linie między różnymi częściami.

Nie golfowany:

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;

Wyjaśnienie:

Najpierw znajdujemy wszystkie multisety z brutalną siłą:

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

repmat(0:n-1, 1, k)powtarza wektor wartości od 0do n-1 kczasu.

nchoosek(x, k) zwraca macierz zawierającą wszystkie kombinacje k powtórzonego wektora.

sort(x, 2) sortuje wszystkie kombinacje k, a następnie unique(x, 'rows') usuwa wszystkie duplikaty.

p=zeros(0,k);tworzy pustą macierz z kkolumnami. Użyjemy go jako stosu. Przy każdej iteracji najbardziej zewnętrznej forpętli najpierw dodajemy bieżący multiset do wspomnianego stosu:p=[p;l(i,:)]; .

Następnie sprawdzamy, czy przecięcie wszystkich multiset w stosie jest co najmniej k-1długie za pomocą następującego kodu (nie możemy użyć intersectpolecenia MATLAB do sprawdzenia przecięć, ponieważ zwraca zestaw, ale potrzebujemy multisetu):

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;

Teraz, jeśli skrzyżowanie jest wystarczająco długie a == 0, w przeciwnym raziea == 1 .

Jeśli przecięcie nie jest wystarczająco długie, wypisujemy nowy wiersz i opróżniamy stos:

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

Następnie drukujemy tylko bieżący multiset:

disp(l(i,:));

MATL , 34 bajty

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

Części są oddzielone linią zawierającą białe znaki.

Wypróbuj online!

Wyjaśnienie

Uwaga: ta metoda wydaje się działać (i działa w przypadkach testowych), ale nie mam dowodu, że zawsze działa

Multisety są sortowane, zarówno wewnętrznie (tj. Każdy multiset ma nie zmniejszające się wpisy), jak i zewnętrznie (tj. Multiset M występuje przed multisetem N, jeśli M poprzedza N leksykograficznie).

Aby obliczyć przecięcie wielosetowe, posortowane multisety są ułożone jako rzędy macierzy, a kolejne różnice są obliczane wzdłuż każdej kolumny. Jeśli wszystkie kolumny oprócz co najwyżej jednej mają wszystkie różnice równe zero, multisety należą do tej samej części.

Ten test dałby wynik fałszywie ujemny w przypadku multisetów takich jak (1,2,3)i (2,3,4): nawet jeśli 2,3 są wspólne wpisy, nie będzie wykrywany jako taki, ponieważ są one w niedopasowanych kolumn.

Nie wydaje się to jednak problemem, przynajmniej w przypadkach testowych. Wygląda na to, że test między multisetami jak 1,2,3i 2,3,4nigdy tak naprawdę nie musi być wykonany, ponieważ niektóre pośrednie multisety dały wynik ujemny, a więc już są w różnych częściach. Jeśli jest to rzeczywiście prawda, powód niewątpliwie ma związek z faktem, że multisety są sortowane.

Ale nie mam na to dowodu. To po prostu wydaje się działać.

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

PHP, 245 bajtów

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);

Wypróbuj online!

Rozszerzony

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

Dane wyjściowe jako ciąg

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

n> 15 dla większej precyzji

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;
}