Greedily partition the list of combinations with repetition
Jelly, 26 25 bytes
œ&µL‘<⁴ȧ⁹ȯ
œċµç\L€=⁴œṗµḊ’
Full program which prints a representation of a list of lists, each list being a part, e.g. for 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]]]
Note: the representation used removes the redundant [ and ] around lists of length 1.
Try it online! or see a pretty print version (cost 3 bytes)
How?
œ&µ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;
Output:
>> 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
Two empty lines between different parts.
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;
Explanation:
First we find all the multisets with brute force:
l=unique(sort(nchoosek(repmat(0:n-1,1,k),k),2),'rows');
repmat(0:n-1, 1, k) repeats the vector of values from 0 to n-1 k times.
nchoosek(x, k) returns a matrix containing all k-combinations of the repeated vector.
sort(x, 2) sorts all the k-combinations, and then unique(x, 'rows') removes all duplicates.
p=zeros(0,k); creates an empty matrix with k columns. We'll use it as a stack. On each iteration of the outernmost for loop, we first add the current multiset to said stack: p=[p;l(i,:)];.
Then we check if the intersection of all multisets in the stack is at least k-1 long with the following code (we can't use MATLAB's intersect command to check for the intersections, because it returns a set, but we need a 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;
Now, if the intersection is long enough, a == 0, otherwise a == 1.
If the intersection isn't long enough, we print a newline and empty the stack:
if(a)
fprintf('\n');
p=l(i,:); % Only the current multiset will be left in the stack.
end;
Then we just print the current multiset:
disp(l(i,:));
MATL, 34 bytes
vi:qiZ^!S!Xu!"@!&vt1&dXasq?0&Y)0cb
Parts are separated by a line containing whitespace.
Try it online!
Explanation
Disclaimer: this method seems to work (and it does in the test cases), but I don't have a proof that it always does
Multisets are sorted, both internally (i.e. each multiset has non-decreasing entries) and externally (i.e. multiset M comes before multiset N if M precedes N lexicographically).
To compute the multiset intersection, the sorted multisets are arranged as rows of a matrix and consecutive differences are computed along each column. If all columns except at most one have all differences equal to zero, the multisets belong to the same part.
This test would give a false negative result for multisets like (1,2,3) and (2,3,4): even if 2, 3 are common entries, they would not be detected as such because they are in non-matching columns.
However, this doesn't seem to be a problem, at least in the test cases. It appears that a test between multisets like 1,2,3 and 2,3,4 never actually has to be done, because some intermediate multiset gave a negative result and so they already are in different parts. If this is indeed true, the reason no doubt has to do with the fact that the multisets are sorted.
I don't have a proof of this, though. It just seems to work.
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