代码之家 › 专栏 › 技术社区 › cbp

随机排列等元素的比较法

sorting random comparison language-agnostic algorithm

cbp · 技术社区 · 16 年前

这是一个难题。

我想改变下面的比较方法,这样当两个项目被认为是相等的时候,它们将被随机洗牌。

myList.Sort( (x, y) => x.Score.CompareTo(y.Score) );

我可以想象,如果您不想在搜索结果相同的情况下,优先选择一个结果而不是另一个结果,那么在排序搜索结果时,这个场景会很有用。

有人想试试吗?

这是我第一次尝试解决问题,但没用。我会告诉你原因。

class RandomizeWhenEqualComparer<T> : IComparer<T>
{
    private readonly Func<T, T, int> _comparer;

    public int Compare(T x, T y)
    {
            if (x.Equals(y)) return 0;

        int result = _comparer(x, y);

        if (result != 0) return result;

        double random = StaticRandom.NextDouble();
        return (random < .5) ? -1 : 1;
    }

    public RandomizeWhenEqualComparer(Func<T, T, int> comparer)
    {
        _comparer = comparer;
    }
}

4 回复 | 直到 16 年前

Geerad 16 年前

正如夏普图思所说,您可以存储每次比较的结果,然后再次查看它们。

但这并不有趣,而且它增加了时间复杂性和空间复杂性,因为您必须存储以前的比较,并在每次进行比较时搜索它们。

所以我要做的是: 在搜索开始时,随机获得一个种子。然后编写一个基于t和种子创建哈希的函数。

public int Hash(T a, int s)
{
    // e.g.
    return Random( a.Name().ToInt() + s ).NextDouble();
}

public int Compare(T x, T y, int s)
{
    if (x.Equals(y)) return 0;

    int result = _comparer(x, y);

    if (result != 0) return result;

    return (Hash(x, s) < Hash(y, s) ) ? -1 : 1;
}

这在给定的排序中是稳定的,但不需要查找表。