Si j'ai un tableau:
[] [1] [2] [3] [1,2] [2,3] [1,2,3]
5 Réponses :
Vous pouvez générer des nombres aléatoires, les convertir en binaires et choisir les éléments de votre tableau d'origine où les bits étaient 1. Voici une implémentation de ce type de monkey pour la catégorie usage: généralement cela ne fonctionne pas si mal, c'est o (n * m) où n est le nombre de Sous-ensembles que vous voulez et m est la longueur de la matrice. TRAY
a.select {|element| rand(2) == 0 }
For each element, a coin is flipped. If heads ( == 0), then it is selected.
Sample (Rand * A.Size) produit des sous-ensembles entre 0 et A.SIZE - 1 de longueur. Si vous désirez exclure l'ensemble vide et inclure la superset, échantillon (rand (A.Size) + 1) .
J'ai utilisé rand (A.Size + 1) et il semble produire à la fois le sous-ensemble vide [] et le sous-ensemble A . Il peut donc produire tous les sous-ensembles possibles de A .
Notez que tableau # échantillon est disponible dans Ruby 1.9+
Ce n'est pas une distribution uniforme sur le jeu d'énergie de A , puisqu'il choisit d'abord une longueur puis un échantillon de cette longueur. Dans le jeu d'énergie de A , il existe clairement beaucoup plus de jeu de longueur 2 que de longueur a.length !
@Albertsantini je suis d'accord avec vous. J'ai changé ma réponse.
Je pense que la monnaie bascule va bien.
ar = ('a'..'j').to_a
p ar.select{ rand(2) == 0 }
Allez juste de l'avant avec votre idée originale "Coin Flowing". Il échantillonne uniformément l'espace des possibilités.
Ça vous semble être biaisé vers le "milieu", mais c'est parce que le nombre de possibilités est le plus grand dans le "milieu". Pensez-y: il n'y a qu'une possibilité avec aucun élément, et seulement 1 avec tous les éléments. Il existe n possibilités avec 1 élément et N possibilités avec des éléments (N-1). Comme le nombre d'éléments choisis se rapproche de (N / 2), le nombre de possibilités augmente très rapidement.
a.select {| élément | rand (2) == 0}
a.select {| _ | Rand (2) .zero? } ;-)
Un moyen de sélectionner un élément aléatoire à partir du jeu d'alimentation est le suivant:
my_array = ('a'..'z').to_a
power_set_size = 2 ** my_array.length
random_subset = rand(power_set_size)
subset = []
random_subset.to_i(2).chars.each_with_index do |bit, corresponding_element|
subset << my_array[corresponding_element] if bit == "1"
end
Je viens de remarquer que Michael Kohl a posté une solution similaire, ce qui est probablement mieux. Il utilise des opérations de bits réelles et vous permet également de demander plus d'un sous-ensemble.
Je suppose que
a ne sera pas un tableau d'entiers?Non, c'est une gamme de cordes dans mon exemple actuel.