My comment to John made me realise what an efficient way to go about it would be. The crux of the problem is creating the unique permutations of repelem(1:numberofsets, setsize) or finding unique permutations of a set with repetition. I'm sure that there's something to do that already on the file exchange but I can't find it.
I've left my original answer below, but don't use it. This is much faster and more efficient. Note that the code for finding unique permutations is heavily inspired by this post. First the helper function that generates the unique permutations function partitions = uniquesets(setcount, setlength)
lefttoplace = setcount * setlength;
partitions = zeros(lefttoplace, 1);
nperms = 1;
for subset = 1:setcount
locs = nchoosek(1:lefttoplace, setlength).';
[emptyrows, ~] = find(~partitions);
emptyrows = reshape(emptyrows, [], nperms);
destrows = emptyrows(locs, :);
nperms = nperms * size(locs, 2);
destcols = repelem((1:nperms)', setlength);
partitions = repelem(partitions, 1, size(locs, 2)) + accumarray([destrows(:), destcols], subset);
lefttoplace = lefttoplace - setlength;
end
end
Then the code to use it:
P = [4.5; 4.5; 5.25; 5.25; 2.25; 0.6; 0.5; 0.6; 0.5; 0.3; 1; 2; 0.5; 0.5];
phase = 3;
P = [P; zeros(mod(-numel(P), phase), 1)];
partitions = uniquesets(phase, numel(P)/phase);
[~, order] = sort(partitions, 1);
allmatrices = reshape(P(order), numel(P)/phase , phase, []);
colsum = sum(allmatrices, 1);
distance = sum(abs(colsum - sum(P)/3), 2);
[minsum, whichmatrix] = min(distance)
chosenmatrix = allmatrices(:, :, whichmatrix)
mincolsum = colsum(1, :, whichmatrix)
This is very quick, about half a second on my machine and will work for much longer P.
It still does create a few duplicate matrices as duplicate numbers in P are still considered distinct for the purpose of partitioning. However, it does not creat unecessary partitions.
-------
Original answer, which wasn't efficient at all
Bearing in mind this is not my domain at all (this is a problem for John), here is a solution that works for this problem size but is probably very inefficient.
It uses this fileexchange entry to find all partitions of size 3 of your P vector. This is very inefficient since of these, you only want the partitions where each subset has size 5. Still, it's better than computing all permutations. In addition, duplicate numbers are considered distinct for the partitioning problem, again giving you more partitions than necessary: P = [4.5; 4.5; 5.25; 5.25; 2.25; 0.6; 0.5; 0.6; 0.5; 0.3; 1; 2; 0.5; 0.5];
parts = partitions([P;zeros(mod(-numel(P), 3), 1)], 3);
parts = parts(cellfun(@(c) all(cellfun('length', c) == 5), parts));
allmatrices = cellfun(@(c) [c{:}], parts, 'UniformOutput', false);
allmatrices = cat(3, allmatrices{:});
[minsum, which] = min(sum(abs(sum(allmatrices, 1) - sum(P)/3), 2))
selectedmatrix = allmatrices(:, :, which)
columnsum = sum(selectedmatrix, 1)
columneps = columnsum - sum(P)/3
minsum =
0.76667
which =
29036
selectedmatrix =
4.5 5.25 5.25
4.5 2.25 1
0.5 0.6 2
0.3 0.6 0.5
0 0.5 0.5
columnsum =
9.8 9.2 9.25
columneps =
0.38333 -0.21667 -0.16667
Best Answer