확률로 항목을 선택하는 방법은 무엇입니까?

확률로 항목을 선택하는 방법은 무엇입니까?

---

항목 목록이 있습니다. 이러한 각 항목에는 고유 한 확률이 있습니다.

확률에 따라 항목을 선택하는 알고리즘을 제안 할 수 있습니까?

---

따라서 각 항목 저장소에는 상대 확률을 표시하는 숫자가 있습니다. 예를 들어 3 개의 항목이있는 경우 하나는 다른 두 개 중 하나보다 선택 될 가능성이 두 배가되어야 목록에 다음과 같이 표시됩니다.

 [{A,1},{B,1},{C,2}]

그런 다음 목록의 수를 더합니다 (예 : 우리의 경우 4). 이제 난수를 생성하고 해당 인덱스를 선택하십시오. int 인덱스 = rand.nextInt (4); 인덱스가 올바른 범위에 있도록 숫자를 반환합니다.

자바 코드 :

class Item {
    int relativeProb;
    String name;

    //Getters Setters and Constructor
}

...

class RandomSelector {
    List<Item> items = new List();
    Random rand = new Random();
    int totalSum = 0;

    RandomSelector() {
        for(Item item : items) {
            totalSum = totalSum + item.relativeProb;
        }
    }

    public Item getRandom() {

        int index = rand.nextInt(totalSum);
        int sum = 0;
        int i=0;
        while(sum < index ) {
             sum = sum + items.get(i++).relativeProb;
        }
        return items.get(Math.max(0,i-1));
    }
}

---

1. 균일하게 분포 된 난수를 생성합니다.
2. 방문한 요소의 누적 확률이 난수보다 클 때까지 목록을 반복합니다.

샘플 코드 :

double p = Math.random();
double cumulativeProbability = 0.0;
for (Item item : items) {
    cumulativeProbability += item.probability();
    if (p <= cumulativeProbability) {
        return item;
    }
}

---

다음 목록이있는 척

Item A 25%
Item B 15%
Item C 35%
Item D 5%
Item E 20%

모든 확률이 정수라고 가정하고 다음과 같이 계산 된 "범위"를 각 항목에 할당합니다.

Start - Sum of probability of all items before
End - Start + own probability

새로운 번호는 다음과 같습니다

Item A 0 to 25
Item B 26 to 40
Item C 41 to 75
Item D 76 to 80
Item E 81 to 100

이제 0에서 100까지 임의의 숫자를 선택합니다. 32를 선택한다고 가정하겠습니다. 32는 항목 B의 범위에 속합니다.

mj

---

룰렛 휠 선택을 시도 할 수 있습니다 .

먼저 모든 확률을 더한 다음 각 확률을 합으로 나누어 1 척도의 모든 확률을 척도 화합니다. 확률이 A(0.4), B(0.3), C(0.25) and D(0.05). 그런 다음 [0, 1] 범위에서 임의의 부동 소수점 숫자를 생성 할 수 있습니다. 이제 다음과 같이 결정할 수 있습니다.

random number between 0.00 and 0.40 -> pick A
              between 0.40 and 0.70 -> pick B
              between 0.70 and 0.95 -> pick C
              between 0.95 and 1.00 -> pick D

임의의 정수로도 수행 할 수 있습니다. 0에서 99 (포함) 사이의 임의의 정수를 생성한다고 가정하면 위와 같은 결정을 내릴 수 있습니다.

---

Algorithm described in Ushman's, Brent's and @kaushaya's answers are implemented in Apache commons-math library.

Take a look at EnumeratedDistribution class (groovy code follows):

def probabilities = [
   new Pair<String, Double>("one", 25),
   new Pair<String, Double>("two", 30),
   new Pair<String, Double>("three", 45)]
def distribution = new EnumeratedDistribution<String>(probabilities)
println distribution.sample() // here you get one of your values

Note that sum of probabilities doesn't need to be equal to 1 or 100 - it will be normalized automatically.

---

My method is pretty simple. Generate a random number. Now since the probabilities of your items are known,simply iterate through the sorted list of probability and pick the item whose probability is lesser than the randomly generated number.

For more details,read my answer here.

---

A slow but simple way to do it is to have every member to pick a random number based on its probability and pick the one with highest value.

Analogy:

Imagine 1 of 3 people needs to be chosen but they have different probabilities. You give them die with different amount of faces. First person's dice has 4 face, 2nd person's 6, and the third person's 8. They roll their die and the one with the biggest number wins.

Lets say we have the following list:

[{A,50},{B,100},{C,200}]

Pseudocode:

 A.value = random(0 to 50);
 B.value = random(0 to 100);
 C.value = random (0 to 200);

We pick the one with the highest value.

This method above does not exactly map the probabilities. For example 100 will not have twice the chance of 50. But we can do it in a by tweaking the method a bit.

Method 2

Instead of picking a number from 0 to the weight we can limit them from the upper limit of previous variable to addition of the current variable.

[{A,50},{B,100},{C,200}]

Pseudocode:

 A.lowLimit= 0; A.topLimit=50;
 B.lowLimit= A.topLimit+1; B.topLimit= B.lowLimit+100
 C.lowLimit= B.topLimit+1; C.topLimit= C.lowLimit+200 

resulting limits

A.limits = 0,50
B.limits = 51,151
C.limits = 152,352

Then we pick a random number from 0 to 352 and compare it to each variable's limits to see whether the random number is in its limits.

I believe this tweak has better performance since there is only 1 random generation.

There is a similar method in other answers but this method does not require the total to be 100 or 1.00.

---

Brent's answer is good, but it doesn't account for the possibility of erroneously choosing an item with a probability of 0 in cases where p = 0. That's easy enough to handle by checking the probability (or perhaps not adding the item in the first place):

double p = Math.random();
double cumulativeProbability = 0.0;
for (Item item : items) {
    cumulativeProbability += item.probability();
    if (p <= cumulativeProbability && item.probability() != 0) {
        return item;
    }
}

---

If you don't mind adding a third party dependency in your code you can use the MockNeat.probabilities() method.

For example:

String s = mockNeat.probabilites(String.class)
                .add(0.1, "A") // 10% chance to pick A
                .add(0.2, "B") // 20% chance to pick B
                .add(0.5, "C") // 50% chance to pick C
                .add(0.2, "D") // 20% chance to pick D
                .val();

Disclaimer: I am the author of the library, so I might be biased when I am recommending it.

---

You could use the Julia code:

function selrnd(a::Vector{Int})
    c = a[:]
    sumc = c[1]
    for i=2:length(c)
        sumc += c[i]
        c[i] += c[i-1]
    end
    r = rand()*sumc
    for i=1:length(c)
        if r <= c[i]
            return i
        end
    end
end

This function returns the index of an item efficiently.

참고URL : https://stackoverflow.com/questions/9330394/how-to-pick-an-item-by-its-probability