Chciwie podziel listę kombinacji z powtórzeniami

10

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.

Jonathan Allan
źródło
@LuisMendo Właśnie popełniłem błąd. Miałem na myśli, że multisety powinny być zapisane poziomo w jednym wierszu.
Dlaczego w pierwszym przypadku testowym jest (0, 4, 4)sam? Biorąc pod uwagę twój opis, sądzę, że będzie to jego „część” (0, 4, 4), (1, 4, 4), (2, 4, 4), (3, 4, 4), (4, 4, 4). Podobnie (0, 0, 3, 3)w drugim przypadku testowym.
Greg Martin
@GregMartin Ze względu na chciwość metody. Masz rację, że ogólnie będzie on nieoptymalny. Minimalna liczba części, które można uzyskać za pomocą chciwej metody, jest interesującym, choć trudnym pytaniem,
Och, masz na myśli dosłownie, że kiedy następny termin nie pasuje do części „aktywnej”, wówczas ta część jest zamknięta na zawsze. Ok.
Greg Martin

Odpowiedzi:

4

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 œċ)
Jonathan Allan
źródło
To jest świetne. Dziękuję Ci.
3

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,:));
Steadybox
źródło
Wygląda na to, że go złamałeś! Czy możesz wyjaśnić swoją metodę?
@Lembik Dodałem wyjaśnienie.
Steadybox 16.04.17
3

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
Luis Mendo
źródło
To bardzo imponujące.
Próbuję zrozumieć, czy opisana metoda zawsze będzie działać. Widzę, że w n=k=4przypadku, gdy zaczynamy od nowej części (0, 0, 3, 3), wektoryzowana kolejna różnica tego i poprzedniego zestawu wielu elementów (0, 0, 2, 3)ma tylko jedną różnicę, więc w jaki sposób „jak dotąd część” sprawia, że ​​to działa? (lub równoważnie jaki był wynik z poprzedniego kroku, który został zastosowany zamiast (0, 0, 2, 3)?)
Jonathan Allan
Ach, widzę, że robisz kolejną różnicę. Tak, to zawsze powinno działać! Dosłownie szukasz punktów, w których zmienia się więcej niż jeden element, ale zamiast skrzyżowania z wieloma zestawami, po prostu wektoryzowane skrzyżowanie - które zadziała, ponieważ zestawy mutli są sortowane na początek.
Jonathan Allan
@JonathanAllan Tak, to kolejna różnica, a nie skrzyżowanie. Nadal nie widzę jasno, że zawsze będzie działać, ale jeśli tak mówisz ... :-)
Luis Mendo
1

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;
}
Jörg Hülsermann
źródło
To wydaje się działać! Ale co rozumiesz przez większą precyzję?
@Lembik krótka wersja daje z powrotem 0do (16**16-1)%16i wersja długa praca tylko z precyzją, która jest potrzebna do n>15 bcmod(bcsub(bcpow(16,16),1),16)jest 15 php.net/manual/en/ref.bc.php
Jörg Hülsermann