Chọn một phần tử ngẫu nhiên từ một tập hợp

Question

Làm cách nào để chọn một phần tử ngẫu nhiên từ một tập hợp? Tôi đặc biệt quan tâm đến việc chọn một phần tử ngẫu nhiên từ một số HashSet hoặc LinkedHashSet, trong Java. Các giải pháp cho các ngôn ngữ khác cũng được hoan nghênh.

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

Vì bạn nói: "Giải pháp cho các ngôn ngữ khác cũng được hoan nghênh", đây là phiên bản dành cho Python:

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

Answer 3

Trong Java:

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 4

Có thể bạn không chỉ lấy kích thước/chiều dài của tập hợp/mảng, tạo ra một số ngẫu nhiên giữa 0 và kích thước/chiều dài, sau đó gọi phần tử có chỉ mục khớp với số đó? HashSet có một phương thức .size(), tôi khá chắc chắn.

Trong psuedocode -

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

Answer 5

PHP, giả sử "set" là một mảng:

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

Các chức năng Mersenne Twister là tốt hơn nhưng không có MT tương đương với array_rand trong PHP.

Answer 6

PHP, sử dụng 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 7

giải pháp Javascript;)

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

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

Hoặc cách khác:

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

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

Answer 8

Một phần nào liên quan Bạn có biết:

Có phương pháp hữu ích trong java.util.Collections để xáo trộn toàn bộ bộ sưu tập: Collections.shuffle(List<?>) và Collections.shuffle(List<?> list, Random rnd).

Answer 9

Perl 5

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

Dưới đây là một cách để làm điều đó.

Answer 10

Icon có một kiểu thiết lập và điều hành một phần tử ngẫu nhiên, nhất nguyên "?", Vì vậy biểu thức

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

sẽ tạo ra một số ngẫu nhiên từ 1 đến 5.

Hạt giống ngẫu nhiên được khởi tạo 0 khi một chương trình được chạy, vì vậy tạo ra kết quả khác nhau trên mỗi lần sử dụng chạy randomize()

Answer 11

Trong 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 12

Trong lisp

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

Answer 13

Nếu bạn muốn làm điều đó trong Java, bạn nên xem xét sao chép các phần tử vào một số loại bộ sưu tập truy cập ngẫu nhiên (chẳng hạn như một ArrayList). Bởi vì, trừ khi thiết lập của bạn là nhỏ, truy cập vào phần tử đã chọn sẽ tốn kém (O (n) thay vì O (1)). [ed: bản sao danh sách cũng là O (n)]

Ngoài ra, bạn có thể tìm một triển khai Bộ khác phù hợp hơn với yêu cầu của bạn. ListOrderedSet từ Bộ sưu tập của Commons trông đầy hứa hẹn.

Answer 14

Clojure giải pháp:

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

Answer 15

Thật không may, điều này không thể được thực hiện một cách hiệu quả (tốt hơn so với O (n)) trong bất kỳ bộ thư viện chuẩn thiết container.

Điều này thật kỳ quặc, vì việc thêm hàm chọn ngẫu nhiên vào bộ băm cũng như tập hợp nhị phân rất dễ dàng. Trong một bộ băm không thưa thớt, bạn có thể thử các mục nhập ngẫu nhiên, cho đến khi bạn nhận được một lần truy cập. Đối với cây nhị phân, bạn có thể chọn ngẫu nhiên giữa cây con trái hoặc phải, với tối đa các bước O (log2). Tôi đã thực hiện một bản demo của sau này dưới đây:

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 

tôi [995, 975, 971, 995, 1057, 1004, 966, 1052, 984, 1001] là đầu ra, vì vậy vỉa phân phối tốt.

Tôi đã vật lộn với cùng một vấn đề cho bản thân mình, và tôi vẫn chưa quyết định thời tiết hiệu suất đạt được của lựa chọn này hiệu quả hơn là giá trị trên không của việc sử dụng một bộ sưu tập dựa trên python. Tất nhiên tôi có thể tinh chỉnh nó và dịch nó sang C, nhưng đó là quá nhiều công việc cho tôi hôm nay :)

Answer 16

C++. Điều này nên được hợp lý nhanh chóng, vì nó không yêu cầu lặp lại trên toàn bộ thiết lập, hoặc phân loại nó. Điều này sẽ làm việc ra khỏi hộp với các trình biên dịch hiện đại nhất, giả sử chúng hỗ trợ tr1. Nếu không, bạn có thể cần phải sử dụng Boost.

Boost docs hữu ích ở đây để giải thích điều này, ngay cả khi bạn không sử dụng Boost.

Bí quyết là sử dụng dữ liệu đã được chia thành các nhóm và để nhanh chóng xác định một nhóm được chọn ngẫu nhiên (với xác suất thích hợp).

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

sau khi đọc chủ đề này, tốt nhất tôi có thể viết là:

static Random random = new Random(System.currentTimeMillis()); 
public static <T> T randomChoice(T[] choices) 
{ 
    int index = random.nextInt(choices.length); 
    return choices[index]; 
} 

Answer 18

giải pháp nhanh cho Java sử dụng một ArrayList và HashMap: [nguyên tố -> index].

Động lực: Tôi cần một tập hợp các mục có thuộc tính RandomAccess, đặc biệt là để chọn một mục ngẫu nhiên từ bộ này (xem phương pháp pollRandom). Điều hướng ngẫu nhiên trong cây nhị phân không chính xác: cây không được cân bằng hoàn hảo, điều này sẽ không dẫn đến sự phân bố đồng đều.

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 19

Trong Mathematica:

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

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

Hoặc, trong các phiên bản gần đây, chỉ cần:

RandomChoice[a] 

---

này đã nhận được một xuống bỏ phiếu, có lẽ vì nó thiếu lời giải thích, vì vậy đây một là:

Random[] tạo ra một pseudorandom float giữa 0 và 1. Điều này được nhân với độ dài của danh sách và sau đó chức năng trần được sử dụng để làm tròn đến số nguyên tiếp theo. Chỉ số này sau đó được chiết xuất từ ​​a.

Kể từ khi chức năng bảng băm thường được thực hiện với quy tắc trong Mathematica, và các quy tắc được lưu trữ trong danh sách, người ta có thể sử dụng:

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

Answer 20

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

Answer 21

Làm thế nào về chỉ

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

Answer 22

Đối với niềm vui tôi đã viết một RandomHashSet dựa trên mẫu từ chối. Đó là một chút hacky, kể từ HashMap không cho phép chúng tôi truy cập vào bảng của nó trực tiếp, nhưng nó sẽ làm việc tốt.

Nó không sử dụng bất kỳ bộ nhớ bổ sung nào, và thời gian tra cứu là O (1) được khấu hao. (Bởi vì java HashTable là dày đặc).

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 23

Đây là nhanh hơn so với for-each vòng lặp trong câu trả lời được chấp nhận:

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

Các for-each cấu trúc gọi Iterator.hasNext() trên mỗi vòng lặp, nhưng kể từ khi index < set.size(), kiểm tra đó là chi phí không cần thiết. Tôi thấy tốc độ tăng 10-20%, nhưng YMMV. (Ngoài ra, điều này biên dịch mà không cần phải thêm câu trả lại bổ sung.)

Lưu ý rằng mã này (và hầu hết các câu trả lời khác) có thể được áp dụng cho bất kỳ Bộ sưu tập nào chứ không chỉ là Đặt. Trong form method generic:

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 24

bạn cũng có thể chuyển các thiết lập để sử dụng mảng mảng nó có lẽ sẽ làm việc trên quy mô nhỏ tôi thấy các vòng lặp for trong câu trả lời đã bỏ phiếu nhất là O (n) anyway

Object[] arr = set.toArray(); 

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

Answer 25

Điều này giống với câu trả lời được chấp nhận (Khoth), nhưng với các biến số size và i không cần thiết đã bị xóa.

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

Mặc dù với việc từ bỏ hai biến nói trên, giải pháp trên vẫn ngẫu nhiên vì chúng ta đang dựa vào ngẫu nhiên (bắt đầu từ một chỉ số được lựa chọn ngẫu nhiên) để giảm giá trị bản thân về phía 0 qua mỗi lần lặp.

Answer 26

Giải pháp ở trên nói về độ trễ nhưng không đảm bảo xác suất bằng nhau của từng chỉ mục được chọn.
Nếu cần được xem xét, hãy thử lấy mẫu hồ chứa.http://en.wikipedia.org/wiki/Reservoir_sampling.
Collections.shuffle() (như được đề xuất bởi một số ít) sử dụng một thuật toán như vậy.

Answer 27

Nếu bạn thực sự chỉ muốn chọn đối tượng "bất kỳ" từ Set, không có bất kỳ sự đảm bảo nào về tính ngẫu nhiên, cách dễ nhất là lấy đối tượng đầu tiên được trả về bởi trình lặp.

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

Answer 28

Cách dễ dàng nhất với Java 8 là:

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

nơi n là một số nguyên ngẫu nhiên. Tất nhiên, hiệu suất của nó kém hiệu quả hơn với for(elem: Col)

Answer 29

Một giải pháp chung sử dụng câu trả lời của Khoth làm điểm bắt đầu.

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

Nếu kích thước thiết lập không lớn thì bằng cách sử dụng Mảng này có thể được thực hiện.

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

Answer 31

Với Guava chúng ta có thể làm tốt hơn một chút so với câu trả lời của Khoth:

public static E random(Set<E> set) { 
    int index = random.nextInt(set.size(); 
    if (set instanceof ImmutableSet) { 
    // ImmutableSet.asList() is O(1), as is .get() on the returned list 
    return set.asList().get(index); 
    } 
    return Iterables.get(set, index); 
} 

Answer 32

Chỉ muốn để lại điều này ở đây:

random.choice(your_set) 

không nhớ con rắn.

Answer 33

Nếu bạn không nhớ một thư viện của bên thứ 3, thư viện Utils có IterableUtils rằng có một phương pháp randomFrom (Iterable iterable) rằng sẽ mất một Set và trả về một yếu tố ngẫu nhiên từ nó

Set<Object> set = new HashSet<>(); 
set.add(...); 
... 
Object random = IterableUtils.randomFrom(set); 

Nó nằm trong Kho lưu trữ trung tâm của Maven tại:

<dependency> 
    <groupId>com.github.rkumsher</groupId> 
    <artifactId>utils</artifactId> 
    <version>1.0</version> 
</dependency>