حدد N عناصر عشوائية من القائمة<T> في C#

Question

أحتاج إلى خوارزمية سريعة لتحديد 5 عناصر عشوائية من قائمة عامة.على سبيل المثال، أود الحصول على 5 عناصر عشوائية من ملف List<string>.

Answer 1

قم بالتكرار من خلال كل عنصر ولكل عنصر، مما يجعل احتمالية الاختيار = (الرقم المطلوب)/(الرقم المتبقي)

لذا، إذا كان لديك 40 عنصرًا، فستكون فرصة اختيار العنصر الأول 5/40.إذا كان الأمر كذلك، فإن التالي لديه فرصة 4/39، وإلا فإن لديه فرصة 5/39.بحلول الوقت الذي تصل فيه إلى النهاية، سيكون لديك العناصر الخمسة الخاصة بك، وغالبًا ما تكون لديك جميعها قبل ذلك.

Answer 2

باستخدام لينك:

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

Answer 3

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

Answer 4

هذه في الواقع مشكلة أصعب مما تبدو عليه، ويرجع ذلك أساسًا إلى أن العديد من الحلول الصحيحة رياضيًا ستفشل في السماح لك فعليًا بضرب جميع الاحتمالات (المزيد حول هذا أدناه).

أولاً، إليك بعض المولدات سهلة التنفيذ والصحيحة إذا كان لديك مولد أرقام عشوائي حقًا:

(0) إجابة كايل هي O(n).

(1) أنشئ قائمة بأزواج n [(0، rand)، (1، rand)، (2، rand)، ...]، وقم بفرزها حسب الإحداثي الثاني، واستخدم k الأول (لك، k =5) مؤشرات للحصول على مجموعتك الفرعية العشوائية.أعتقد أن هذا سهل التنفيذ، على الرغم من أن الوقت قد حان لـ O(n log n).

(2) قم ببدء قائمة فارغة s = [] والتي ستصبح مؤشرات لعناصر عشوائية k.اختر رقم r في {0، 1، 2، ...، n-1} بشكل عشوائي، r = rand % n، وأضف هذا إلى s.بعد ذلك، خذ r = rand % (n-1) والصق في s؛أضف إلى r العناصر # الأقل منها في s لتجنب الاصطدامات.بعد ذلك، خذ r = rand % (n-2)، وافعل الشيء نفسه، وما إلى ذلك.حتى يكون لديك عناصر k مميزة في s.هذا لديه وقت تشغيل أسوأ حالة O(k^2).لذلك بالنسبة لـ k << n، يمكن أن يكون هذا أسرع.إذا واصلت ترتيب s وتتبع الفواصل الزمنية المتجاورة، فيمكنك تنفيذه في O(k log k)، ولكنه يتطلب المزيد من العمل.

@ كايل - أنت على حق، في الفكرة الثانية أتفق مع إجابتك.لقد قرأته على عجل في البداية، واعتقدت خطأً أنك كنت تشير إلى اختيار كل عنصر بالتسلسل مع احتمال ثابت k/n، وهو ما قد يكون خاطئًا - ولكن أسلوبك التكيفي يبدو صحيحًا بالنسبة لي.اسف بشأن ذلك.

حسنًا ، والآن بالنسبة للركلة:بشكل مقارب (للنمو الثابت k، n)، هناك n^k/k!اختيارات مجموعة فرعية من عناصر k من عناصر n [هذا تقريب لـ (n اختر k)].إذا كانت n كبيرة، وk ليست صغيرة جدًا، فإن هذه الأرقام ضخمة.أفضل طول دورة يمكنك أن تأمل فيه في أي مولد أرقام عشوائي قياسي 32 بت هو 2 ^ 32 = 256 ^ 4.لذا، إذا كانت لدينا قائمة مكونة من 1000 عنصر، وأردنا اختيار 5 منها عشوائيًا، فمن المستحيل أن يحقق مولد الأرقام العشوائية القياسي كل الاحتمالات.ومع ذلك، طالما أنك توافق على الاختيار الذي يعمل بشكل جيد مع المجموعات الأصغر، و"يبدو" دائمًا عشوائيًا، فيجب أن تكون هذه الخوارزميات على ما يرام.

إضافة:بعد كتابة هذا أدركت أنه من الصعب تنفيذ الفكرة (2) بشكل صحيح، لذلك أردت توضيح هذه الإجابة.للحصول على وقت O(k log k)، تحتاج إلى بنية تشبه المصفوفة تدعم عمليات البحث والإدراج O(log m) - يمكن لشجرة ثنائية متوازنة القيام بذلك.باستخدام مثل هذه البنية لبناء مصفوفة تسمى s، إليك بعض الثعابين الزائفة:

# 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

أقترح مراجعة بعض الحالات النموذجية لمعرفة كيفية تنفيذ هذا الشرح باللغة الإنجليزية بكفاءة.

Answer 5

أعتقد أن الإجابة المختارة صحيحة وحلوة جدًا.لقد قمت بتطبيقه بشكل مختلف، لأنني أردت أيضًا الحصول على النتيجة بترتيب عشوائي.

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

Answer 6

لقد واجهت هذه المشكلة للتو، وقد أوصلني المزيد من البحث على Google إلى مشكلة خلط القائمة بشكل عشوائي: http://en.wikipedia.org/wiki/Fisher-Yates_shuffle

لخلط قائمتك بشكل عشوائي (في مكانها)، يمكنك القيام بذلك:

لخلط مصفوفة a من العناصر n (المؤشرات 0..n-1):

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

إذا كنت تحتاج فقط إلى العناصر الخمسة الأولى، فبدلاً من تشغيل i على طول الطريق من n-1 إلى 1، تحتاج فقط إلى تشغيله إلى n-5 (على سبيل المثال:ن-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)، فيجب أن تتوقف عند 1، وليس n-k، حيث أن العدد الصحيح الذي تم اختياره عشوائيًا سيكون دائمًا 0.

Answer 7

يمكنك استخدام هذا ولكن الطلب سيحدث من جانب العميل

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

Answer 8

من التنين في الخوارزمية, ، تفسير في 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--;
}

ستحدد هذه الخوارزمية مؤشرات فريدة لقائمة العناصر.

Answer 9

كنت أفكر في تعليق @JohnShedletsky على إجابة مقبولة بخصوص (إعادة الصياغة):

يجب أن تكون قادرًا على القيام بذلك في O(subset.Length)، بدلاً من O(originalList.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);
        }
    }
}

Answer 10

اختيار ن عشوائي لا ينبغي أن يكون للعناصر الموجودة في المجموعة أي علاقة بها طلب!العشوائية تتعلق بعدم القدرة على التنبؤ وليس بخلط المواقع في المجموعة.جميع الإجابات التي تتعامل مع بعض الترتيبات لا بد أن تكون أقل كفاءة من تلك التي لا تفعل ذلك.وبما أن الكفاءة هي المفتاح هنا، فسوف أقوم بنشر شيء لا يغير ترتيب العناصر كثيرًا.

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 }، فيمكنها إعطاء { 1، 4، 4 }، { 1، 4، 3 } إلخ لـ 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();
}

يعد الكود أطول قليلاً من طرق القاموس الأخرى هنا لأنني لا أقوم فقط بإضافة القائمة، ولكن أيضًا إزالتها من القائمة، لذا فهي عبارة عن حلقتين نوعًا ما.يمكنك أن ترى هنا أنني لم أفعل ذلك أعيد ترتيبها أي شيء على الإطلاق عندما 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 }، فيمكن أن ينتهي الأمر في { 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);
}

إذا كان الأمر كله يتعلق بالأداء مع وجود عشرات الآلاف من العناصر في القائمة والتي يجب تكرارها 10000 مرة، فقد ترغب في الحصول على فئة عشوائية أسرع من System.Random, ، لكنني لا أعتقد أن هذه مشكلة كبيرة نظرًا لأن الأخير على الأرجح لا يمثل عنق الزجاجة أبدًا، فهو سريع جدًا بما فيه الكفاية..

يحرر: إذا كنت بحاجة إلى إعادة ترتيب العناصر المرتجعة أيضًا، فلا يوجد شيء يمكن التغلب عليه نهج فيشر ييتس لحكيم - قصير وحلو وبسيط..

Answer 11

الحل البسيط الذي أستخدمه (ربما لا يكون جيدًا للقوائم الكبيرة):انسخ القائمة إلى قائمة مؤقتة، ثم حدد بشكل عشوائي عنصرًا من القائمة المؤقتة وضعه في قائمة العناصر المحددة أثناء إزالته من القائمة المؤقتة (بحيث لا يمكن إعادة تحديده).

مثال:

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

Answer 12

لقد قمت بدمج العديد من الإجابات المذكورة أعلاه لإنشاء طريقة تمديد تم تقييمها بتكاسل.أظهر الاختبار الذي أجريته أن نهج كايل (Order(N)) أبطأ بعدة مرات من استخدام drzaus لمجموعة لاقتراح المؤشرات العشوائية للاختيار (Order(K)).يقوم الأول بإجراء العديد من الاستدعاءات لمولد الأرقام العشوائية، بالإضافة إلى التكرار مرات أكثر على العناصر.

وكانت أهداف التنفيذ الخاصة بي:

1) لا تدرك القائمة الكاملة إذا تم إعطاؤك IEnumerable الذي ليس ضمن قائمة IList.إذا تم إعطائي سلسلة من ملايين العناصر، فلا أريد أن تنفد الذاكرة.استخدم نهج كايل للحصول على حل عبر الإنترنت.

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# عشوائي إذا أردت.(FastRandom كتبه كولن جرين وهو جزء من SharpNEAT.لها فترة 2^128-1 وهي أفضل من العديد من RNGs.)

وإليكم اختبارات الوحدة:

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

Answer 13

هنا لديك تطبيق واحد يعتمد على فيشر ييتس شافل تعقيد خوارزميته هو 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;
    }
}

Answer 14

بناءً على إجابة كايل، هذا هو تطبيق 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 ;
}

Answer 15

قد تكون هذه الطريقة معادلة لطريقة كايل.

لنفترض أن قائمتك بحجم 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--;
    }
} 

يعمل كالسحر :)

-أليكس جيلبرت

Answer 16

يمتد من إجابة @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

Answer 17

هذا هو أفضل ما يمكن أن أتوصل إليه في القطع الأول:

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 - إجمالي عدد القائمة ثم سحب تلك العناصر في القائمة هو أفضل طريقة، ولكن استخدام القاموس لضمان التفرد هو شيء ما زلت أفكر فيه.

لاحظ أيضًا أنني استخدمت قائمة سلاسل، واستبدلها حسب الحاجة.

Answer 18

لماذا لا شيء من هذا القبيل:

 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#

Answer 19

إنه أصعب بكثير مما يعتقده المرء.انظر مقال رائع """""""""""" من جيف.

لقد كتبت مقالة قصيرة جدًا حول هذا الموضوع بما في ذلك كود C#:
إرجاع مجموعة فرعية عشوائية من عناصر N من صفيف معين

Answer 20

هدف:حدد عدد 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;
    }
}

Answer 21

لقد قمت بذلك مؤخرًا في مشروعي باستخدام فكرة مشابهة لـ نقطة تايلر 1.
كنت أقوم بتحميل مجموعة من الأسئلة واختيار خمسة منها بشكل عشوائي.تم الفرز باستخدام IComparer.
تم تحميل كافة الأسئلة في قائمة "فرز الأسئلة"، والتي تم فرزها بعد ذلك باستخدام وظيفة فرز القائمة والعناصر 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

Answer 22

هذا هو نهجي (النص الكامل هنا http://krkadev.blogspot.com/2010/08/random-numbers-without-repetition.html ).

يجب تشغيله بطريقة O(K) بدلاً من O(N)، حيث 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;
}

Answer 23

هذا ليس أنيقًا أو فعالاً مثل الحل المقبول، لكنه سريع الكتابة.أولاً، قم بتبديل المصفوفة بشكل عشوائي، ثم حدد عناصر K الأولى.في بايثون،

import numpy

N = 20
K = 5

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

print idx[:K]

Answer 24

سأستخدم طريقة التمديد.

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

Answer 25

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

ذاكرة:~ العد
تعقيد:يا (العد²)

Answer 26

عندما تكون 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

Answer 27

استخدام LINQ مع قوائم كبيرة (عندما يكون لمس كل عنصر مكلفًا) وإذا كان بإمكانك التعايش مع إمكانية التكرارات:

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

لاستخدامي، كان لدي قائمة تضم 100.000 عنصر، وبسبب سحبها من قاعدة البيانات، قمت بتخفيض الوقت إلى النصف تقريبًا (أو أفضل) مقارنةً بـ rnd في القائمة بأكملها.

سيؤدي وجود قائمة كبيرة إلى تقليل احتمالات التكرارات بشكل كبير.