一种多样化排序算法

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;
    }
}

Answer 1

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

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

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)) 

试试这个例子：

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)空间复杂度，因为它需要两类和两个副本的列表。