さて、私がこの答えから得た小さな拡張から始めましょう、
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;
}
合計が目標を超えなければならない特定の時点で、最初のリストを並べ替えて、組み合わせの反復をやめることができると思います。いくつかの検討の後、その点を特定することは簡単ではなく、チェックのコストは利益を超える可能性があります。この利点は、ターゲット値とセットの平均のいくつかの関数に対してバランスをとる必要があります。
さらに最適化は可能だと思いますが、この作業はすでに完了しているので、適切な場所で調べる必要があります。