सेट

Question

से एक यादृच्छिक तत्व चुनना मैं एक सेट से यादृच्छिक तत्व कैसे चुनूं? मैं जावा में हैशसेट या लिंक्ड हैशसेट से यादृच्छिक तत्व चुनने में विशेष रूप से रूचि रखता हूं। अन्य भाषाओं के लिए समाधान भी स्वागत है।

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

जब से तुम ने कहा, "अन्य भाषाओं के लिए समाधान का भी स्वागत है", यहां अजगर के लिए संस्करण है:

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

Answer 3

जावा में:

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

कर सकते हैं केवल आपके नहीं सेट/सरणी का आकार/लंबाई प्राप्त करें, 0 और आकार/लंबाई के बीच यादृच्छिक संख्या उत्पन्न करें, फिर उस तत्व को कॉल करें जिसका सूचकांक उस नंबर से मेल खाता है? हैशसेट में एक .size() विधि है, मुझे पूरा यकीन है।

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

Mersenne ट्विस्टर कार्यों में बेहतर हैं लेकिन वहाँ PHP में array_rand का कोई मीट्रिक टन के बराबर है: -

psuedocode में

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

Answer 5

पीएचपी, यह मानते हुए "सेट" एक सरणी है।

Answer 6

पीएचपी, मीट्रिक टन का उपयोग कर:

$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

जावास्क्रिप्ट समाधान;)

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 8

एक कुछ हद तक संबंधित था क्या तुम जानते:

रहे हैंमें उपयोगी तरीकेपूरे संग्रह को शफल करने के लिए: Collections.shuffle(List<?>) और Collections.shuffle(List<?> list, Random rnd)।

Answer 9

पर्ल 5

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

यहाँ एक तरह से यह करने के लिए है।

Answer 10

Icon एक सेट के प्रकार और एक यादृच्छिक तत्व ऑपरेटर, एकल "?", तो अभिव्यक्ति

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

1 और 5 के बीच एक यादृच्छिक संख्या का उत्पादन करेगा है।

यादृच्छिक बीज जब एक कार्यक्रम चलाया जाता है 0 पर आरंभ नहीं हो जाता है, इसलिए प्रत्येक रन उपयोग randomize()

Answer 11

सी # में पर अलग अलग परिणाम प्राप्त होने की

 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

में तुतलाना

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

Answer 13

यदि आप जावा में ऐसा करना चाहते हैं, तो आपको तत्वों को किसी प्रकार के यादृच्छिक-अभिगम संग्रह (जैसे एक ArrayList) में कॉपी करने पर विचार करना चाहिए)। चूंकि, जब तक आपका सेट छोटा न हो, चयनित तत्व तक पहुंच महंगा हो (ओ (एन) के बजाय ओ (एन))। [ed: सूची प्रति भी ओ (एन)]

वैकल्पिक रूप से, आप एक और सेट कार्यान्वयन की तलाश कर सकते हैं जो आपकी आवश्यकताओं से अधिक निकटता से मेल खाता है। कॉमन्स संग्रह से ListOrderedSet आशाजनक लग रहा है।

Answer 14

Clojure समाधान:

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

Answer 15

दुर्भाग्य से, यह कुशलतापूर्वक स्टैंडर्ड लाइब्रेरी में से किसी में नहीं किया जा सकता (बेहतर हे (एन) की तुलना में) कंटेनर की स्थापना की।

यह अजीब है, क्योंकि हैश सेट के साथ-साथ बाइनरी सेट में यादृच्छिक पिक फ़ंक्शन जोड़ना बहुत आसान है। हैश सेट को स्पैस करने के लिए, आप हिट होने तक यादृच्छिक प्रविष्टियों को आजमा सकते हैं। एक बाइनरी पेड़ के लिए, आप अधिकतम ओ (लॉग 2) चरणों के साथ बाएं या दाएं उपट्री के बीच यादृच्छिक रूप से चुन सकते हैं। मैं नीचे बाद में का एक डेमो को क्रियान्वित किया है:

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] आउटपुट के रूप में है, तो वितरण तेजी अच्छा।

मैंने अपने लिए एक ही समस्या के साथ संघर्ष किया है, और मैंने अभी तक फैसला नहीं किया है कि इस अधिक कुशल पिक के प्रदर्शन लाभ को एक पायथन आधारित संग्रह का उपयोग करने के ऊपरी हिस्से के लायक है। मैं निश्चित रूप से इसे परिष्कृत कर सकता हूं और इसे सी में अनुवाद कर सकता हूं, लेकिन आज मेरे लिए यह बहुत अधिक काम है :)

Answer 16

सी ++। यह उचित रूप से त्वरित होना चाहिए, क्योंकि इसे पूरे सेट पर पुनरावृत्ति की आवश्यकता नहीं है, या इसे सॉर्ट करना आवश्यक नहीं है। यह सबसे आधुनिक कंपाइलर्स के साथ बॉक्स से बाहर काम करना चाहिए, मानते हैं कि वे tr1 का समर्थन करते हैं। यदि नहीं, तो आपको बूस्ट का उपयोग करने की आवश्यकता हो सकती है।

Boost docs यह समझाने के लिए यहां सहायक हैं, भले ही आप बूस्ट का उपयोग न करें।

चाल इस तथ्य का उपयोग करना है कि डेटा बाल्टी में बांटा गया है, और जल्दी से यादृच्छिक रूप से चुनी गई बाल्टी (उपयुक्त संभावना के साथ) की पहचान करने के लिए है।

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

इस सूत्र को पढ़ने के बाद, सबसे अच्छा मैं लिख सकता है:

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

जावा के लिए तेजी से समाधान एक 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 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

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

Answer 21

कैसे के बारे में सिर्फ

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

Answer 22

मस्ती के लिए मैं अस्वीकृति नमूनाकरण के आधार पर एक RandomHashSet लिखा था। यह थोड़ा हैकी है, क्योंकि हैश मैप हमें सीधे इसकी तालिका तक पहुंचने नहीं देता है, लेकिन इसे ठीक काम करना चाहिए।

यह किसी भी अतिरिक्त मेमोरी का उपयोग नहीं करता है, और लुकअप समय ओ (1) amortized है। (क्योंकि जावा हैशटेबल घना है)।

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

इस से भी तेज है के लिए-प्रत्येक स्वीकार किए जाते हैं जवाब में पाश:

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% की वृद्धि देखी, लेकिन वाईएमएमवी। (इसके अलावा, यह अतिरिक्त रिटर्न स्टेटमेंट जोड़ने के बिना संकलित करता है।)

ध्यान दें कि यह कोड (और अधिकांश अन्य उत्तरों) किसी भी संग्रह पर लागू नहीं किया जा सकता है, न केवल सेट करें। सामान्य विधि के रूप में:

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

आप भी यह शायद छोटे पैमाने पर काम करेंगे सरणी उपयोग सरणी को सेट मैं देख हस्तांतरण कर सकते हैं सबसे मतदान जवाब में पाश के लिए हे (एन) वैसे भी

Object[] arr = set.toArray(); 

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

है

Answer 25

यह स्वीकार्य उत्तर (खोथ) के समान है, लेकिन अनावश्यक size और i चर के साथ हटा दिया गया है।

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

दो aforementioned चर के साथ दूर कर रही है हालांकि, इसके बाद के संस्करण समाधान अभी भी बनी हुई है क्योंकि हम यादृच्छिक यादृच्छिक पर भरोसा कर रहे हैं (यादृच्छिक रूप से चयनित सूचकांक से शुरु करके) प्रत्येक यात्रा से अधिक 0 की ओर ही घटती है।

Answer 26

उपरोक्त समाधान विलंबता के मामले में बोलते हैं लेकिन प्रत्येक इंडेक्स का चयन होने की समान संभावना की गारंटी नहीं देता है।
यदि इसे माना जाना चाहिए, तो जलाशय नमूनाकरण का प्रयास करें।http://en.wikipedia.org/wiki/Reservoir_sampling।
संग्रह। शफल() (जैसा कि कुछ द्वारा सुझाया गया है) एक ऐसे एल्गोरिदम का उपयोग करता है।

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

के साथ कम प्रदर्शन का है जो खोथ के उत्तर का उपयोग शुरुआती बिंदु के रूप में करते हुए एक सामान्य समाधान है।

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

यदि सेट आकार बड़ा नहीं है तो Arrays का उपयोग करके यह किया जा सकता है।

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

Answer 31

Guava के साथ हम एक छोटे से 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

बस इस यहाँ छोड़ना चाहते हैं:

random.choice(your_set) 

साँप कोई आपत्ति नहीं है।

Answer 33

आप एक 3 पार्टी पुस्तकालय कोई आपत्ति नहीं है, Utils पुस्तकालय एक IterableUtils एक randomFrom (Iterable iterable) विधि है कि एक सेट लेने के लिए और से यह

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

यह एक यादृच्छिक तत्व वापस आ जाएगी है कि है मेवेन सेंट्रल रिपोजिटरी में है:

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