C# の List<T> から N 個のランダムな要素を選択します

https://stackoverflow.com/questions/48087

09-06-2019
|

質問

一般的なリストから 5 つのランダムな要素を選択する簡単なアルゴリズムが必要です。たとえば、から 5 つのランダムな要素を取得したいとします。 List<string>.

解決

各要素を反復処理して、選択の確率 = (必要な数)/(残りの数) を作成します。

したがって、40 個の項目がある場合、最初の項目が選択される確率は 5/40 になります。そうであれば、次は 4/39 の確率で、そうでない場合は 5/39 の確率です。最後までたどり着く頃には 5 つのアイテムが揃っており、その前にすべてのアイテムが揃っていることもよくあります。

他のヒント

linq の使用:

YourList.OrderBy(x => rnd.Next()).Take(5)

public static List<T> GetRandomElements<T>(this IEnumerable<T> list, int elementsCount)
{
    return list.OrderBy(arg => Guid.NewGuid()).Take(elementsCount).ToList();
}

これは実際には思っているよりも難しい問題です。その主な理由は、数学的に正しい解決策の多くでは、すべての可能性を実際に満たすことができないからです (これについては以下で詳しく説明します)。

まず、実装が簡単で、真の乱数ジェネレーターをお持ちの場合に適したものをいくつか示します。

(0) カイルの答えは O(n) です。

(1) n 個のペア [(0, rand), (1, rand), (2, rand), ...] のリストを生成し、それらを 2 番目の座標でソートし、最初の k を使用します (ここでは k =5) ランダムなサブセットを取得するためのインデックス。これは O(n log n) 時間かかりますが、実装は簡単だと思います。

(2) k 個のランダムな要素のインデックスになるまで成長する空のリスト s = [] を初期化します。{0, 1, 2, ..., n-1} の数値 r をランダムに選択し (r = rand % n)、これを s に加算します。次に r = rand % (n-1) を取得し、s を固定します。衝突を避けるために、s 内の要素よりも小さい # 要素を r に追加します。次に r = rand % (n-2) を取得し、同じことを行います。s に k 個の異なる要素ができるまで。これの最悪の場合の実行時間は O(k^2) です。したがって、k << n の場合、これは高速になる可能性があります。s をソートし、どの連続した間隔があるかを追跡する場合は、O(k log k) で実装できますが、手間がかかります。

@Kyle - おっしゃるとおりです。よく考えたらあなたの答えに同意します。私は最初急いでそれを読み、固定確率 k/n で各要素を順番に選択することを示していると誤解しました。それは間違いでした。しかし、あなたの適応的なアプローチは私には正しいように思えます。ごめんなさい。

さて、ここからはキッカーです:漸近的に (k が固定され、n が増加する場合)、n^k/k になります。n 個の要素から k 個の要素サブセットを選択します [これは (n が k を選択する) の近似です]。n が大きく、k がそれほど小さくない場合、これらの数は巨大になります。標準的な 32 ビット乱数発生器で期待できる最適なサイクル長は 2^32 = 256^4 です。したがって、1000 個の要素のリストがあり、ランダムに 5 個を選択したい場合、標準的な乱数ジェネレーターがすべての可能性をヒットさせることはできません。ただし、小さいセットで適切に機能し、常にランダムに「見える」選択をしても問題がない限り、これらのアルゴリズムは問題ないはずです。

補遺:これを書いた後、アイデア (2) を正しく実装するのは難しいことに気づいたので、この答えを明確にしたいと思いました。O(k log k) の時間を取得するには、O(log m) の検索と挿入をサポートする配列のような構造が必要です。バランスのとれたバイナリツリーはこれを実行できます。このような構造を使用して s という配列を構築する疑似 Python を次に示します。

# Returns a container s with k distinct random numbers from {0, 1, ..., n-1}
def ChooseRandomSubset(n, k):
  for i in range(k):
    r = UniformRandom(0, n-i)                 # May be 0, must be < n-i
    q = s.FirstIndexSuchThat( s[q] - q > r )  # This is the search.
    s.InsertInOrder(q ? r + q : r + len(s))   # Inserts right before q.
  return s

いくつかのサンプルケースを実行して、上記の英語の説明がどのように効率的に実装されるかを確認することをお勧めします。

選択された回答は正しく、かなり良い回答だと思います。ただし、結果をランダムな順序で取得したかったので、別の方法で実装しました。

    static IEnumerable<SomeType> PickSomeInRandomOrder<SomeType>(
        IEnumerable<SomeType> someTypes,
        int maxCount)
    {
        Random random = new Random(DateTime.Now.Millisecond);

        Dictionary<double, SomeType> randomSortTable = new Dictionary<double,SomeType>();

        foreach(SomeType someType in someTypes)
            randomSortTable[random.NextDouble()] = someType;

        return randomSortTable.OrderBy(KVP => KVP.Key).Take(maxCount).Select(KVP => KVP.Value);
    }

私はちょうどこの問題に遭遇し、さらにグーグルで検索したところ、リストをランダムにシャッフルするという問題にたどり着きました。 http://en.wikipedia.org/wiki/Fisher-Yates_shuffle

リストを (所定の位置で) 完全にランダムにシャッフルするには、次のようにします。

n 要素 (インデックス 0..n-1) の配列 a をシャッフルするには:

  for i from n − 1 downto 1 do
       j ← random integer with 0 ≤ j ≤ i
       exchange a[j] and a[i]

最初の 5 つの要素のみが必要な場合は、 i を n-1 から 1 まで実行するのではなく、n-5 まで実行するだけで済みます (つまり:n-5)

k 個のアイテムが必要だとします。

これは次のようになります。

  for (i = n − 1; i >= n-k; i--)
  {
       j = random integer with 0 ≤ j ≤ i
       exchange a[j] and a[i]
  }

選択された各項目は配列の終わりに向かって交換されるため、選択された k 要素は配列の最後の k 要素になります。

これには O(k) 時間がかかります。ここで、k は必要なランダムに選択された要素の数です。

さらに、初期リストを変更したくない場合は、すべてのスワップを一時リストに書き留め、そのリストを反転して再度適用することができます。これにより、逆のスワップセットが実行され、変更せずに初期リストが返されます。 O(k) 実行時間。

最後に、実際にこだわる場合は、(n == k) の場合、ランダムに選択された整数は常に 0 になるため、n-k ではなく 1 で停止する必要があります。

これを使用できますが、注文はクライアント側で行われます

 .AsEnumerable().OrderBy(n => Guid.NewGuid()).Take(5);

からアルゴリズムにおけるドラゴン, 、C# での解釈:

int k = 10; // items to select
var items = new List<int>(new[] { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12 });
var selected = new List<int>();
double needed = k;
double available = items.Count;
var rand = new Random();
while (selected.Count < k) {
   if( rand.NextDouble() < needed / available ) {
      selected.Add(items[(int)available-1])
      needed--;
   }
   available--;
}

このアルゴリズムは、項目リストの一意のインデックスを選択します。

@JohnShedletsky によるコメントについて考えていました。受け入れられた回答（言い換え）に関して：

O(originalList.Length) ではなく O(subset.Length) でこれを行うことができるはずです

基本的には生成できるはずです subset ランダムなインデックスを作成し、元のリストからそれらを抽出します。

方法

public static class EnumerableExtensions {

    public static Random randomizer = new Random(); // you'd ideally be able to replace this with whatever makes you comfortable

    public static IEnumerable<T> GetRandom<T>(this IEnumerable<T> list, int numItems) {
        return (list as T[] ?? list.ToArray()).GetRandom(numItems);

        // because ReSharper whined about duplicate enumeration...
        /*
        items.Add(list.ElementAt(randomizer.Next(list.Count()))) ) numItems--;
        */
    }

    // just because the parentheses were getting confusing
    public static IEnumerable<T> GetRandom<T>(this T[] list, int numItems) {
        var items = new HashSet<T>(); // don't want to add the same item twice; otherwise use a list
        while (numItems > 0 )
            // if we successfully added it, move on
            if( items.Add(list[randomizer.Next(list.Length)]) ) numItems--;

        return items;
    }

    // and because it's really fun; note -- you may get repetition
    public static IEnumerable<T> PluckRandomly<T>(this IEnumerable<T> list) {
        while( true )
            yield return list.ElementAt(randomizer.Next(list.Count()));
    }

}

さらに効率的にしたい場合は、おそらく HashSet の インデックス, 、実際のリスト要素ではありません (複雑な型や高価な比較がある場合に備えて)。

単体テスト

そして、衝突などが発生しないようにするためです。

[TestClass]
public class RandomizingTests : UnitTestBase {
    [TestMethod]
    public void GetRandomFromList() {
        this.testGetRandomFromList((list, num) => list.GetRandom(num));
    }

    [TestMethod]
    public void PluckRandomly() {
        this.testGetRandomFromList((list, num) => list.PluckRandomly().Take(num), requireDistinct:false);
    }

    private void testGetRandomFromList(Func<IEnumerable<int>, int, IEnumerable<int>> methodToGetRandomItems, int numToTake = 10, int repetitions = 100000, bool requireDistinct = true) {
        var items = Enumerable.Range(0, 100);
        IEnumerable<int> randomItems = null;

        while( repetitions-- > 0 ) {
            randomItems = methodToGetRandomItems(items, numToTake);
            Assert.AreEqual(numToTake, randomItems.Count(),
                            "Did not get expected number of items {0}; failed at {1} repetition--", numToTake, repetitions);
            if(requireDistinct) Assert.AreEqual(numToTake, randomItems.Distinct().Count(),
                            "Collisions (non-unique values) found, failed at {0} repetition--", repetitions);
            Assert.IsTrue(randomItems.All(o => items.Contains(o)),
                        "Some unknown values found; failed at {0} repetition--", repetitions);
        }
    }
}

Nを選択する ランダム グループのアイテムは何の関係もありません注文！ランダム性とは、予測不可能性を意味し、グループ内の位置を入れ替えることを意味するものではありません。何らかの順序付けを扱うすべての回答は、そうでない回答よりも効率が劣るはずです。ここでは効率が重要なので、項目の順序をあまり変えないものを投稿します。

1) 必要な場合真実ランダムな値は、選択する要素に制限がないことを意味します (つまり、一度選択した項目は再選択できます)。

public static List<T> GetTrueRandom<T>(this IList<T> source, int count, 
                                       bool throwArgumentOutOfRangeException = true)
{
    if (throwArgumentOutOfRangeException && count > source.Count)
        throw new ArgumentOutOfRangeException();

    var randoms = new List<T>(count);
    randoms.AddRandomly(source, count);
    return randoms;
}

例外フラグをオフに設定すると、ランダムなアイテムを何度でも選択できます。

{ 1, 2, 3, 4 } がある場合、3 つの項目に対しては { 1, 4, 4 }、{ 1, 4, 3 } などを与えることができ、さらには { 1, 4, 3, 2, 4 } を与えることができます。 5アイテム！

チェックするものが何もないので、これはかなり高速になるはずです。

2) 必要な場合個人グループのメンバーに繰り返しがない場合は、辞書に頼ることになります（多くの人がすでに指摘しているように）。

public static List<T> GetDistinctRandom<T>(this IList<T> source, int count)
{
    if (count > source.Count)
        throw new ArgumentOutOfRangeException();

    if (count == source.Count)
        return new List<T>(source);

    var sourceDict = source.ToIndexedDictionary();

    if (count > source.Count / 2)
    {
        while (sourceDict.Count > count)
            sourceDict.Remove(source.GetRandomIndex());

        return sourceDict.Select(kvp => kvp.Value).ToList();
    }

    var randomDict = new Dictionary<int, T>(count);
    while (randomDict.Count < count)
    {
        int key = source.GetRandomIndex();
        if (!randomDict.ContainsKey(key))
            randomDict.Add(key, sourceDict[key]);
    }

    return randomDict.Select(kvp => kvp.Value).ToList();
}

ここでのコードは、リストに追加するだけでなく削除も行うため、他の辞書アプローチよりも少し長くなります。つまり 2 つのループになります。ここで私がそうでないことがわかります 並べ替えた いつでも何でも count と等しくなる source.Count. 。それは私が信じているからです ランダム性は 返されたセット 全体として. 。つまり、あなたが望むなら 5 からのランダムなアイテム 1, 2, 3, 4, 5, 、それが問題ではないはずです 1, 3, 4, 2, 5 または 1, 2, 3, 4, 5, 、しかし必要な場合は 4 同じセットのアイテムの場合、予想外に結果が得られるはずです。 1, 2, 3, 4, 1, 3, 5, 2, 2, 3, 5, 4 等第二に、 返されるランダムな項目の数が元のグループの半分を超える場合、削除が容易になります。 source.Count - count グループからのアイテム 追加するよりも count アイテム。パフォーマンス上の理由から、私は使用しました source の代わりに sourceDict 削除メソッドでランダムなインデックスを取得します。

したがって、{ 1, 2, 3, 4 } がある場合、これは 3 つの項目に対して { 1, 2, 3 }、{ 3, 4, 1 } などになる可能性があります。

3) 元のグループ内の重複を考慮して、グループから真に異なるランダム値が必要な場合は、上記と同じアプローチを使用できますが、 HashSet 辞書より軽くなります。

public static List<T> GetTrueDistinctRandom<T>(this IList<T> source, int count, 
                                               bool throwArgumentOutOfRangeException = true)
{
    if (count > source.Count)
        throw new ArgumentOutOfRangeException();

    var set = new HashSet<T>(source);

    if (throwArgumentOutOfRangeException && count > set.Count)
        throw new ArgumentOutOfRangeException();

    List<T> list = hash.ToList();

    if (count >= set.Count)
        return list;

    if (count > set.Count / 2)
    {
        while (set.Count > count)
            set.Remove(list.GetRandom());

        return set.ToList();
    }

    var randoms = new HashSet<T>();
    randoms.AddRandomly(list, count);
    return randoms.ToList();
}

の randoms 変数は HashSet 最もまれなケースで重複が追加されるのを避けるため。 Random.Next 特に入力リストが小さい場合、同じ値が得られる可能性があります。

したがって、 { 1, 2, 2, 4 } => 3 つのランダムなアイテム => { 1, 2, 4 } となり、決して { 1, 2, 2} にはなりません。

{ 1, 2, 2, 4 } => ランダムなアイテム 4 つ => 例外!!または、フラグの設定に応じて { 1, 2, 4 }。

私が使用した拡張メソッドのいくつかは次のとおりです。

static Random rnd = new Random();
public static int GetRandomIndex<T>(this ICollection<T> source)
{
    return rnd.Next(source.Count);
}

public static T GetRandom<T>(this IList<T> source)
{
    return source[source.GetRandomIndex()];
}

static void AddRandomly<T>(this ICollection<T> toCol, IList<T> fromList, int count)
{
    while (toCol.Count < count)
        toCol.Add(fromList.GetRandom());
}

public static Dictionary<int, T> ToIndexedDictionary<T>(this IEnumerable<T> lst)
{
    return lst.ToIndexedDictionary(t => t);
}

public static Dictionary<int, T> ToIndexedDictionary<S, T>(this IEnumerable<S> lst, 
                                                           Func<S, T> valueSelector)
{
    int index = -1;
    return lst.ToDictionary(t => ++index, valueSelector);
}

リスト内の数十の項目を 10,000 回繰り返す必要があるパフォーマンスがすべての場合は、次のようにすることをお勧めします。より高速なランダムクラスよりも System.Random, 、しかし、後者がおそらくボトルネックになることはなく、非常に十分に速いことを考えると、それは大したことではないと思います。

編集： 返品された商品の順序を再調整する必要がある場合、これに勝るものはありませんダキムのフィッシャー・イェーツのアプローチ - 短くて甘くてシンプル。

私が使用する簡単な解決策 (おそらく大きなリストには適していません):リストを一時リストにコピーし、ループ内で一時リストから項目をランダムに選択し、一時リストから削除しながら選択済み項目リストに入れます (再選択できません)。

例：

List<Object> temp = OriginalList.ToList();
List<Object> selectedItems = new List<Object>();
Random rnd = new Random();
Object o;
int i = 0;
while (i < NumberOfSelectedItems)
{
            o = temp[rnd.Next(temp.Count)];
            selectedItems.Add(o);
            temp.Remove(o);
            i++;
 }

上記の回答のいくつかを組み合わせて、遅延評価された拡張メソッドを作成しました。私のテストでは、Kyle のアプローチ (Order(N)) は、選択するランダムなインデックスを提案するための drzaus のセットの使用 (Order(K)) よりも何倍も遅いことがわかりました。前者は、乱数ジェネレーターへの呼び出しをさらに多く実行し、さらに項目に対してより多くの回数繰り返します。

私の実装の目標は次のとおりです。

1) IList ではない IEnumerable が指定された場合、完全なリストは認識されません。膨大な項目のシーケンスが与えられた場合、メモリ不足になることは避けたいです。カイルのアプローチをオンラインソリューションに使用します。

2) それが IList であることが分かる場合は、drzaus のアプローチを少しひねって使用します。K が N の半分より大きい場合、多くのランダムなインデックスを何度も選択し、それらをスキップする必要があるため、スラッシングが発生する危険があります。したがって、保持しないインデックスのリストを作成します。

3) 私は、商品が届いたのと同じ順序で返品されることを保証します。カイルのアルゴリズムは変更する必要がありませんでした。drzaus のアルゴリズムでは、ランダムなインデックスが選択された順序でアイテムを発行しないことが必要でした。すべてのインデックスを SortedSet に収集し、ソートされたインデックス順に項目を出力します。

4) K が N に比べて大きく、セットの意味を反転した場合、すべての項目を列挙し、インデックスがセット内にないかどうかをテストします。これは、私が注文（k）の実行時間を失うことを意味しますが、これらの場合にはkはnに近いため、あまり失うことはありません。

コードは次のとおりです。

    /// <summary>
    /// Takes k elements from the next n elements at random, preserving their order.
    /// 
    /// If there are fewer than n elements in items, this may return fewer than k elements.
    /// </summary>
    /// <typeparam name="TElem">Type of element in the items collection.</typeparam>
    /// <param name="items">Items to be randomly selected.</param>
    /// <param name="k">Number of items to pick.</param>
    /// <param name="n">Total number of items to choose from.
    /// If the items collection contains more than this number, the extra members will be skipped.
    /// If the items collection contains fewer than this number, it is possible that fewer than k items will be returned.</param>
    /// <returns>Enumerable over the retained items.
    /// 
    /// See http://stackoverflow.com/questions/48087/select-a-random-n-elements-from-listt-in-c-sharp for the commentary.
    /// </returns>
    public static IEnumerable<TElem> TakeRandom<TElem>(this IEnumerable<TElem> items, int k, int n)
    {
        var r = new FastRandom();
        var itemsList = items as IList<TElem>;

        if (k >= n || (itemsList != null && k >= itemsList.Count))
            foreach (var item in items) yield return item;
        else
        {  
            // If we have a list, we can infer more information and choose a better algorithm.
            // When using an IList, this is about 7 times faster (on one benchmark)!
            if (itemsList != null && k < n/2)
            {
                // Since we have a List, we can use an algorithm suitable for Lists.
                // If there are fewer than n elements, reduce n.
                n = Math.Min(n, itemsList.Count);

                // This algorithm picks K index-values randomly and directly chooses those items to be selected.
                // If k is more than half of n, then we will spend a fair amount of time thrashing, picking
                // indices that we have already picked and having to try again.   
                var invertSet = k >= n/2;  
                var positions = invertSet ? (ISet<int>) new HashSet<int>() : (ISet<int>) new SortedSet<int>();

                var numbersNeeded = invertSet ? n - k : k;
                while (numbersNeeded > 0)
                    if (positions.Add(r.Next(0, n))) numbersNeeded--;

                if (invertSet)
                {
                    // positions contains all the indices of elements to Skip.
                    for (var itemIndex = 0; itemIndex < n; itemIndex++)
                    {
                        if (!positions.Contains(itemIndex))
                            yield return itemsList[itemIndex];
                    }
                }
                else
                {
                    // positions contains all the indices of elements to Take.
                    foreach (var itemIndex in positions)
                        yield return itemsList[itemIndex];              
                }
            }
            else
            {
                // Since we do not have a list, we will use an online algorithm.
                // This permits is to skip the rest as soon as we have enough items.
                var found = 0;
                var scanned = 0;
                foreach (var item in items)
                {
                    var rand = r.Next(0,n-scanned);
                    if (rand < k - found)
                    {
                        yield return item;
                        found++;
                    }
                    scanned++;
                    if (found >= k || scanned >= n)
                        break;
                }
            }
        }  
    }

私は特殊な乱数ジェネレーターを使用していますが、C# を使用することもできます。 ランダム あなたが望むなら。(高速ランダム Colin Green によって書かれ、SharpNEAT の一部です。周期は 2^128-1 で、多くの RNG よりも優れています)。

単体テストは次のとおりです。

[TestClass]
public class TakeRandomTests
{
    /// <summary>
    /// Ensure that when randomly choosing items from an array, all items are chosen with roughly equal probability.
    /// </summary>
    [TestMethod]
    public void TakeRandom_Array_Uniformity()
    {
        const int numTrials = 2000000;
        const int expectedCount = numTrials/20;
        var timesChosen = new int[100];
        var century = new int[100];
        for (var i = 0; i < century.Length; i++)
            century[i] = i;

        for (var trial = 0; trial < numTrials; trial++)
        {
            foreach (var i in century.TakeRandom(5, 100))
                timesChosen[i]++;
        }
        var avg = timesChosen.Average();
        var max = timesChosen.Max();
        var min = timesChosen.Min();
        var allowedDifference = expectedCount/100;
        AssertBetween(avg, expectedCount - 2, expectedCount + 2, "Average");
        //AssertBetween(min, expectedCount - allowedDifference, expectedCount, "Min");
        //AssertBetween(max, expectedCount, expectedCount + allowedDifference, "Max");

        var countInRange = timesChosen.Count(i => i >= expectedCount - allowedDifference && i <= expectedCount + allowedDifference);
        Assert.IsTrue(countInRange >= 90, String.Format("Not enough were in range: {0}", countInRange));
    }

    /// <summary>
    /// Ensure that when randomly choosing items from an IEnumerable that is not an IList, 
    /// all items are chosen with roughly equal probability.
    /// </summary>
    [TestMethod]
    public void TakeRandom_IEnumerable_Uniformity()
    {
        const int numTrials = 2000000;
        const int expectedCount = numTrials / 20;
        var timesChosen = new int[100];

        for (var trial = 0; trial < numTrials; trial++)
        {
            foreach (var i in Range(0,100).TakeRandom(5, 100))
                timesChosen[i]++;
        }
        var avg = timesChosen.Average();
        var max = timesChosen.Max();
        var min = timesChosen.Min();
        var allowedDifference = expectedCount / 100;
        var countInRange =
            timesChosen.Count(i => i >= expectedCount - allowedDifference && i <= expectedCount + allowedDifference);
        Assert.IsTrue(countInRange >= 90, String.Format("Not enough were in range: {0}", countInRange));
    }

    private IEnumerable<int> Range(int low, int count)
    {
        for (var i = low; i < low + count; i++)
            yield return i;
    }

    private static void AssertBetween(int x, int low, int high, String message)
    {
        Assert.IsTrue(x > low, String.Format("Value {0} is less than lower limit of {1}. {2}", x, low, message));
        Assert.IsTrue(x < high, String.Format("Value {0} is more than upper limit of {1}. {2}", x, high, message));
    }

    private static void AssertBetween(double x, double low, double high, String message)
    {
        Assert.IsTrue(x > low, String.Format("Value {0} is less than lower limit of {1}. {2}", x, low, message));
        Assert.IsTrue(x < high, String.Format("Value {0} is more than upper limit of {1}. {2}", x, high, message));
    }
}

ここには、以下に基づいた実装が 1 つあります。フィッシャー・イェーツ・シャッフル John Shedletsky が指摘したように、そのアルゴリズムの複雑さは O(n) です。ここで、n はリストサイズではなく、サブセットまたはサンプルサイズです。

public static IEnumerable<T> GetRandomSample<T>(this IList<T> list, int sampleSize)
{
    if (list == null) throw new ArgumentNullException("list");
    if (sampleSize > list.Count) throw new ArgumentException("sampleSize may not be greater than list count", "sampleSize");
    var indices = new Dictionary<int, int>(); int index;
    var rnd = new Random();

    for (int i = 0; i < sampleSize; i++)
    {
        int j = rnd.Next(i, list.Count);
        if (!indices.TryGetValue(j, out index)) index = j;

        yield return list[index];

        if (!indices.TryGetValue(i, out index)) index = i;
        indices[j] = index;
    }
}

カイルの答えに基づいて、私の C# 実装は次のとおりです。

/// <summary>
/// Picks random selection of available game ID's
/// </summary>
private static List<int> GetRandomGameIDs(int count)
{       
    var gameIDs = (int[])HttpContext.Current.Application["NonDeletedArcadeGameIDs"];
    var totalGameIDs = gameIDs.Count();
    if (count > totalGameIDs) count = totalGameIDs;

    var rnd = new Random();
    var leftToPick = count;
    var itemsLeft = totalGameIDs;
    var arrPickIndex = 0;
    var returnIDs = new List<int>();
    while (leftToPick > 0)
    {
        if (rnd.Next(0, itemsLeft) < leftToPick)
        {
            returnIDs .Add(gameIDs[arrPickIndex]);
            leftToPick--;
        }
        arrPickIndex++;
        itemsLeft--;
    }

    return returnIDs ;
}

この方法はカイルの方法と同等である可能性があります。

リストのサイズが n で、k 個の要素が必要だとします。

Random rand = new Random();
for(int i = 0; k>0; ++i) 
{
    int r = rand.Next(0, n-i);
    if(r<k) 
    {
        //include element i
        k--;
    }
}

魅力的に機能します:)

-アレックス・ギルバート

@ersの回答から拡張すると、OrderByの異なる実装の可能性について心配している場合、これは安全なはずです。

// Instead of this
YourList.OrderBy(x => rnd.Next()).Take(5)

// Temporarily transform 
YourList
    .Select(v => new {v, i = rnd.Next()}) // Associate a random index to each entry
    .OrderBy(x => x.i).Take(5) // Sort by (at this point fixed) random index 
    .Select(x => x.v); // Go back to enumerable of entry

最初のカットで私が思いついた最高のものはこれです:

public List<String> getRandomItemsFromList(int returnCount, List<String> list)
{
    List<String> returnList = new List<String>();
    Dictionary<int, int> randoms = new Dictionary<int, int>();

    while (randoms.Count != returnCount)
    {
        //generate new random between one and total list count
        int randomInt = new Random().Next(list.Count);

        // store this in dictionary to ensure uniqueness
        try
        {
            randoms.Add(randomInt, randomInt);
        }
        catch (ArgumentException aex)
        {
            Console.Write(aex.Message);
        } //we can assume this element exists in the dictonary already 

        //check for randoms length and then iterate through the original list 
        //adding items we select via random to the return list
        if (randoms.Count == returnCount)
        {
            foreach (int key in randoms.Keys)
                returnList.Add(list[randoms[key]]);

            break; //break out of _while_ loop
        }
    }

    return returnList;
}

1 からリストの総数までの範囲内のランダムのリストを使用し、リスト内のそれらの項目を単純に取り出すのが最良の方法のように思えますが、辞書を使用して一意性を確保することはまだ考え中です。

また、文字列リストを使用していることに注意してください。必要に応じて置き換えてください。

なぜ次のようなものではないのでしょうか:

 Dim ar As New ArrayList
    Dim numToGet As Integer = 5
    'hard code just to test
    ar.Add("12")
    ar.Add("11")
    ar.Add("10")
    ar.Add("15")
    ar.Add("16")
    ar.Add("17")

    Dim randomListOfProductIds As New ArrayList

    Dim toAdd As String = ""
    For i = 0 To numToGet - 1
        toAdd = ar(CInt((ar.Count - 1) * Rnd()))

        randomListOfProductIds.Add(toAdd)
        'remove from id list
        ar.Remove(toAdd)

    Next
'sorry i'm lazy and have to write vb at work :( and didn't feel like converting to c#

それは思っているよりもずっと難しいことです。を参照してください。素晴らしい記事「シャッフル」ジェフから。

私はこのテーマについて、C# コードを含む非常に短い記事を書きました。
指定された配列の N 要素のランダムなサブセットを返します

ゴール：収集元から重複のないN個のアイテムを選択します。汎用コレクション用の拡張機能を作成しました。私がやった方法は次のとおりです。

public static class CollectionExtension
{
    public static IList<TSource> RandomizeCollection<TSource>(this IList<TSource> source, int maxItems)
    {
        int randomCount = source.Count > maxItems ? maxItems : source.Count;
        int?[] randomizedIndices = new int?[randomCount];
        Random random = new Random();

        for (int i = 0; i < randomizedIndices.Length; i++)
        {
            int randomResult = -1;
            while (randomizedIndices.Contains((randomResult = random.Next(0, source.Count))))
            {
                //0 -> since all list starts from index 0; source.Count -> maximum number of items that can be randomize
                //continue looping while the generated random number is already in the list of randomizedIndices
            }

            randomizedIndices[i] = randomResult;
        }

        IList<TSource> result = new List<TSource>();
        foreach (int index in randomizedIndices)
            result.Add(source.ElementAt(index));

        return result;
    }
}

私は最近、次のようなアイデアを使用して自分のプロジェクトでこれを実行しましたタイラーのポイント1.
たくさんの質問をロードし、ランダムに 5 つを選択していました。並べ替えは、 I比較者.
aすべての質問は QuestionSorter リストにロードされ、その後、リストのソート機能選択された最初の k 個の要素。

    private class QuestionSorter : IComparable<QuestionSorter>
    {
        public double SortingKey
        {
            get;
            set;
        }

        public Question QuestionObject
        {
            get;
            set;
        }

        public QuestionSorter(Question q)
        {
            this.SortingKey = RandomNumberGenerator.RandomDouble;
            this.QuestionObject = q;
        }

        public int CompareTo(QuestionSorter other)
        {
            if (this.SortingKey < other.SortingKey)
            {
                return -1;
            }
            else if (this.SortingKey > other.SortingKey)
            {
                return 1;
            }
            else
            {
                return 0;
            }
        }
    }

使用法：

    List<QuestionSorter> unsortedQuestions = new List<QuestionSorter>();

    // add the questions here

    unsortedQuestions.Sort(unsortedQuestions as IComparer<QuestionSorter>);

    // select the first k elements

私のアプローチは次のとおりです（全文はこちら） http://krkadev.blogspot.com/2010/08/random-numbers-without-repetition.html ).

O(N) ではなく O(K) で実行する必要があります。K は必要な要素の数、N は選択するリストのサイズです。

public <T> List<T> take(List<T> source, int k) {
 int n = source.size();
 if (k > n) {
   throw new IllegalStateException(
     "Can not take " + k +
     " elements from a list with " + n +
     " elements");
 }
 List<T> result = new ArrayList<T>(k);
 Map<Integer,Integer> used = new HashMap<Integer,Integer>();
 int metric = 0;
 for (int i = 0; i < k; i++) {
   int off = random.nextInt(n - i);
   while (true) {
     metric++;
     Integer redirect = used.put(off, n - i - 1);
     if (redirect == null) {
       break;
     }
     off = redirect;
   }
   result.add(source.get(off));
 }
 assert metric <= 2*k;
 return result;
}

これは、一般に認められているソリューションほど洗練されておらず、効率的でもありませんが、すぐに作成できます。まず、配列をランダムに並べ替えてから、最初の K 個の要素を選択します。Pythonでは、

import numpy

N = 20
K = 5

idx = np.arange(N)
numpy.random.shuffle(idx)

print idx[:K]

拡張メソッドを使用します。

    public static IEnumerable<T> TakeRandom<T>(this IEnumerable<T> elements, int countToTake)
    {
        var random = new Random();

        var internalList = elements.ToList();

        var selected = new List<T>();
        for (var i = 0; i < countToTake; ++i)
        {
            var next = random.Next(0, internalList.Count - selected.Count);
            selected.Add(internalList[next]);
            internalList[next] = internalList[internalList.Count - selected.Count];
        }
        return selected;
    }

public static IEnumerable<T> GetRandom<T>(this IList<T> list, int count, Random random)
    {
        // Probably you should throw exception if count > list.Count
        count = Math.Min(list.Count, count);

        var selectedIndices = new SortedSet<int>();

        // Random upper bound
        int randomMax = list.Count - 1;

        while (selectedIndices.Count < count)
        {
            int randomIndex = random.Next(0, randomMax);

            // skip over already selected indeces
            foreach (var selectedIndex in selectedIndices)
                if (selectedIndex <= randomIndex)
                    ++randomIndex;
                else
                    break;

            yield return list[randomIndex];

            selectedIndices.Add(randomIndex);
            --randomMax;
        }
    }

メモリ：~カウント
複雑：O(カウント²)

N が非常に大きい場合、N 個の数値をランダムにシャッフルして、たとえば最初の k 個の数値を選択する通常の方法は、空間の複雑さのために法外な方法になる可能性があります。次のアルゴリズムでは、時間と空間の両方の複雑さに対して O(k) のみが必要です。

http://arxiv.org/abs/1512.00501

def random_selection_indices(num_samples, N):
    modified_entries = {}
    seq = []
    for n in xrange(num_samples):
        i = N - n - 1
        j = random.randrange(i)

        # swap a[j] and a[i] 
        a_j = modified_entries[j] if j in modified_entries else j 
        a_i = modified_entries[i] if i in modified_entries else i

        if a_i != j:
            modified_entries[j] = a_i   
        elif j in modified_entries:   # no need to store the modified value if it is the same as index
            modified_entries.pop(j)

        if a_j != i:
            modified_entries[i] = a_j 
        elif i in modified_entries:   # no need to store the modified value if it is the same as index
            modified_entries.pop(i)
        seq.append(a_j)
    return seq

大きなリストで LINQ を使用し (各要素にアクセスするのにコストがかかる場合)、重複の可能性を許容できる場合:

new int[5].Select(o => (int)(rnd.NextDouble() * maxIndex)).Select(i => YourIEnum.ElementAt(i))

私の用途では、100,000 個の要素のリストがあり、それらは DB から取得されたため、リスト全体の rnd と比較して時間は約半分 (またはそれ以上) でした。

リストを大きくすると、重複の可能性が大幅に下がります。

ライセンス： CC-BY-SA と帰属

所属していません StackOverflow