Pilih N elemen acak dari Daftar <T> dalam C #

Saya memerlukan algoritma cepat untuk memilih 5 elemen acak dari daftar generik. Misalnya, saya ingin mendapatkan 5 elemen acak dari a List<string>.

Iterate through dan untuk setiap elemen, buat probabilitas seleksi = (jumlah yang diperlukan) / (jumlah kiri)

Jadi jika Anda memiliki 40 item, yang pertama akan memiliki peluang 5/40 untuk dipilih. Jika ya, peluang berikutnya 4/39, jika tidak, peluang 5/39. Pada saat Anda mencapai akhir, Anda akan memiliki 5 item Anda, dan seringkali Anda akan memiliki semuanya sebelum itu.

Menggunakan 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();
}

Ini sebenarnya adalah masalah yang lebih sulit daripada kedengarannya, terutama karena banyak solusi yang benar secara matematis akan gagal untuk benar-benar memungkinkan Anda untuk mencapai semua kemungkinan (lebih lanjut tentang ini di bawah).

Pertama, berikut adalah beberapa generator yang mudah diimplementasikan, benar-jika-Anda-memiliki-nomor-acak:

(0) Jawaban Kyle, yaitu O (n).

(1) Buat daftar n pasangan [(0, rand), (1, rand), (2, rand), ...], urutkan berdasarkan koordinat kedua, dan gunakan k pertama (untuk Anda, k = 5) indeks untuk mendapatkan bagian acak Anda. Saya pikir ini mudah diimplementasikan, meskipun sudah waktunya O (n log n).

(2) Init daftar kosong s = [] yang akan tumbuh menjadi indeks k elemen acak. Pilih angka r dalam {0, 1, 2, ..., n-1} secara acak, r = rand% n, dan tambahkan ini ke s. Selanjutnya ambil r = rand% (n-1) dan tetap di s; tambahkan ke r elemen # kurang dari dalam s untuk menghindari tabrakan. Selanjutnya ambil r = rand% (n-2), dan lakukan hal yang sama, dll. Hingga Anda memiliki k elemen yang berbeda di s. Ini memiliki waktu berjalan paling buruk O (k ^ 2). Jadi untuk k << n, ini bisa lebih cepat. Jika Anda terus mengurutkan dan melacak interval bersebelahan yang dimilikinya, Anda dapat mengimplementasikannya dalam O (k log k), tetapi ini lebih banyak pekerjaan.

@Kyle - Anda benar, setelah dipikir-pikir saya setuju dengan jawaban Anda. Saya buru-buru membacanya pada awalnya, dan secara keliru berpikir Anda mengindikasikan untuk secara berurutan memilih setiap elemen dengan probabilitas tetap k / n, yang mungkin salah - tetapi pendekatan adaptif Anda tampaknya tepat bagi saya. Maaf soal itu.

Ok, dan sekarang untuk kicker: asimptotik (untuk k tetap, n tumbuh), ada n ^ k / k! pilihan elemen k subset dari n elemen [ini merupakan perkiraan (n pilih k)]. Jika n besar, dan k tidak terlalu kecil, maka angka-angka ini sangat besar. Panjang siklus terbaik yang dapat Anda harapkan dalam generator angka acak 32 bit standar adalah 2 ^ 32 = 256 ^ 4. Jadi jika kita memiliki daftar 1000 elemen, dan kita ingin memilih 5 secara acak, tidak mungkin generator nomor acak standar akan mencapai semua kemungkinan. Namun, selama Anda baik-baik saja dengan pilihan yang berfungsi baik untuk set yang lebih kecil, dan selalu "terlihat" acak, maka algoritma ini harus ok.

Tambahan : Setelah menulis ini, saya menyadari bahwa itu sulit untuk mengimplementasikan ide (2) dengan benar, jadi saya ingin mengklarifikasi jawaban ini. Untuk mendapatkan waktu O (k log k), Anda memerlukan struktur mirip array yang mendukung pencarian dan penyisipan O (log m) - pohon biner seimbang dapat melakukan ini. Menggunakan struktur seperti itu untuk membangun array bernama s, berikut adalah beberapa pseudopython:

# 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

Saya sarankan menjalankan beberapa contoh kasus untuk melihat bagaimana ini secara efisien mengimplementasikan penjelasan bahasa Inggris di atas.

Saya pikir jawaban yang dipilih benar dan cukup manis. Saya menerapkannya secara berbeda, karena saya juga ingin hasilnya dalam urutan acak.

    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);
    }

Saya baru saja mengalami masalah ini, dan beberapa lagi pencarian google membawa saya pada masalah pengacakan daftar secara acak: http://en.wikipedia.org/wiki/Fisher-Yates_shuffle

Untuk mengacak daftar Anda (di tempat) secara acak, Anda melakukan ini:

Untuk mengocok array a dari n elemen (indeks 0..n-1):

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

Jika Anda hanya memerlukan 5 elemen pertama, maka alih-alih menjalankan saya dari n-1 hingga 1, Anda hanya perlu menjalankannya ke n-5 (yaitu: n-5)

Katakanlah Anda membutuhkan k item,

Ini menjadi:

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

Setiap item yang dipilih ditukar ke ujung array, sehingga elemen k yang dipilih adalah elemen k terakhir dari array.

Ini membutuhkan waktu O (k), di mana k adalah jumlah elemen yang dipilih secara acak yang Anda butuhkan.

Selanjutnya, jika Anda tidak ingin mengubah daftar awal Anda, Anda dapat menuliskan semua swap Anda dalam daftar sementara, membalikkan daftar itu, dan menerapkannya lagi, sehingga melakukan set swap terbalik dan mengembalikan daftar awal Anda tanpa mengubah O (k) waktu berjalan.

Akhirnya, untuk stickler nyata, jika (n == k), Anda harus berhenti pada 1, bukan nk, karena bilangan bulat yang dipilih secara acak akan selalu 0.

Anda dapat menggunakan ini tetapi pemesanan akan terjadi di sisi klien

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

Dari Naga dalam Algoritma , interpretasi dalam 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--;
}

Algoritma ini akan memilih indeks unik dari daftar item.

Memilih N item acak dari grup seharusnya tidak ada hubungannya dengan pesanan ! Keacakan adalah tentang ketidakpastian dan bukan tentang pengacakan posisi dalam suatu grup. Semua jawaban yang berhubungan dengan pemesanan agak pasti kurang efisien daripada yang tidak. Karena efisiensi adalah kuncinya di sini, saya akan memposting sesuatu yang tidak mengubah urutan item terlalu banyak.

1) Jika Anda membutuhkan nilai acak sejati yang berarti tidak ada batasan pada elemen mana yang harus dipilih (yaitu, item yang dipilih dapat dipilih kembali):

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;
}

Jika Anda menonaktifkan flag pengecualian, maka Anda dapat memilih item acak berapa kali.

Jika Anda memiliki {1, 2, 3, 4}, maka ia dapat memberikan {1, 4, 4}, {1, 4, 3} dll untuk 3 item atau bahkan {1, 4, 3, 2, 4} untuk 5 item!

Ini harusnya cukup cepat, karena tidak ada yang perlu diperiksa.

2) Jika Anda memerlukan anggota individu dari grup tanpa pengulangan, maka saya akan mengandalkan kamus (seperti yang sudah ditunjukkan banyak orang).

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();
}

Kode ini sedikit lebih panjang daripada pendekatan kamus lain di sini karena saya tidak hanya menambahkan, tetapi juga menghapus dari daftar, jadi itu agak dua loop. Anda dapat melihat di sini bahwa saya belum memesan ulang apa pun ketika countmenjadi sama dengan source.Count. Itu karena saya percaya keacakan harus di set kembali secara keseluruhan . Maksudku jika Anda ingin 5 item acak dari 1, 2, 3, 4, 5, seharusnya tidak peduli jika 1, 3, 4, 2, 5atau 1, 2, 3, 4, 5, tapi jika Anda membutuhkan 4 item dari set yang sama, maka harus tak terduga menghasilkan di 1, 2, 3, 4, 1, 3, 5, 2, 2, 3, 5, 4dll Kedua, ketika jumlah item acak menjadi dikembalikan lebih dari setengah dari grup asli, maka lebih mudah untuk dihapussource.Count - countitem dari grup daripada menambahkan countitem. Untuk alasan kinerja, saya menggunakan sourcealih-alih sourceDictmendapatkan indeks acak dalam metode hapus.

Jadi jika Anda memiliki {1, 2, 3, 4}, ini bisa berakhir pada {1, 2, 3}, {3, 4, 1} dll untuk 3 item.

3) Jika Anda membutuhkan nilai acak yang benar-benar berbeda dari grup Anda dengan mempertimbangkan duplikat dalam grup asli, maka Anda dapat menggunakan pendekatan yang sama seperti di atas, tetapi HashSetakan lebih ringan daripada kamus.

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();
}

The randomsvariabel membuat HashSetuntuk menghindari duplikasi yang ditambahkan dalam yang paling langka kasus yang paling langka di mana Random.Nextdapat menghasilkan nilai yang sama, terutama ketika daftar masukan kecil.

Jadi {1, 2, 2, 4} => 3 item acak => {1, 2, 4} dan tidak pernah {1, 2, 2}

{1, 2, 2, 4} => 4 item acak => pengecualian !! atau {1, 2, 4} tergantung pada set bendera.

Beberapa metode ekstensi yang saya gunakan:

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);
}

Jika itu semua tentang kinerja dengan puluhan item 1000s dalam daftar harus diulang 10.000 kali, maka Anda mungkin ingin memiliki kelas acak lebih cepat daripada System.Random, tapi saya tidak berpikir itu masalah besar mengingat yang terakhir kemungkinan besar tidak pernah menjadi bottleneck, itu cukup cepat ..

Sunting: Jika Anda perlu mengatur ulang pesanan barang yang dikembalikan juga, maka tidak ada yang dapat mengalahkan pendekatan Fisher-Yates dhakim - pendek, manis dan sederhana ..

Sedang memikirkan komentar oleh @JohnShedletsky tentang jawaban yang diterima mengenai (parafrase):

Anda harus dapat melakukan ini di O (subset.Length), daripada O (originalList.Length)

Pada dasarnya, Anda harus bisa menghasilkan subset indeks acak dan kemudian memetiknya dari daftar asli.

Metode

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()));
    }

}

Jika Anda ingin menjadi lebih efisien, Anda mungkin akan menggunakan HashSetsatu indeks , tidak daftar unsur-unsur yang sebenarnya (dalam kasus Anda punya jenis kompleks atau perbandingan mahal);

Tes Unit

Dan untuk memastikan kami tidak memiliki tabrakan, dll.

[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);
        }
    }
}

Saya menggabungkan beberapa jawaban di atas untuk membuat metode penyuluhan yang dievaluasi dengan baik. Pengujian saya menunjukkan bahwa pendekatan Kyle (Urutan (N)) berkali-kali lebih lambat daripada penggunaan satu set drzaus untuk mengusulkan indeks acak untuk dipilih (Orde (K)). Yang pertama melakukan lebih banyak panggilan ke generator nomor acak, ditambah iterates lebih banyak kali atas item.

Tujuan implementasi saya adalah:

1) Jangan menyadari daftar lengkap jika diberi nomor IEnumer yang bukan IList. Jika saya diberi urutan satu juta item, saya tidak ingin kehabisan memori. Gunakan pendekatan Kyle untuk solusi online.

2) Jika saya dapat mengatakan bahwa itu adalah IList, gunakan pendekatan drzaus, dengan twist. Jika K lebih dari setengah N, saya berisiko meronta-ronta karena saya memilih banyak indeks acak lagi dan lagi dan harus melewati mereka. Jadi saya menyusun daftar indeks untuk TIDAK disimpan.

3) Saya menjamin bahwa barang akan dikembalikan dalam urutan yang sama dengan yang ditemui. Algoritma Kyle tidak membutuhkan perubahan. Algoritma drzaus mensyaratkan bahwa saya tidak memancarkan item dalam urutan bahwa indeks acak dipilih. Saya mengumpulkan semua indeks ke dalam SortedSet, lalu memancarkan item dalam urutan indeks yang diurutkan.

4) Jika K besar dibandingkan dengan N dan saya membalikkan arti set, maka saya menghitung semua item dan menguji jika indeks tidak di set. Ini berarti bahwa saya kehilangan Orde (K) waktu berjalan, tetapi karena K dekat dengan N dalam kasus ini, saya tidak kehilangan banyak.

Ini kodenya:

    /// <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;
                }
            }
        }  
    } 

Saya menggunakan generator nomor acak khusus, tetapi Anda hanya dapat menggunakan C # 's Acak jika Anda mau. ( FastRandom ditulis oleh Colin Green dan merupakan bagian dari SharpNEAT. Ia memiliki periode 2 ^ 128-1 yang lebih baik daripada banyak RNG.)

Berikut adalah unit test:

[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));
    }
}

Meluas dari jawaban @ers, jika ada yang khawatir tentang kemungkinan implementasi berbeda dari OrderBy, ini harusnya aman:

// 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

Ini adalah yang terbaik yang bisa saya dapatkan pada potongan pertama:

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;
}

Menggunakan daftar tebusan dalam kisaran 1 - jumlah total daftar dan kemudian hanya menarik barang-barang itu dalam daftar tampaknya merupakan cara terbaik, tetapi menggunakan Kamus untuk memastikan keunikan adalah sesuatu yang masih saya pertimbangkan.

Juga perhatikan saya menggunakan daftar string, ganti sesuai kebutuhan.

Solusi sederhana yang saya gunakan (mungkin tidak baik untuk daftar besar): Salin daftar ke daftar sementara, kemudian dalam loop pilih item secara acak dari daftar temp dan meletakkannya di daftar item yang dipilih sambil menghapusnya dari daftar temp (jadi tidak bisa terpilih kembali).

Contoh:

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++;
 }

Di sini Anda memiliki satu implementasi berdasarkan Fisher-Yates Shuffle yang kompleksitas algoritmanya adalah O (n) di mana n adalah subset atau ukuran sampel, alih-alih ukuran daftar, seperti yang ditunjukkan oleh John Shedletsky.

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;
    }
}

Berdasarkan jawaban Kyle, inilah implementasi c # saya.

/// <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 ;
}

Metode ini mungkin setara dengan milik Kyle.

Katakanlah daftar Anda berukuran n dan Anda ingin elemen 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--;
    }
} 

Bekerja seperti pesona :)

-Alex Gilbert

kenapa tidak seperti ini:

 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#

Ini jauh lebih sulit daripada yang orang pikirkan. Lihat Artikel hebat "Mengocok" dari Jeff.

Saya memang menulis artikel yang sangat singkat tentang subjek itu termasuk kode C #:
Mengembalikan subset acak elemen N dari array yang diberikan

Sasaran: Pilih N jumlah item dari sumber koleksi tanpa duplikasi. Saya membuat ekstensi untuk semua koleksi generik. Begini cara saya melakukannya:

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;
    }
}

Baru-baru ini saya melakukan ini pada proyek saya menggunakan ide yang mirip dengan poin 1 Tyler .
Saya sedang memuat banyak pertanyaan dan memilih lima secara acak. Penyortiran dicapai menggunakan IComparer .
aSemua pertanyaan dimuat dalam daftar QuestionSorter, yang kemudian disortir menggunakan fungsi Urutkan Daftar dan elemen k pertama yang dipilih.

    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;
            }
        }
    }

Pemakaian:

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

    // add the questions here

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

    // select the first k elements

Inilah pendekatan saya (teks lengkap di sini http://krkadev.blogspot.com/2010/08/random-numbers-without-repetition.html ).

Itu harus dijalankan dalam O (K) bukan O (N), di mana K adalah jumlah elemen yang diinginkan dan N adalah ukuran daftar untuk dipilih:

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;
}

Ini tidak seanggun atau seefisien solusi yang diterima, tetapi cepat untuk menulis. Pertama, permute array secara acak, lalu pilih elemen K pertama. Dengan python,

import numpy

N = 20
K = 5

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

print idx[:K]

Saya akan menggunakan metode ekstensi.

    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;
        }
    }

Memori: ~ hitung
Kompleksitas: O (hitung ² )

Ketika N sangat besar, metode normal yang secara acak mengocok angka N dan memilih, katakanlah, angka k pertama, dapat menjadi penghalang karena kompleksitas ruang. Algoritma berikut hanya membutuhkan O (k) untuk kompleksitas waktu dan ruang.

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

Menggunakan LINQ dengan daftar besar (ketika mahal untuk menyentuh setiap elemen) DAN jika Anda dapat hidup dengan kemungkinan duplikat:

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

Untuk penggunaan saya, saya punya daftar 100.000 elemen, dan karena mereka ditarik dari DB saya sekitar setengah (atau lebih baik) waktu dibandingkan dengan rnd pada seluruh daftar.

Memiliki daftar besar akan sangat mengurangi kemungkinan duplikat.

Ini akan menyelesaikan masalah Anda

var entries=new List<T>();
var selectedItems = new List<T>();


                for (var i = 0; i !=10; i++)
                {
                    var rdm = new Random().Next(entries.Count);
                        while (selectedItems.Contains(entries[rdm]))
                            rdm = new Random().Next(entries.Count);

                    selectedItems.Add(entries[rdm]);
                }