0

我有许多科目，每个科目都有一个分数。我想将这些科目分配到一些（大致）大小相同的组中，这样得到的组都具有（大致）相等的平均分数。从概念上讲，最聪明的方法是什么？我将在 MATLAB 中实现代码。

我的第一个解决方案是根据分数对科目进行排序。然后我通过交替的组将主题分配到组中，就像发牌者向许多玩家发牌一样。这工作得很好，但我想知道是否有更好的方法。

n = 200; %number of subjects
k = 5; %number of desired groups
subjects = linspace(1,n,n)'; %subject ids
scores = randi(100,n,1); %scores
data = [subjects,scores];
data = sortrows(data,-2);
group_subjects = cell(1,k);
group_scores = cell(1,k);
x=1;
for i = 1:n
   if x>k, x=1; end
   group_subjects{x} = [group_subjects{x},data(i,1)];
   group_scores{x} = [group_scores{x},data(i,2)];
   x = x+1;
end
avg_scores = cellfun(@mean,group_scores)

我的最终目标是按组输出主题，如group_subjects.

4

1 回答 1

0

我建议将您所拥有的内容保留为“起始”分区。

一旦有了这样的起始分区，我建议采用具有最大和最小平均值的分区，并通过某种规则在它们之间交换成员，以使平均值更接近全局平均值。如果在循环中重复该操作，直到找不到合适的成员对来切换当前具有最大和最小分区的分区（即每次交换后选择最大和最小的分区），您应该至少留下一个局部最优值。

那么如何选择合适的一对数字进行交换呢？好吧，您正在寻找这样的数字，以使它们与所需的总和变化之间的差异最小化以使它们的平均值相等，并增加了限制，即它们不应导致平均值过度补偿并最终导致它们进一步分开。

while 1
 sm_idx=find(avg_scores==min(avg_scores),1); %Choose a set with the smallest average
 lg_idx=find(avg_scores==max(avg_scores),1); %Same with largest average
 pcorr=round((avg_scores(lg_idx)-avg_scores(sm_idx))*...
  (length(group_scores{lg_idx})*length(group_scores{sm_idx}))/...
  (length(group_scores{lg_idx})+length(group_scores{sm_idx}))); %Calculate perfect correction
 M = group_scores{lg_idx}'*ones(size(group_scores{sm_idx}))-...
  ones(size(group_scores{lg_idx}'))*group_scores{sm_idx}; %note: assumes group_scores are row vectors
 Midx=find(abs(M-pcorr)==min(abs(M-pcorr)(:)),1);
 if (abs(M(Midx)-pcorr)>=pcorr)
     break;
 end
 [l_c_idx,s_c_idx] = ind2sub(size(M),Midx);
 temp=group_scores{lg_idx}(l_c_idx);
 group_scores{lg_idx}(l_c_idx)=group_scores{sm_idx}(s_c_idx);
 group_scores{sm_idx}(s_c_idx)=temp;
 temp=group_subjects{lg_idx}(l_c_idx);
 group_subjects{lg_idx}(l_c_idx)=group_subjects{sm_idx}(s_c_idx);
 group_subjects{sm_idx}(s_c_idx)=temp;
 avg_scores(lg_idx)=avg_scores(lg_idx)-M(Midx)/length(group_scores{lg_idx});
 avg_scores(sm_idx)=avg_scores(sm_idx)+M(Midx)/length(group_scores{sm_idx});
end

作为代码的后续测试，我得到如下结果：

在我的循环之前：

avg_scores =
 54.000
 53.525
 53.050
 52.500
 51.925

在我的循环之后：

avg_scores =
 53.000
 53.000
 53.000
 53.000
 53.000

如您所见，它有时会得到完美的结果。

对代码的一个小小的好奇是，它总是更喜欢产生结果的第一个匹配项，正如所写的那样。为了增加一点随机性以使找到最佳解决方案的可能性更大，您可以替换

Midx=find(abs(M-pcorr)==min(abs(M-pcorr)(:)),1);

和

Midx_options=find(abs(M-pcorr)==min(abs(M-pcorr)(:)));
Midx=Midx(randi(length(Midx)));

这将使它从一组最佳开关中随机选择一个最佳开关。

于 2013-03-22T01:29:30.200 回答