2

假设我有 1000 个左右唯一小数的排序列表，按值排列。

List<decimal> decList

如何从总计为 y 的唯一小数列表中获得随机 x 个小数？

private List<decimal> getWinningValues(int xNumberToGet, decimal yTotalValue)
{

}

有什么办法可以避免处理时间过长吗？到目前为止，我的想法是从池中获取 xNumberToGet 随机数。类似的东西（从列表中随机选择的很酷的方法）

foreach (decimal d in decList.OrderBy(x => randomInstance.Next())Take(xNumberToGet))
{

}

然后我可能会检查这些总数，如果总数更少，我可能会慢慢地将数字向上移动（到下一个可用数字）。如果总数更多，我可能会将数字向下移动。我现在仍然确定如何实施，或者是否有更好的设计可用。任何帮助将非常感激。

4

2 回答 2

1

(可能是 0)有k这样的子集。decListk

假设您要以统一的概率选择每个1/k，我认为您基本上需要执行以下操作：

  1. 遍历所有匹配的子集
  2. 选择一个

第 1 步可能是一项艰巨的任务，您可以研究解决固定子集大小的“子集和问题”的各种方法，并调整它们以依次生成每个解决方案。

步骤 2 可以通过列出所有解决方案并选择一个来完成，或者（如果这可能占用太多内存）通过使用聪明的流式随机选择算法来完成。

如果您的数据可能有很多这样的子集，那么生成它们可能会非常慢。在这种情况下，您可能会尝试一次识别它们的组。您必须在不逐一访问其成员的情况下知道该组的大小，然后您可以根据其大小选择使用哪个组，然后您将问题减少到随机选择该组中的一个。

如果您不需要以均匀概率进行选择，那么问题可能会变得更容易。在最好的情况下，如果你根本不关心分布，那么你可以返回你找到的第一个子集和解决方案——你是否称之为“随机”是另一回事......

于 2012-10-12T08:51:30.467 回答
1

好的，从我从这个答案中得到的一个小扩展开始，

public static IEnumerable<IEnumerable<T>> Combinations<T>(
    this IEnumerable<T> source,
    int k)
{
    if (k == 0)
    {
        return new[] { Enumerable.Empty<T>() };
    }

    return source.SelectMany((e, i) =>
        source.Skip(i + 1).Combinations(k - 1)
            .Select(c => (new[] { e }).Concat(c)));
}

这为您提供了一种非常有效的方法k，可以从给定的IEnumerable. 您可以在您的实现中充分利用这一点。

请记住，如果IEnumerable和k足够大，这可能需要一些时间，即比您拥有的时间长得多。所以，我已经修改了你的函数以采用CancellationToken.

private static IEnumerable<decimal> GetWinningValues(
    IEnumerable<decimal> allValues,
    int numberToGet, 
    decimal targetValue,
    CancellationToken canceller)
{
    IList<decimal> currentBest = null;
    var currentBestGap = decimal.MaxValue;
    var locker = new object();

    allValues.Combinations(numberToGet)
        .AsParallel()
        .WithCancellation(canceller)
        .TakeWhile(c => currentBestGap != decimal.Zero)
        .ForAll(c =>
        {
            var gap = Math.Abs(c.Sum() - targetValue);
            if (gap < currentBestGap)
            {
                lock (locker)
                {
                    currentBestGap = gap;
                    currentBest = c.ToList();
                }
            }
        }

    return currentBest;
}

我有一个想法，当总和必须超过目标时，您可以对初始列表进行排序并在某个点停止迭代组合。经过一番考虑，确定这一点并非易事，而且检查的成本可能会超过收益。这个好处必须与目标值和集合的平均值的某些函数相平衡。

我仍然认为进一步优化是可能的，但我也认为这项工作已经完成，我只需要在正确的地方查找它。

于 2012-10-15T09:41:08.423 回答