Zunächst einige Definitionen:

• Gegeben nund kbetrachten Sie die sortierte Liste der Multisets , wobei wir für jedes Multiset kZahlen {0, 1, ..., n-1}mit Wiederholungen auswählen .

Zum Beispiel für n=5und k=3haben wir:

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

• Ein Teil ist eine Liste von Multisets mit der Eigenschaft, dass die Größe des Schnittpunkts aller Multisets im Teil mindestens beträgt k-1. Das heißt, wir nehmen alle Multisets und schneiden sie (unter Verwendung der Multiset-Schnittmenge) auf einmal. Als Beispiel [(1, 2, 2), (1, 2, 3), (1, 2, 4)]ist ein Teil, da sein Schnittpunkt die Größe 2 hat, aber [(1, 1, 3),(1, 2, 3),(1, 2, 4)]nicht, weil sein Schnittpunkt die Größe 1 hat.

Aufgabe

Ihr Code sollte zwei Argumente nund k. Es sollte dann diese Multisets gierig in sortierter Reihenfolge durchgehen und die Teile der Liste ausgeben. Für den Fall n=5, k=3lautet die richtige Partitionierung:

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

Hier ist ein weiteres Beispiel für 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)

Klarstellung, was gierig bedeutet: Für jedes Multiset prüfen wir wiederum, ob es dem vorhandenen Teil hinzugefügt werden kann. Wenn es geht, fügen wir es hinzu. Wenn es nicht geht, beginnen wir ein neues Teil. Wir betrachten die Multisets in sortierter Reihenfolge wie im obigen Beispiel.

Ausgabe

Sie können die Partitionierung in einem beliebigen Format ausgeben. Multisets sollten jedoch horizontal in eine Zeile geschrieben werden. Das heißt, ein einzelnes Multiset sollte nicht vertikal geschrieben oder über mehrere Zeilen verteilt werden. Sie können auswählen, wie Sie die Darstellung von Teilen in der Ausgabe trennen möchten.

Annahmen

Das können wir annehmen n >= k > 0.

Gelee , 26 25 Bytes

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

Vollständiges Programm, das eine Darstellung einer Liste von Listen druckt, wobei jede Liste ein Teil ist, z. B. für 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]]]

Hinweis: Die verwendete Darstellung entfernt die redundanten [ und ] um Listen der Länge 1.

Probieren Sie es online aus! oder sehen Sie eine hübsche Druckversion (kostet 3 Bytes)

Wie?

œ&µ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 Bytes

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;

Ausgabe:

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

Zwei leere Zeilen zwischen verschiedenen Teilen.

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;

Erläuterung:

Zuerst finden wir alle Multisets mit roher Gewalt:

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

repmat(0:n-1, 1, k)wiederholt den Vektor der Werte von 0bis zu n-1 kZeiten.

nchoosek(x, k) gibt eine Matrix zurück, die alle k-Kombinationen des wiederholten Vektors enthält.

sort(x, 2)sortiert alle k-Kombinationen und unique(x, 'rows')entfernt dann alle Duplikate.

p=zeros(0,k);Erstellt eine leere Matrix mit kSpalten. Wir werden es als Stapel verwenden. Bei jeder Iteration der äußersten forSchleife fügen wir zuerst das aktuelle Multiset zu diesem Stapel hinzu : p=[p;l(i,:)];.

Dann prüfen wir k-1mit dem folgenden Code , ob der Schnittpunkt aller Multisets im Stapel mindestens lang ist (wir können den intersectBefehl MATLAB nicht verwenden , um nach den Schnittpunkten zu suchen, da er eine Menge zurückgibt, aber wir benötigen einen Multiset):

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;

Nun, wenn die Kreuzung a == 0sonst lang genug ist a == 1.

Wenn die Kreuzung nicht lang genug ist, drucken wir eine neue Zeile und leeren den Stapel:

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

Dann drucken wir einfach das aktuelle Multiset:

disp(l(i,:));

MATL , 34 Bytes

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

Teile werden durch eine Zeile mit Leerzeichen getrennt.

Probieren Sie es online aus!

Erläuterung

Haftungsausschluss: Diese Methode scheint zu funktionieren (und in den Testfällen auch), aber ich habe keinen Beweis dafür, dass dies immer der Fall ist

Multisets werden sowohl intern (dh jedes Multiset hat nicht abnehmende Einträge) als auch extern (dh Multiset M steht vor Multiset N, wenn M lexikographisch vor N steht ) sortiert .

Um den Multiset-Schnittpunkt zu berechnen, werden die sortierten Multisets als Zeilen einer Matrix angeordnet und aufeinanderfolgende Differenzen werden entlang jeder Spalte berechnet. Wenn alle Spalten außer höchstens einer alle Differenzen gleich Null haben, gehören die Multisets zum selben Teil.

Dieser Test würde ein falsches negatives Ergebnis für Multimengen geben , wie (1,2,3)und (2,3,4): selbst wenn 2, 3sind gemeinsame Einträge, würden sie nicht als solche erkannt werden , weil sie in nicht passenden Spalten sind.

Dies scheint jedoch zumindest in den Testfällen kein Problem zu sein. Es scheint, dass ein Test zwischen Multisets wie 1,2,3und 2,3,4nie wirklich durchgeführt werden muss, da einige Zwischen-Multisets ein negatives Ergebnis lieferten und sich daher bereits in verschiedenen Teilen befinden. Wenn dies tatsächlich zutrifft, hat der Grund zweifellos damit zu tun, dass die Multisets sortiert sind.

Ich habe jedoch keinen Beweis dafür. Es scheint einfach zu funktionieren.

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 Bytes

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

Probieren Sie es online aus!

Erweitert

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

Ausgabe als String

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

n> 15 für mehr Präzision

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