Escolhendo um elemento random de um conjunto

Como eu escolho um elemento random de um conjunto? Estou particularmente interessado em escolher um elemento random de um HashSet ou LinkedHashSet, em Java. Soluções para outros idiomas também são bem vindas.

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

Um pouco relacionado Você sabia:

Existem methods úteis em java.util.Collections para embaralhar collections inteiras: Collections.shuffle(List) E Collections.shuffle(List list, Random rnd) .

Solução rápida para Java usando um ArrayList e um HashMap : [element -> index].

Motivação: Eu precisava de um conjunto de itens com propriedades RandomAccess , especialmente para escolher um item random do conjunto (veja o método pollRandom ). A navegação aleatória em uma tree binária não é precisa: as trees não são perfeitamente balanceadas, o que não levaria a uma distribuição uniforme.

 public class RandomSet extends AbstractSet { List dta = new ArrayList(); Map idx = new HashMap(); public RandomSet() { } public RandomSet(Collection 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 id 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 iterator() { return dta.iterator(); } } 

Isso é mais rápido que o loop for-each na resposta aceita:

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

A construção for each chama Iterator.hasNext() em cada loop, mas, como index < set.size() , essa verificação é desnecessária. Eu vi um aumento de 10-20% na velocidade, mas YMMV. (Além disso, isso compila sem ter que adicionar uma instrução de retorno extra.)

Note que este código (e a maioria das outras respostas) pode ser aplicado a qualquer coleção, não apenas a Set. Em forma de método genérico:

 public static  E choice(Collection 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) coll).get(index); } else { Iterator iter = coll.iterator(); for (int i = 0; i < index; i++) { iter.next(); } return iter.next(); } } 

Se você quiser fazer isso em Java, você deve considerar copiar os elementos em algum tipo de coleção de access random (como um ArrayList). Porque, a menos que seu conjunto seja pequeno, acessar o elemento selecionado será caro (O (n) em vez de O (1)). [ed: cópia da lista também é O (n)]

Como alternativa, você pode procurar outra implementação de conjunto que corresponda melhor aos seus requisitos. O ListOrderedSet da Commons Collections parece promissor.

Em Java:

 Set set = new LinkedHashSet(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())]); } 
 List asList = new ArrayList(mySet); Collections.shuffle(asList); return asList.get(0); 

Solução Clojure:

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

Você não pode simplesmente pegar o tamanho / comprimento do conjunto / array, gerar um número random entre 0 e o tamanho / comprimento, então chamar o elemento cujo índice corresponde a esse número? HashSet tem um método .size (), tenho certeza.

Em psuedocode –

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

Perl 5

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

Aqui está uma maneira de fazer isso.

C ++. Isso deve ser razoavelmente rápido, pois não requer iteração em todo o conjunto ou sorting. Isso deve funcionar fora da checkbox com a maioria dos compiladores modernos, assumindo que eles suportam tr1 . Se não, você pode precisar usar o Boost.

Os documentos do Boost são úteis aqui para explicar isso, mesmo que você não use o Boost.

O truque é aproveitar o fato de que os dados foram divididos em intervalos e identificar rapidamente um intervalo escolhido aleatoriamente (com a probabilidade apropriada).

 //#include  //using namespace boost; #include  using namespace std::tr1; #include  #include  #include  using namespace std; int main() { unordered_set 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::const_local_iterator l = u.begin(b); while(x>0) { l++; assert(l!=u.end(b)); x--; } cout << "random item is " << *l << ". "; cout << endl; } } 

A solução acima fala em termos de latência, mas não garante a probabilidade igual de cada índice ser selecionado.
Se isso precisar ser considerado, tente a amostragem do reservatório. http://en.wikipedia.org/wiki/Reservoir_sampling .
Collections.shuffle () (como sugerido por alguns) usa um desses algoritmos.

Desde que você disse “Soluções para outras linguagens também são bem vindas”, aqui está a versão para Python:

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

PHP, assumindo que “set” é um array:

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

As funções do Mersenne Twister são melhores, mas não há MT equivalente a array_rand no PHP.

O ícone tem um tipo de conjunto e um operador de elemento random, unário “?”, Portanto, a expressão

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

irá produzir um número random entre 1 e 5.

A semente aleatória é inicializada para 0 quando um programa é executado, portanto, para produzir resultados diferentes em cada execução use randomize()

Em 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"]); 

Solução de JavaScript;)

 function choose (set) { return set[Math.floor(Math.random() * set.length)]; } var set = [1, 2, 3, 4], rand = choose (set); 

Ou alternativamente:

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

Em lisp

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

No Mathematica:

 a = {1, 2, 3, 4, 5} a[[ ⌈ Length[a] Random[] ⌉ ]] 

Ou, nas versões recentes, simplesmente:

 RandomChoice[a] 

Isso recebeu uma baixa, talvez porque não tem explicação, então aqui está uma:

Random[] gera uma flutuação pseudo-aleatória entre 0 e 1. Isso é multiplicado pelo comprimento da lista e, em seguida, a function de teto é usada para arredondar para o próximo inteiro. Este índice é então extraído de a .

Como a funcionalidade da tabela de hash é frequentemente executada com regras no Mathematica, e as regras são armazenadas em listas, pode-se usar:

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

Isso é idêntico à resposta aceita (Khoth), mas com o size desnecessário e as variables i removidas.

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

Embora eliminando as duas variables ​​mencionadas acima, a solução acima ainda permanece aleatória porque estamos nos baseando em random (iniciando em um índice selecionado aleatoriamente) para decrementar a si mesmo em direção a 0 sobre cada iteração.

Infelizmente, isso não pode ser feito com eficiência (melhor que O (n)) em qualquer um dos contêineres do conjunto de bibliotecas padrão.

Isso é estranho, já que é muito fácil adicionar uma function de seleção aleatória a conjuntos de hash, assim como a conjuntos binários. Em um conjunto de hash não esparso, você pode tentar inputs aleatórias, até obter um hit. Para uma tree binária, você pode escolher aleatoriamente entre a subtree esquerda ou direita, com um máximo de etapas O (log2). Eu implementei uma demonstração do mais tardar abaixo:

 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 

Eu tenho [995, 975, 971, 995, 1057, 1004, 966, 1052, 984, 1001] como saída, então a distribuição é boa.

Eu lutei com o mesmo problema por mim mesmo, e ainda não decidi o tempo em que o ganho de desempenho dessa escolha mais eficiente vale a pena usar uma coleção baseada em Python. Eu poderia, claro, refiná-lo e traduzi-lo para C, mas isso é muito trabalho para mim hoje 🙂

No Java 8:

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

PHP, usando o 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]; 

Por diversão eu escrevi um RandomHashSet baseado em amostragem de rejeição. É um pouco hacky, já que o HashMap não nos permite acessar sua tabela diretamente, mas deve funcionar muito bem.

Não usa memory extra, e o tempo de pesquisa é O (1) amortizado. (Porque o java HashTable é denso).

 class RandomHashSet extends AbstractSet { private Map map = new HashMap<>(); public boolean add(V v) { return map.put(new WrapKey(v),v) == null; } @Override public Iterator iterator() { return new Iterator() { 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 { 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; } } } 

você também pode transferir o conjunto para matriz array use ele provavelmente funcionará em pequena escala eu vejo o loop for na resposta mais votada é O (n) de qualquer maneira

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

Se você realmente quer apenas escolher “qualquer” object do Set , sem nenhuma garantia sobre a aleatoriedade, o mais fácil é pegar o primeiro retornado pelo iterador.

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

O mais fácil com o Java 8 é:

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

onde n é um inteiro random. Claro que é de menor desempenho que com o for(elem: Col)

Uma solução genérica usando a resposta de Khoth como ponto de partida.

 /** * @param set a Set in which to look for a random element * @param  generic type of the Set elements * @return a random element in the Set or null if the set is empty */ public  T randomElement(Set 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; } 

Se o tamanho do conjunto não for grande, então, usando Arrays, isso pode ser feito.

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