lundi 10 octobre 2022

Algorithm for Randomly selecting k elements from n with Some Elements Belonging to Disjoint Pairs

I need to randomly select k elements from a list of n. Let's say that:

n = (1,2,3,4,5,6,7,8,9,10)

and I want to randomly chose k = 4 elements and arrange them in random order. I am using Perl, so I could easily do this with:

@ord = ($o1,$o2,$o3,$o4) = pick(4,(1..10));

However, the complication is for certain pairs (not all pairs), for example, if 3 is chosen then 4 should not be chosen (I'll call these disjoint pairs). However, if 1 is chosen, the likelihood of any other element being chosen should not be affected (1 is not part of a disjoint pair). In other words, the selection of certain elements is independent of the selection of other elements, but the selection of 1 of the disjoint pairs should exclude the selection of the other.

So, let's say (3,4) and (7,8) are the only disjoint pairs. Can someone suggest an efficient algorithm that randomly selects k = 4 elements with an equal chance of selection from the list (1,2,3,4,5,6,7,8,9,10) unless one of the disjoint elements is selected in which case the other element in the disjoin pair would be excluded from subsequent selection?




Aucun commentaire:

Enregistrer un commentaire