一个多元化排序的算法

Question

我正在寻找实现多样化排序的方法。每个单元格都包含一个权重值和一个枚举类型。我希望根据已选择的元素类型动态调整权重值，优先考虑到目前为止“较少选择”的类型。我想控制多样性因素，这样当设置一个高值时，它会产生完全多样化的结果数组，而当给出一个低值时，它将提供一个几乎“常规”排序的数组。

由于这不像是一个非常具体的用例，所以如果有任何已知算法的参考，那也将是很好的。

更新： 根据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;
    }
}

- Noam

---

请问您能否添加一个示例，展示排序前后的样子？ - Mysterion

@Mysterion 这不是一个真正的示例数组，但为实现添加了一个基础。有帮助吗？ - Noam

Answer 1

您的定义是非常通用的术语，而不是数学术语，因此我怀疑您是否能找到与您所需完全匹配的解决方案。 我可以提出这种简单的方法：

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

- Ophir Gvirtzer

---

你的实现中有几个错误。 - Ophir Gvirtzer

我只是试图将你的话转化为伪代码，以确保我们理解彼此，如果这是“打字错误”，请忽略。我是否误解了你提出的方法？ - Noam

抱歉，上一条评论发送不完整。伪代码存在问题：您没有删除所选项目，并且没有计算每种类型的挨饿步数，即自选择该类型以来经过了多少轮。回答您的问题：SelectBest()将选择具有最高val*stravation_fact的那个，其中挨饿因素例如为(1+diversifyFactor)^number_of_starvation_steps。 - Ophir Gvirtzer

不。您可以拥有一个由类型索引的数组starvation_count，当您选择类型t时，将所有计数增加一，并且starvation_count[t]=0。 - Ophir Gvirtzer

哦，现在我明白了。你能解释一下使用val *（1 + diversifyFactor）^number_of_starvation_steps [$type]的数学原理吗？此外，diversifyFactor应该是[0,1]吗？ - Noam

Answer 2

这是一个想法：

class item(object):
    def __init__(self, enum_type, weight):
        self.enum_type = enum_type
        self.weight = weight
        self.dyn_weight = weight

    def __repr__(self):
        return unicode((self.enum_type, self.weight, self.dyn_weight))


def sort_diverse(lst, factor):
    # first sort
    by_type = sorted(lst, key=lambda obj: (obj.enum_type, obj.weight))
    cnt = 1
    for i in xrange(1, len(lst)):
        current = by_type[i]
        previous = by_type[i-1]
        if current.enum_type == previous.enum_type:
            current.dyn_weight += factor * cnt
            cnt += 1
        else:
            cnt = 1
    return sorted(by_type, key=lambda obj: (obj.dyn_weight, obj.enum_type)) 

Try this example:

lst = [item('a', 0) for x in xrange(10)] + [item('b', 1) for x in xrange(10)] + [item('c', 2) for x in xrange(10)]
print sort_diverse(lst, 0) # regular sort
print sort_diverse(lst, 1) # partially diversified
print sort_diverse(lst, 100) # completely diversified

根据您的需求，您可能需要使用更复杂的权重更新函数。

该算法基本上是O（nlogn）时间复杂度和O（n）空间复杂度，因为它需要两次排序和两个列表的副本。

- Samy Arous