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

さて、私がこの答えから得た小さな拡張から始めましょう、

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 に答える
1

(が 0 の場合もある)kのそのようなサブセットがあります。decListk

一様確率でそれぞれを選択したいと仮定すると、1/k基本的に次のことを行う必要があると思います。

  1. 一致するすべてのサブセットを反復します
  2. 一つ選択してください

ステップ 1 は大きなタスクになる可能性があります。固定サブセット サイズの「サブセット和問題」を解決するさまざまな方法を調べ、それらを適応させて各ソリューションを順番に生成することができます。

ステップ 2 は、すべてのソリューションのリストを作成して 1 つを選択するか、または (メモリが多すぎる場合) 巧妙なストリーミング ランダム選択アルゴリズムを使用して実行できます。

データにそのようなサブセットが多数含まれる可能性が高い場合、それらすべてを生成するのは非常に遅くなる可能性があります。その場合、一度にそれらのグループを識別しようとするかもしれません。メンバーを 1 つずつ訪問せずにグループのサイズを知る必要があります。次に、そのサイズによって重み付けされた使用するグループを選択できます。そのグループの 1 つをランダムに選択する問題を減らしました。

一様確率で選択する必要がない場合、問題はより簡単になる可能性があります。最良の場合、分布をまったく気にしない場合は、最初に見つけたサブセット和解を返すことができます。それを「ランダムに」と呼ぶかどうかは別の問題です...

于 2012-10-12T08:51:30.467 に答える