根据受欢迎程度选择项目：避免美化排序

Question

我有一个网站，用户可以在其中发布建议并对建议进行投票。在起始页面上，我最初列出了 10 个建议，标头每 7 秒获取一个新的随机建议。

我希望投票能够影响建议出现的概率，无论是在 10 条建议列表中还是在标题建议中。为此，我有一个小算法来计算受欢迎程度，考虑到选票、年龄和其他一些因素（需要大量调整）。

不管怎样，运行算法后，我有一个建议和流行度指数的字典，按流行度排序：

{ S = Suggestion1, P = 0.86  }
{ S = Suggestion2, P = 0.643 }
{ S = Suggestion3, P = 0.134 }
{ S = Suggestion4, P = 0.07  }
{ S = Suggestion5, P = 0.0   }
{ . . .}

我不希望这是一种美化的排序，所以我想在选择过程中引入一些随机元素。

简而言之，我希望流行度是从列表中选择建议的概率。

有了完整的建议/受欢迎程度列表，我该如何根据概率选出 10 个呢？如何将相同的内容应用于循环标题建议？

Answer 1

恐怕我不知道如何快速执行此操作，但如果内存中有集合，您可以这样做：

请注意，您不需要对列表进行排序即可使该算法发挥作用。

1. 首先对所有概率求和（如果概率与流行度相关，则只需对流行度数字求和，我假设较高的值意味着较高的概率）
2. 计算 0 到但不包括该总和范围内的随机数
3. 从一端开始列表并迭代它
4. 对于每个元素，如果生成的随机数小于流行度，则选择该元素
5. 如果不是，则从随机数中减去该元素的流行度，然后继续下一个

如果列表是静态的，您可以构建范围并进行一些二进制搜索，但如果列表不断变化，那么我不知道更好的方法。

这是一个示例 LINQPad 程序，演示：

void Main()
{
    var list = Enumerable.Range(1, 9)
        .Select(i => new { V = i, P = i })
        .ToArray();
    list.Dump("list");

    var sum =
        (from element in list
         select element.P).Sum();

    Dictionary<int, int> selected = new Dictionary<int, int>();
    foreach (var value in Enumerable.Range(0, sum))
    {
        var temp = value;
        var v = 0;
        foreach (var element in list)
        {
            if (temp < element.P)
            {
                v = element.V;
                break;
            }

            temp -= element.P;
        }
        Debug.Assert(v > 0);
        if (!selected.ContainsKey(v))
            selected[v] = 1;
        else
            selected[v] += 1;
    }

    selected.Dump("how many times was each value selected?");
}

输出：

list 
[] (9 items)  
 V  P
 1  1 
 2  2 
 3  3 
 4  4 
 5  5 
 6  6 
 7  7 
 8  8 
 9  9 
45 45  <-- sum

how many times was each value selected? 
Dictionary<Int32,Int32> (9 items)  
Key Value
 1    1 
 2    2 
 3    3 
 4    4 
 5    5 
 6    6 
 7    7 
 8    8 
 9    9 
     45 <-- again, sum