多样化排序的算法(Algorithm for a diversified sort)

多样化排序的算法(Algorithm for a diversified sort)

我正在寻找一种实现多样化排序的方法。 每个单元格包含权重值和枚举类型。 我想以一种方式对它进行排序，它将根据已经选择的元素类型使权重值动态变化，优先考虑那些“选择较少”的元素。 我想控制多样性因子，这样当它设置为高值时，它将产生一个完全不同的结果数组，当给出一个低值时，它将提供一个几乎“常规”的排序数组。

这听起来不是一个非常具体的用例，所以如果有任何对已知算法的引用，那也会很棒。

更新：根据Ophir的建议，这可能是一个基本的包装器：

// these will be the three arrays, one per type $contentTypeA, $contentTypeB, $contentTypeC; // sort each by value sort($contentTypeA); sort($contentTypeB); sort($contentTypeC); // while i didn't get the amount I want or there aren't any more options to chose from while ($amountChosen < 100 && (count($contentTypeA) + count($contentTypeB) + count($contentTypeC) > 0)) { $diversifiedContent[] = selectBest($bestA, $bestB, $bestC, &$contentTypeA, &$contentTypeB, &$contentTypeC); $amountChosen++; } $diversifiedContent = array_slice($diversifiedContent, 0, 520); return $diversifiedContent; } function selectBest($bestA, $bestB, $bestC, &$contentTypeA, &$contentTypeB, &$contentTypeC) { static $typeSelected; $diversifyFactor = 0.5; if (?) { $typeSelected['A']++; array_shift($contentTypeA); return $bestA; } else if (?) { $typeSelected['B']++; array_shift($contentTypeB); return $bestA; } else if (?) { $typeSelected['C']++; array_shift($contentTypeC); return $bestA; } }

I'm looking for a way to implement a diversified sort. Each cell contains a weight value along with an enum type. I would like to sort it in a way that it will make the weight value dynamic according to the types of elements that were already chosen, giving priority to those 'less chosen' so far. I would like to control the diversity factor, so that when setting it with a high value, it'll produce a fully diverse results array, and when giving a low value it will provide an almost 'regular' sorted array.

This doesn't sound like a very specific use case, so if there are any references to known algorithms, that will also be great.

Update: According to Ophir suggestion, this might be a basic wrapper:

// these will be the three arrays, one per type $contentTypeA, $contentTypeB, $contentTypeC; // sort each by value sort($contentTypeA); sort($contentTypeB); sort($contentTypeC); // while i didn't get the amount I want or there aren't any more options to chose from while ($amountChosen < 100 && (count($contentTypeA) + count($contentTypeB) + count($contentTypeC) > 0)) { $diversifiedContent[] = selectBest($bestA, $bestB, $bestC, &$contentTypeA, &$contentTypeB, &$contentTypeC); $amountChosen++; } $diversifiedContent = array_slice($diversifiedContent, 0, 520); return $diversifiedContent; } function selectBest($bestA, $bestB, $bestC, &$contentTypeA, &$contentTypeB, &$contentTypeC) { static $typeSelected; $diversifyFactor = 0.5; if (?) { $typeSelected['A']++; array_shift($contentTypeA); return $bestA; } else if (?) { $typeSelected['B']++; array_shift($contentTypeB); return $bestA; } else if (?) { $typeSelected['C']++; array_shift($contentTypeC); return $bestA; } }

最满意答案

你的定义是非常笼统的术语，而不是数学术语，所以我怀疑你是否能找到一个与你想要的完全匹配的紧密解决方案。 我可以建议这个简单的方法：

分别对每种类型排序。 然后通过迭代地获取最高优先级列表中的最大值来合并列表，其中优先级是值的乘积和该类型的“饥饿”因子。 饥饿因子将是忽略该类型的步数和多样性因子的组合。 此功能的确切形状取决于您的应用。

Your definition is very general terms, not in mathematical terms, so I doubt if you can find a close solution that matches exactly what you want. I can suggest this simple approach:

Sort each type separately. Then merge the lists by iteratively taking the maximum value in the list of highest priority, where priority is the product of the value and a "starvation" factor for that type. The starvation factor will be a combination of how many steps ignored that type, and the diversity factor. The exact shape of this function depends on your application.