اختيار عنصر عشوائي من مجموعة

Question

كيف يمكنني اختيار عنصر عشوائي من مجموعة ؟ أنا مهتم بشكل خاص في انتقاء عنصر عشوائي من HashSet أو LinkedHashSet في جافا.حلول لغات أخرى هي أيضا موضع ترحيب.

Answer 1

int size = myHashSet.size();
int item = new Random().nextInt(size); // In real life, the Random object should be rather more shared than this
int i = 0;
for(Object obj : myhashSet)
{
    if (i == item)
        return obj;
    i++;
}

Answer 2

إلى حد ما ذات صلة هل تعلم:

هناك أساليب مفيدة في java.util.Collections من أجل خلط كل مجموعات: Collections.shuffle(List<?>) و Collections.shuffle(List<?> list, Random rnd).

Answer 3

حل سريع لـ Java باستخدام ArrayList و HashMap:[عنصر -> الفهرس].

الدافع:أنا في حاجة إلى مجموعة من العناصر مع RandomAccess خصائص خاصة إلى اختيار عنصر عشوائي من مجموعة (انظر pollRandom طريقة).عشوائية الملاحة في شجرة ثنائية ليست دقيقة:الأشجار ليست متوازنة تماما ، التي لن تؤدي إلى توزيع موحد.

public class RandomSet<E> extends AbstractSet<E> {

    List<E> dta = new ArrayList<E>();
    Map<E, Integer> idx = new HashMap<E, Integer>();

    public RandomSet() {
    }

    public RandomSet(Collection<E> items) {
        for (E item : items) {
            idx.put(item, dta.size());
            dta.add(item);
        }
    }

    @Override
    public boolean add(E item) {
        if (idx.containsKey(item)) {
            return false;
        }
        idx.put(item, dta.size());
        dta.add(item);
        return true;
    }

    /**
     * Override element at position <code>id</code> with last element.
     * @param id
     */
    public E removeAt(int id) {
        if (id >= dta.size()) {
            return null;
        }
        E res = dta.get(id);
        idx.remove(res);
        E last = dta.remove(dta.size() - 1);
        // skip filling the hole if last is removed
        if (id < dta.size()) {
            idx.put(last, id);
            dta.set(id, last);
        }
        return res;
    }

    @Override
    public boolean remove(Object item) {
        @SuppressWarnings(value = "element-type-mismatch")
        Integer id = idx.get(item);
        if (id == null) {
            return false;
        }
        removeAt(id);
        return true;
    }

    public E get(int i) {
        return dta.get(i);
    }

    public E pollRandom(Random rnd) {
        if (dta.isEmpty()) {
            return null;
        }
        int id = rnd.nextInt(dta.size());
        return removeAt(id);
    }

    @Override
    public int size() {
        return dta.size();
    }

    @Override
    public Iterator<E> iterator() {
        return dta.iterator();
    }
}

Answer 4

هذا هو أسرع من أجل كل حلقة في قبول الإجابة:

int index = rand.nextInt(set.size());
Iterator<Object> iter = set.iterator();
for (int i = 0; i < index; i++) {
    iter.next();
}
return iter.next();

ل-كل بناء المكالمات Iterator.hasNext() في كل حلقة ، ولكن منذ index < set.size(), هذا الاختيار غير الضرورية والنفقات العامة.رأيت 10-20% زيادة في السرعة ، ولكن YMMV.(أيضا هذا برمجيا دون الحاجة إلى إضافة مبلغ إضافي عودة البيان.)

لاحظ أن هذه التعليمات البرمجية (و معظم إجابات أخرى) يمكن تطبيقها على أي مجموعة ، وليس مجرد مجموعة.في عام طريقة النموذج:

public static <E> E choice(Collection<? extends E> coll, Random rand) {
    if (coll.size() == 0) {
        return null; // or throw IAE, if you prefer
    }

    int index = rand.nextInt(coll.size());
    if (coll instanceof List) { // optimization
        return ((List<? extends E>) coll).get(index);
    } else {
        Iterator<? extends E> iter = coll.iterator();
        for (int i = 0; i < index; i++) {
            iter.next();
        }
        return iter.next();
    }
}

Answer 5

إذا كنت تريد أن تفعل ذلك في جافا, يجب عليك أن تنظر نسخ العناصر إلى نوع من الوصول العشوائي جمع (مثل ArrayList).لأنه ما لم يكن لديك مجموعة صغيرة ، الوصول إلى العنصر المحدد سوف تكون مكلفة (O(n) بدلا من O(1)).[ed:قائمة نسخ أيضا O(n)]

بدلا من ذلك, يمكنك البحث عن مجموعة أخرى تنفيذ أكثر تطابقا مع الاحتياجات الخاصة بك.على ListOrderedSet من المشاع مجموعات تبدو واعدة.

Answer 6

في جاوة:

Set<Integer> set = new LinkedHashSet<Integer>(3);
set.add(1);
set.add(2);
set.add(3);

Random rand = new Random(System.currentTimeMillis());
int[] setArray = (int[]) set.toArray();
for (int i = 0; i < 10; ++i) {
    System.out.println(setArray[rand.nextInt(set.size())]);
}

Answer 7

List asList = new ArrayList(mySet);
Collections.shuffle(asList);
return asList.get(0);

Answer 8

Clojure الحل:

(defn pick-random [set] (let [sq (seq set)] (nth sq (rand-int (count sq)))))

Answer 9

Perl 5

@hash_keys = (keys %hash);
$rand = int(rand(@hash_keys));
print $hash{$hash_keys[$rand]};

هنا هو طريقة واحدة للقيام بذلك.

Answer 10

C++.هذا ينبغي أن يكون سريع معقولة ، كما أنها لا تتطلب بالتكرار على مجموعة كاملة أو الفرز ذلك.هذا يجب أن تعمل من خارج منطقة الجزاء مع معظم الحديث المجمعين على افتراض أنها تدعم tr1.إن لم يكن, قد تحتاج إلى استخدام دفعة.

على دفعة مستندات هل من المفيد هنا أن أشرح هذا حتى إذا كنت لا تستخدم دفعة.

الخدعة هو الاستفادة من حقيقة أن البيانات التي تم تقسيمها إلى الدلاء ، لتحديد بسرعة اختيارها عشوائيا دلو (مع احتمال).

//#include <boost/unordered_set.hpp>  
//using namespace boost;
#include <tr1/unordered_set>
using namespace std::tr1;
#include <iostream>
#include <stdlib.h>
#include <assert.h>
using namespace std;

int main() {
  unordered_set<int> u;
  u.max_load_factor(40);
  for (int i=0; i<40; i++) {
    u.insert(i);
    cout << ' ' << i;
  }
  cout << endl;
  cout << "Number of buckets: " << u.bucket_count() << endl;

  for(size_t b=0; b<u.bucket_count(); b++)
    cout << "Bucket " << b << " has " << u.bucket_size(b) << " elements. " << endl;

  for(size_t i=0; i<20; i++) {
    size_t x = rand() % u.size();
    cout << "we'll quickly get the " << x << "th item in the unordered set. ";
    size_t b;
    for(b=0; b<u.bucket_count(); b++) {
      if(x < u.bucket_size(b)) {
        break;
      } else
        x -= u.bucket_size(b);
    }
    cout << "it'll be in the " << b << "th bucket at offset " << x << ". ";
    unordered_set<int>::const_local_iterator l = u.begin(b);
    while(x>0) {
      l++;
      assert(l!=u.end(b));
      x--;
    }
    cout << "random item is " << *l << ". ";
    cout << endl;
  }
}

Answer 11

الحل الكلام أعلاه من حيث الكمون ولكن لا يضمن المساواة في احتمال كل مؤشر اختياره.
إذا لا بد من النظر فيها ، في محاولة الخزان أخذ العينات. http://en.wikipedia.org/wiki/Reservoir_sampling.
مجموعات.خلط ورق اللعب() (كما اقترح بعض) يستخدم أحد هذه الخوارزمية.

Answer 12

بما أنك قلت "حلول لغات أخرى هي أيضا موضع ترحيب" ، هنا نسخة بايثون:

>>> import random
>>> random.choice([1,2,3,4,5,6])
3
>>> random.choice([1,2,3,4,5,6])
4

Answer 13

لا يمكنك فقط الحصول على الحجم/الطول مجموعة/مجموعة توليد رقم عشوائي بين 0 و الحجم/الطول ، ثم استدعاء العنصر الذي مؤشر مباريات هذا العدد ؟ HashSet لديه .حجم (طريقة), أنا متأكد.

في psuedocode -

function randFromSet(target){
 var targetLength:uint = target.length()
 var randomIndex:uint = random(0,targetLength);
 return target[randomIndex];
}

Answer 14

PHP, على افتراض "مجموعة" صفيف:

$foo = array("alpha", "bravo", "charlie");
$index = array_rand($foo);
$val = $foo[$index];

في ميرسين الاعصار وظائف أفضل ولكن لا يوجد جبل ما يعادل array_rand في PHP.

Answer 15

رمز يحتوي على مجموعة ونوع عشوائي-عنصر المشغل ، الأحادية "?", وبالتالي فإن التعبير

? set( [1, 2, 3, 4, 5] )

سوف تنتج رقم عشوائي بين 1 و 5.

البذور عشوائي هو تهيئة إلى 0 عند تشغيل برنامج ، حتى أن تنتج نتائج مختلفة في كل شوط استخدام randomize()

Answer 16

في C#

        Random random = new Random((int)DateTime.Now.Ticks);

        OrderedDictionary od = new OrderedDictionary();

        od.Add("abc", 1);
        od.Add("def", 2);
        od.Add("ghi", 3);
        od.Add("jkl", 4);


        int randomIndex = random.Next(od.Count);

        Console.WriteLine(od[randomIndex]);

        // Can access via index or key value:
        Console.WriteLine(od[1]);
        Console.WriteLine(od["def"]);

Answer 17

جافا سكريبت الحل ;)

function choose (set) {
    return set[Math.floor(Math.random() * set.length)];
}

var set  = [1, 2, 3, 4], rand = choose (set);

أو بدلا من ذلك:

Array.prototype.choose = function () {
    return this[Math.floor(Math.random() * this.length)];
};

[1, 2, 3, 4].choose();

Answer 18

في اللثغة

(defun pick-random (set)
       (nth (random (length set)) set))

Answer 19

في الرياضيات:

a = {1, 2, 3, 4, 5}

a[[ ⌈ Length[a] Random[] ⌉ ]]

أو في الإصدارات الأخيرة ، ببساطة:

RandomChoice[a]

---

وقد أسفل التصويت ، ربما لأنه يفتقر إلى التفسير ، حتى هنا هو واحد:

Random[] يولد المزيف تطفو بين 0 و 1.هذا هو مضروبا في طول القائمة ثم السقف وظيفة المستخدمة في جولة إلى عدد صحيح.هذا المؤشر هو ثم يستخرج من a.

منذ جدول تجزئة الوظيفة في كثير من الأحيان القيام به مع قواعد في الرياضيات و القواعد المخزنة في قوائم واحدة قد تستخدم:

a = {"Badger" -> 5, "Bird" -> 1, "Fox" -> 3, "Frog" -> 2, "Wolf" -> 4};

Answer 20

ما رأيك

public static <A> A getRandomElement(Collection<A> c, Random r) {
  return new ArrayList<A>(c).get(r.nextInt(c.size()));
}

Answer 21

هذا مطابق الإجابة المقبولة (Khoth) ، ولكن مع غير الضرورية size و i المتغيرات إزالتها.

    int random = new Random().nextInt(myhashSet.size());
    for(Object obj : myhashSet) {
        if (random-- == 0) {
            return obj;
        }
    }

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

Answer 22

للأسف, هذا لا يمكن القيام به بكفاءة (أفضل من O(n)) في أي من المكتبة القياسية مجموعة الحاويات.

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

import random

class Node:
    def __init__(self, object):
        self.object = object
        self.value = hash(object)
        self.size = 1
        self.a = self.b = None

class RandomSet:
    def __init__(self):
        self.top = None

    def add(self, object):
        """ Add any hashable object to the set.
            Notice: In this simple implementation you shouldn't add two
                    identical items. """
        new = Node(object)
        if not self.top: self.top = new
        else: self._recursiveAdd(self.top, new)
    def _recursiveAdd(self, top, new):
        top.size += 1
        if new.value < top.value:
            if not top.a: top.a = new
            else: self._recursiveAdd(top.a, new)
        else:
            if not top.b: top.b = new
            else: self._recursiveAdd(top.b, new)

    def pickRandom(self):
        """ Pick a random item in O(log2) time.
            Does a maximum of O(log2) calls to random as well. """
        return self._recursivePickRandom(self.top)
    def _recursivePickRandom(self, top):
        r = random.randrange(top.size)
        if r == 0: return top.object
        elif top.a and r <= top.a.size: return self._recursivePickRandom(top.a)
        return self._recursivePickRandom(top.b)

if __name__ == '__main__':
    s = RandomSet()
    for i in [5,3,7,1,4,6,9,2,8,0]:
        s.add(i)

    dists = [0]*10
    for i in xrange(10000):
        dists[s.pickRandom()] += 1
    print dists

لدي [995, 975, 971, 995, 1057, 1004, 966, 1052, 984, 1001] كما الناتج, لذا توزيع طبقات جيدة.

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

Answer 23

في جافا 8:

static <E> E getRandomSetElement(Set<E> set) {
    return set.stream().skip(new Random().nextInt(set.size())).findFirst().orElse(null);
}

Answer 24

PHP باستخدام MT:

$items_array = array("alpha", "bravo", "charlie");
$last_pos = count($items_array) - 1;
$random_pos = mt_rand(0, $last_pos);
$random_item = $items_array[$random_pos];

Answer 25

للمتعة كتبت RandomHashSet على أساس رفض أخذ العينات.انها قليلا hacky منذ HashMap لا يسمح لنا الوصول إلى هذا الجدول مباشرة ، ولكن يجب أن تعمل على ما يرام.

لا يستخدم أي ذاكرة إضافية ، بحث الوقت O(1) المطفأة.(لأن جافا HashTable كثيفة).

class RandomHashSet<V> extends AbstractSet<V> {
    private Map<Object,V> map = new HashMap<>();
    public boolean add(V v) {
        return map.put(new WrapKey<V>(v),v) == null;
    }
    @Override
    public Iterator<V> iterator() {
        return new Iterator<V>() {
            RandKey key = new RandKey();
            @Override public boolean hasNext() {
                return true;
            }
            @Override public V next() {
                while (true) {
                    key.next();
                    V v = map.get(key);
                    if (v != null)
                        return v;
                }
            }
            @Override public void remove() {
                throw new NotImplementedException();
            }
        };
    }
    @Override
    public int size() {
        return map.size();
    }
    static class WrapKey<V> {
        private V v;
        WrapKey(V v) {
            this.v = v;
        }
        @Override public int hashCode() {
            return v.hashCode();
        }
        @Override public boolean equals(Object o) {
            if (o instanceof RandKey)
                return true;
            return v.equals(o);
        }
    }
    static class RandKey {
        private Random rand = new Random();
        int key = rand.nextInt();
        public void next() {
            key = rand.nextInt();
        }
        @Override public int hashCode() {
            return key;
        }
        @Override public boolean equals(Object o) {
            return true;
        }
    }
}

Answer 26

يمكنك أيضا نقل مجموعة إلى مجموعة استخدام صفيف فإنه من المحتمل أن تعمل على نطاق صغير أرى حلقة في معظم صوت الجواب O(n) على أي حال

Object[] arr = set.toArray();

int v = (int) arr[rnd.nextInt(arr.length)];

Answer 27

إذا كنت حقا ترغب فقط في اختيار "أي" كائن من Set, دون أي ضمانات على العشوائية ، الأسهل هو أخذ الأول عاد من التكرار.

    Set<Integer> s = ...
    Iterator<Integer> it = s.iterator();
    if(it.hasNext()){
        Integer i = it.next();
        // i is a "random" object from set
    }

Answer 28

أسهل مع جافا 8 هو:

outbound.stream().skip(n % outbound.size()).findFirst().get()

حيث n هو عدد صحيح عشوائي.بالطبع هو من أقل أداء من ذلك مع for(elem: Col)

Answer 29

عامة الحل باستخدام Khoth الجواب كنقطة انطلاق.

/**
 * @param set a Set in which to look for a random element
 * @param <T> generic type of the Set elements
 * @return a random element in the Set or null if the set is empty
 */
public <T> T randomElement(Set<T> set) {
    int size = set.size();
    int item = random.nextInt(size);
    int i = 0;
    for (T obj : set) {
        if (i == item) {
            return obj;
        }
        i++;
    }
    return null;
}

Answer 30

إذا كان حجم مجموعة ليست كبيرة ثم باستخدام المصفوفات هذا يمكن القيام به.

int random;
HashSet someSet;
<Type>[] randData;
random = new Random(System.currentTimeMillis).nextInt(someSet.size());
randData = someSet.toArray();
<Type> sResult = randData[random];