Escolhendo um elemento aleatório de um conjunto

Como escolho um elemento aleatório de um conjunto? Estou particularmente interessado em escolher um elemento aleatório 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 métodos úteis java.util.Collectionspara embaralhar coleções inteiras: Collections.shuffle(List<?>)e Collections.shuffle(List<?> list, Random rnd).

Solução rápida para Java usando an ArrayListe a HashMap: [elemento -> índice].

Motivação: eu precisava de um conjunto de itens com RandomAccesspropriedades, especialmente para escolher um item aleatório do conjunto (consulte o pollRandommétodo). A navegação aleatória em uma árvore binária não é precisa: as árvores não são perfeitamente equilibradas, o 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();
    }
}

Isso é mais rápido que o loop for-each 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 construção for-each chama Iterator.hasNext()cada loop, mas desde então index < set.size(), essa verificação é desnecessária. Eu vi um aumento de 10-20% na velocidade, mas YMMV. (Além disso, isso é compilado sem a necessidade de adicionar uma declaração de retorno extra.)

Observe que esse código (e a maioria das outras respostas) pode ser aplicado a qualquer coleção, não apenas a conjunto. Na forma genérica do método:

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

Se você quiser fazer isso em Java, considere copiar os elementos em algum tipo de coleção de acesso aleatório (como um ArrayList). Porque, a menos que seu conjunto seja pequeno, o acesso ao elemento selecionado será caro (O (n) em vez de O (1)). [ed: list copy também é O (n)]

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

No Java 8:

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

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

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

Isso é idêntico à resposta aceita (Khoth), mas com o desnecessário sizee as ivariáveis ​​removidas.

    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 ainda permanece aleatória, porque confiamos no aleatório (começando em um índice selecionado aleatoriamente) para diminuir 0cada vez mais a iteração.

Solução Clojure:

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

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 classificação. Isso deve funcionar imediatamente com os compiladores mais modernos, assumindo que eles suportem tr1 . Caso contrário, pode ser necessário usar o Boost.

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

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

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

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

Como você disse que "soluções para outros idiomas também são bem-vindas", aqui está a versão do Python:

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

Você não pode simplesmente obter o tamanho / comprimento do conjunto / matriz, gerar um número aleatório entre 0 e o tamanho / comprimento e 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];
}

PHP, assumindo "set" é uma matriz:

$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á equivalente em MT ao array_rand no PHP.

O ícone possui um tipo de conjunto e um operador de elemento aleatório, unário "?", Portanto, a expressão

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

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

A semente aleatória é inicializada como 0 quando um programa é executado, para produzir resultados diferentes em cada execução. 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 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 um voto negativo, talvez por falta de explicação, então aqui está:

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

Como a funcionalidade da tabela de hash é frequentemente feita 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};

Que tal apenas

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

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

Ele não usa memória extra e o tempo de pesquisa é O (1) amortizado. (Como o java HashTable é denso).

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

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 tem menos desempenho do que com ofor(elem: Col)

Com a Goiaba , podemos fazer um pouco melhor do que a resposta de 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);
}

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

você também pode transferir o conjunto para o array usar o array, provavelmente ele funcionará em pequena escala.

Object[] arr = set.toArray();

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

Se você realmente deseja selecionar "qualquer" objeto do Set, sem nenhuma garantia de aleatoriedade, o mais fácil é obter 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
    }

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

Infelizmente, isso não pode ser feito com eficiência (melhor que O (n)) em qualquer um dos contêineres da Biblioteca Padrão.

Isso é estranho, pois é muito fácil adicionar uma função de seleção aleatória a conjuntos de hash e também a conjuntos binários. Em um conjunto de hash não esparso, você pode tentar entradas aleatórias até receber um hit. Para uma árvore binária, você pode escolher aleatoriamente entre a subárvore esquerda ou direita, com no máximo O (log2) etapas. Implementei uma demonstração dos itens abaixo 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 parece boa.

Eu lutei com o mesmo problema para mim e ainda não decidi enfrentar o ganho de desempenho dessa escolha mais eficiente que vale a pena a sobrecarga do uso de uma coleção baseada em python. É claro que eu poderia refiná-lo e traduzi-lo para C, mas isso é muito trabalho para mim hoje :)