Escolhendo um elemento aleatório a partir de um conjunto

Question

Como faço para escolher um elemento aleatório de um conjunto? Estou particularmente interessado em escolher um elemento aleatório a partir de um HashSet ou um LinkedHashSet, em Java. Soluções para outras línguas também são bem-vindos.

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

Um pouco relacionado você sabia:

Existem métodos úteis no java.util.Collections para baralhar coleções inteiras: Collections.shuffle(List<?>) e Collections.shuffle(List<?> list, Random rnd) .

Answer 3

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

Motivação: eu precisava de um conjunto de itens com propriedades RandomAccess, especialmente para escolher um item aleatório a partir do conjunto (ver método pollRandom). navegação aleatória em uma árvore binária não é exato:. árvores não são perfeitamente equilibrado, que não levaria a uma distribuição uniforme

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

Isto é mais rápido do que a for-each loop na resposta aceita:

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

A for-each construção chamadas Iterator.hasNext() em cada loop, mas desde index < set.size(), essa verificação é sobrecarga desnecessária. Eu vi um impulso de 10-20% na velocidade, mas YMMV. (Além disso, este 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 toda a coleção, e não apenas informado. Em forma de método genérico:

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

Se você quiser fazê-lo em Java, você deve considerar a copiar os elementos em algum tipo de coleta de acesso aleatório (como um ArrayList). Uma vez que, a menos que o seu conjunto é pequeno, o acesso ao elemento seleccionado será dispendioso (S (n), em vez de O (1)). [Ed: cópia lista também é O (n)]

Como alternativa, você poderia procurar outra implementação Set que corresponda melhor às suas necessidades. A ListOrderedSet de Commons Collections parece promissor.

Answer 6

Em 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 7

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

Answer 8

solução 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]};

Aqui está uma maneira de fazê-lo.

Answer 10

C ++. Este deve ser razoavelmente rápido, uma vez que não requer iteração sobre o conjunto, ou classificando-o. Isso deve funcionar fora da caixa com a maioria dos compiladores modernos, assumindo que eles apoiar tr1 . Se não, você pode precisar usar Boost.

impulso docs são úteis aqui para explicar isso, mesmo se você não usar Boost.

O truque é fazer uso do fato de que os dados foram divididos em baldes, e para identificar rapidamente um balde escolhidos aleatoriamente (com a probabilidade apropriado).

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

Solution acima falar em termos de latência, mas não garante igual probabilidade de cada índice que está sendo selecionado.
Se o que precisa ser considerado, tente amostragem reservatório. http://en.wikipedia.org/wiki/Reservoir_sampling .
Collections.shuffle ( ) (como sugerido por alguns) usa um tal algoritmo.

Answer 12

Uma vez que você disse "Soluções para outras línguas também são bem vindos", aqui está a versão de Python:

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

Answer 13

Você não pode simplesmente obter o tamanho / comprimento do set / matriz, gerar um número aleatório entre 0 e o tamanho / comprimento, em seguida, chamar o elemento cujo índice corresponde esse número? HashSet tem um método .size (), eu tenho certeza.

Em psuedocode -

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

Answer 14

PHP, assumindo que "conjunto" representa uma matriz:

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

As funções de Mersenne Twister são melhores, mas não há nenhum equivalente MT de array_rand em PHP.

Answer 15

Ícone tem um tipo de conjunto e um operador aleatório-elemento, unário " ?", então a expressão

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

irá produzir um número aleatório entre 1 e 5.

A semente aleatória é inicializada para 0 quando um programa é executado, de modo a produzir resultados diferentes em cada randomize() uso run

Answer 16

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

Answer 17

solução

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

Answer 18

Em lisp

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

Answer 19

Em Mathematica:

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

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

Ou, em versões recentes, simplesmente:

RandomChoice[a]

---

Este recebeu um abaixo-voto, talvez porque ela não tem explicação, por isso aqui é:

Random[] gera um flutuador pseudo-aleatório entre 0 e 1. Esta é multiplicado pelo comprimento da lista e, em seguida, a função de limite máximo é utilizado para arredondar para cima para o próximo número inteiro. Este índice é, em seguida, extraiu-se a partir de a.

Uma vez que a funcionalidade de tabela hash é freqüentemente feito com regras em Mathematica, e as regras são armazenadas em listas, pode-se usar:

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

Answer 20

Como apenas cerca de

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

Answer 21

Esta é idêntica à resposta aceita (Khoth), mas com as variáveis ??size e i desnecessários removidos.

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

Apesar de acabar com as duas variáveis ??acima mencionadas, a solução acima continua a ser aleatória porque estamos confiando aleatória (a partir de um índice seleccionado aleatoriamente) para decrementar si para 0 sobre cada iteração.

Answer 22

Infelizmente, isso não pode ser feito de forma eficiente (melhor do que O (n)) em qualquer um dos recipientes set biblioteca padrão.

Isso é estranho, uma vez que é muito fácil de adicionar uma função de escolha aleatória para conjuntos de hash, bem como conjuntos binários. Em um não conjunto de hash escassa, você pode tentar entradas aleatórias, até obter um hit. Para uma árvore binária, você pode escolher aleatoriamente entre a sub-árvore esquerda ou à direita, com um máximo de O (log2) passos. Eu tenho implementado um programa demonstrativo da tarde 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, de modo que a distribuição costuras bom.

Eu tenho lutado com o mesmo problema para mim, e eu ainda não decidi o tempo ganho desta escolha mais eficiente desempenho vale a pena a sobrecarga de usar uma coleção baseada python. Eu poderia de refinar claro que e traduzi-lo para C, mas isso é muito trabalho para mim hoje:)

Answer 23

Em Java 8:

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

Answer 24

PHP, utilizando 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

Para se divertir Eu escrevi um RandomHashSet com base na rejeição de amostragem. É um pouco hacky, desde HashMap não vamos acessá-lo da tabela diretamente, mas deve funcionar muito bem.

Ele não usa qualquer memória extra, e tempo de pesquisa é O (1) amortizado. (Porque java HashTable é densa).

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

Você também pode transferir o conjunto de matriz uso conjunto ele provavelmente irá trabalhar em pequena escala i ver o loop for no mais resposta votado é O (n) de qualquer maneira

Object[] arr = set.toArray();

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

Answer 27

Se você realmente quer apenas para escolher "qualquer" objeto da Set, sem quaisquer garantias sobre a aleatoriedade, o mais fácil é dar o primeiro retornado pelo iterador.

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

Answer 28

O mais fácil com o Java 8 é:

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

onde n é um número inteiro aleatório. Claro que é de menos desempenho do que com o for(elem: Col)

Answer 29

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

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

Se o tamanho do conjunto não é grande, em seguida, usando Arrays isso pode ser feito.

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