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

158

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

JC Grubbs
sumber
12
Secara Acak, maksud Anda Inklusif atau Eksklusif? TKI, bisakah elemen yang sama diambil lebih dari satu kali? (benar-benar acak) Atau sekali elemen diambil, haruskah itu tidak lagi dipilih dari kumpulan yang tersedia?
Pretzel

Jawaban:

127

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.

Kyle Cronin
sumber
33
Saya merasa ini salah besar. Sepertinya bagian belakang daftar akan dipilih lebih sering daripada ujung depan karena ujung belakang akan melihat probabilitas yang jauh lebih besar. Misalnya, jika 35 nomor pertama tidak dipilih, 5 angka terakhir harus dipilih. Angka pertama hanya akan melihat peluang 5/40, tetapi angka terakhir akan melihat 1/1 lebih sering daripada 5/40 kali. Anda harus mengacak daftar terlebih dahulu sebelum Anda mengimplementasikan algoritma ini.
Ankur Goel
23
ok, saya menjalankan algoritma ini 10 juta kali pada daftar 40 elemen, masing-masing dengan tembakan 5/40 (.125) untuk dipilih, dan kemudian menjalankan simulasi itu beberapa kali. Ternyata ini tidak merata. Elemen 16 hingga 22 menjadi tidak terpilih (16 = .123, 17 = .124), sedangkan elemen 34 menjadi terlalu terpilih (34 = .129). Elemen 39 dan 40 juga tidak terpilih tetapi tidak sebanyak (39 = .1247, 40 = .1246)
Ankur Goel
22
@Ankur: Saya tidak percaya itu signifikan secara statistik. Saya percaya ada bukti induktif bahwa ini akan memberikan distribusi yang merata.
Rekursif
9
Saya telah mengulangi percobaan yang sama 100 juta kali, dan dalam percobaan saya item yang paling sedikit dipilih kurang dari 0,106% lebih jarang daripada item yang paling sering dipilih.
Rekursif
5
@recursive: Buktinya hampir sepele. Kita tahu bagaimana memilih item K dari K untuk setiap K dan bagaimana memilih 0 item dari N untuk N. apa pun. Asumsikan kita tahu metode untuk memilih item K atau K-1 yang seragam dari N-1> = K; maka kita dapat memilih item K dari N dengan memilih item pertama dengan probabilitas K / N dan kemudian menggunakan metode yang dikenal untuk memilih item K atau K-1 yang masih dibutuhkan dari sisa N-1.
Ilmari Karonen
216

Menggunakan LINQ:

YourList.OrderBy(x => rnd.Next()).Take(5)
Ers
sumber
2
+1 Tetapi jika dua elemen mendapatkan nomor yang sama dari rnd.Next () atau serupa maka yang pertama akan dipilih dan yang kedua mungkin tidak (jika tidak ada lagi elemen yang diperlukan). Itu cukup acak tergantung pada penggunaan, meskipun.
Lasse Espeholt
8
Saya pikir urutannya adalah O (n log (n)), jadi saya akan memilih solusi ini jika kesederhanaan kode adalah perhatian utama (yaitu dengan daftar kecil).
Guido
2
Tapi bukankah ini menghitung dan mengurutkan seluruh daftar? Kecuali, dengan "cepat", OP berarti "mudah", bukan "
pemain
2
Ini hanya akan berfungsi jika OrderBy () hanya memanggil pemilih kunci sekali untuk setiap elemen. Jika ia memanggilnya kapan pun ia ingin melakukan perbandingan antara dua elemen maka itu akan mendapatkan nilai yang berbeda setiap kali, yang akan mengacaukan penyortiran. [Dokumentasi] ( msdn.microsoft.com/en-us/library/vstudio/… ) tidak mengatakan yang mana.
Oliver Bock
2
Berhati-hatilah jika YourListmemiliki banyak item tetapi Anda hanya ingin memilih beberapa item. Dalam hal ini bukan cara yang efisien untuk melakukannya.
Callum Watkins
39
public static List<T> GetRandomElements<T>(this IEnumerable<T> list, int elementsCount)
{
    return list.OrderBy(arg => Guid.NewGuid()).Take(elementsCount).ToList();
}
vag
sumber
27

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.

Tyler
sumber
2
untuk (1) Anda dapat mengocok daftar lebih cepat daripada menyortir, karena (2) Anda akan melakukan bias distribusi Anda dengan menggunakan%
jk.
Mengingat keberatan yang Anda ajukan tentang panjang siklus sebuah rng, apakah ada cara kami dapat membuat algoritma yang akan memilih semua set dengan probabilitas yang sama?
Jonah
Untuk (1), untuk meningkatkan O (n log (n)), Anda dapat menggunakan semacam pemilihan untuk menemukan k elemen terkecil. Itu akan berjalan dalam O (n * k).
Jared
@ Jonah: Saya kira begitu. Mari kita asumsikan kita dapat menggabungkan beberapa generator angka acak independen untuk membuat yang lebih besar ( crypto.stackexchange.com/a/27431 ). Maka Anda hanya perlu rentang yang cukup besar untuk menangani ukuran daftar yang dimaksud.
Jared
16

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);
    }
Frank Schwieterman
sumber
LUAR BIASA! Sangat membantu saya!
Armstrongest
1
Apakah Anda punya alasan untuk tidak menggunakan Random () baru yang didasarkan pada Environment.TickCount vs. DateTime.Now.Millisecond?
Lasse Espeholt
Tidak, hanya tidak menyadari bahwa standar ada.
Frank Schwieterman
2
OK setahun terlambat tapi ... Bukankah ini cocok untuk jawaban yang agak pendek @ ersin, dan tidak akan gagal jika Anda mendapatkan nomor acak berulang (Di mana Ersin akan memiliki bias terhadap item pertama dari pasangan berulang)
Andiih
1
Random random = new Random(DateTime.Now.Millisecond);pada setiap panggilan pasti salah. Membuat instance baru Randomsetiap kali mengurangi keacakan yang sebenarnya. Gunakan static readonlycontoh itu, lebih disukai dibangun dengan konstruktor default.
jpmc26
12

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.

dhakim
sumber
Saya menerapkannya menggunakan C # di posting blog saya: vijayt.com/post/random-select-using-fisher-yates-algorithm . Semoga ini bisa membantu seseorang mencari cara C #.
vijayst
9

Anda dapat menggunakan ini tetapi pemesanan akan terjadi di sisi klien

 .AsEnumerable().OrderBy(n => Guid.NewGuid()).Take(5);
Marwan Roushdy
sumber
Sepakat. Ini mungkin bukan yang berkinerja terbaik atau yang paling acak, tetapi bagi sebagian besar orang ini akan cukup baik.
Richiban
Turun karena panduan dijamin unik, bukan acak .
Theodor Zoulias
8

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.

spoulson
sumber
Hanya dapatkan cukup item dalam daftar, tetapi jangan dapatkan secara acak.
culithay
2
Implementasi ini rusak karena menggunakan varhasil neededdan availablekeduanya bilangan bulat, yang needed/availableselalu berarti 0.
Niko
1
Ini tampaknya merupakan implementasi dari jawaban yang diterima.
DCShannon
6

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

nawfal
sumber
6

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);
        }
    }
}
drzaus
sumber
2
Ide bagus, dengan masalah. (1) Jika daftar Anda yang lebih besar sangat besar (baca dari database, misalnya) maka Anda menyadari seluruh daftar, yang mungkin melebihi memori. (2) Jika K dekat dengan N, maka Anda akan banyak sekali mencari indeks yang tidak diklaim di loop Anda, menyebabkan kode membutuhkan jumlah waktu yang tidak terduga. Masalah-masalah ini dapat dipecahkan.
Paul Chernoch
1
Solusi saya untuk masalah meronta-ronta adalah ini: jika K <N / 2, lakukan dengan cara Anda. Jika K> = N / 2, pilih indeks yang TIDAK boleh disimpan, bukan yang harus disimpan. Masih ada beberapa meronta-ronta, tetapi jauh lebih sedikit.
Paul Chernoch
Juga perhatikan bahwa ini mengubah urutan item yang disebutkan, yang mungkin dapat diterima dalam beberapa situasi, tetapi tidak dalam situasi lain.
Paul Chernoch
Rata-rata, untuk K = N / 2 (kasus terburuk untuk perbaikan yang disarankan Paul), algoritma (meronta-ronta) muncul untuk mengambil ~ 0,693 * iterasi N. Sekarang lakukan perbandingan kecepatan. Apakah ini lebih baik daripada jawaban yang diterima? Untuk ukuran sampel yang mana?
mbomb007
6

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));
    }
}
Paul Chernoch
sumber
Apakah tidak ada kesalahan dalam tes? Anda memiliki if (itemsList != null && k < n/2)yang berarti di dalam if invertSetselalu falseyang berarti bahwa logika tidak pernah digunakan.
NetMage
4

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
hardsetting
sumber
3

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.

IanStallings
sumber
1
Bekerja pada tembakan pertama!
sangam
3

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++;
 }
Tine M.
sumber
Menghapus dari tengah daftar sering kali akan mahal. Anda dapat mempertimbangkan menggunakan daftar tertaut untuk algoritme yang membutuhkan begitu banyak pemindahan. Atau setara, ganti item yang dihapus dengan nilai nol, tetapi kemudian Anda akan sedikit menggesek saat Anda memilih item yang sudah dihapus dan harus memilih lagi.
Paul Chernoch
3

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;
    }
}
Jesús López
sumber
2

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 ;
}
Tom Gullen
sumber
2

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

Alex Gilbert
sumber
1
Itu terlihat setara dengan saya. Bandingkan dengan stackoverflow.com/a/48141/2449863 yang
DCShannon
1

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#
Cameron A. Ellis
sumber
1

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;
    }
}
Jesse Gador
sumber
0

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
hitec
sumber
0

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;
}
Kristofer
sumber
0

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]
apdnu
sumber
0

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;
    }
Kvam
sumber
0
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 2 )

Kardinal
sumber
0

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
Dai
sumber
0

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.

Wolf5
sumber
Solusi ini mungkin memiliki elemen berulang !! Acak dalam daftar lubang mungkin tidak.
AxelWass
Hmm. Benar. Di mana saya menggunakannya, itu tidak masalah. Mengedit jawaban untuk mencerminkan hal itu.
Wolf5
-1

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]);
                }
Cyrille
sumber
Meskipun ini mungkin menjawab pertanyaan, Anda harus mengedit jawaban Anda untuk menyertakan penjelasan tentang bagaimana blok kode ini menjawab pertanyaan. Ini membantu memberikan konteks dan membuat jawaban Anda jauh lebih bermanfaat bagi pembaca di masa depan.
Hoppeduppeanut