Рандомизатор по весам с вычитанием веса у выпавшего

@MuaddibFremen · Регистрация: 04.03.2019

Студворк — интернет-сервис помощи студентам

мне необходимо к примеру создать 4 предметов из пула .
создаю пул
List<int> list = {1,2,3,4,5,6,7,8,9};
запустил рандом и получил к примеру 1,1,1,1 или схожую ситуацию 2,5,5,5 и так далее.
ну то есть обычный рандом дает частые выпадения одинаковых чисел.

далее захотелось как то разнообразить выпадения и решил я присобачить к ним шансы выпадения (через вес) с вычетом.
Dictionary<int, int> weights;
где первый int это наше число из пула list
а второй int это шанс выпадения, который меняется.

C#
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
public static int GetRandomOnWeight(Dictionary<int,int> weights)
    {
        var summ = 0;
        foreach (var w in weights.Values) summ += w;
        var r = UnityEngine.Random.Range(0, summ);
        var keys = weights.Keys;
        foreach (var key in keys)
        {
            if (r <= weights[key]) 
            {
                ChangeWeights(key, weights);
                return key;
            }
            r -= weights[key];
        }
    }
 
int summChances = 10000; // сумма шансов выпадений для всех (делим на всех и раздаем)
 
static void ChangeWeights(int id, Dictionary<int,int> weights)
    {
        int len = weights.Count;
        // отнимаем у предмета
        int minus = dictMinusPercent[len]; // тут чиселко зависит от кол-ва предметов в пуле на в среднем 10% от summChances 
        if (weights[id] - minus <= 0)
        {
            // иногда вес может быть меньше отнимаемого
            minus = weights[id];
            weights[id] = 0;
        }
        else
        {
            weights[id] -= minus;
        }
 
        // раздаем по кусочку остальным то что отняли
        int plus = minus / ((len > 1) ? (len - 1) : 1);
 
        int summ = 0;
        var keys = new List<int>();
        foreach (var item in weights.Keys)
            keys.Add(item);
 
        foreach (var item in keys)
        {
            if (item != id)
                weights[item] += plus;
            summ += weights[item];
        }
 
        // елси вдруг есть потеря(остаток) при делении, то накидываем тому у кого забрали. там крохи
        int delta = summChances - summ;
        if (delta > 0)
            weights[id] += delta;
    }

вобщем если вес для всех одинаковый. summChances / кол-во_в_пуле то все норм.
НО если я хочу разный вес для разных итемов и чтобы распределялось (отнимаемое у выпавшего) в зависимости от изначального веса, то начинаются свистопляски и результат меня не устраивает.

по этому вопрос)
где почитать чтобы надыбать правильные формулы расчета чего то подобного?
или может кто может помочь написать такое...

задача дать возмоность задавать вес выпадения для каждого итема и при этом чтобы он (вес) изменялся (вычитался) если итем выпал в рандоме, а вычитаемое распределилось равномерно между остальными с учетом изначального веса.

@I2um1 · 24.12.2020, 01:36

MuaddibFremen, типа такого или надо менять веса еще в процессе генерирования?

C#
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
using System;
using System.Collections.Generic;
 
const int N = 10_000_000;
 
List<(int value, int weight)> list = new List<(int value, int weight)>
{
    (1, 10),
    (2, 20),
    (3, 10),
    (4, 60)
};
for (int i = 1; i < list.Count; i++)
{
    list[i] = (list[i].value, list[i].weight + list[i - 1].weight);
}
 
Random randomizer = new Random();
int maxWeight = list[^1].weight;
Dictionary<int, int> dictionary = new Dictionary<int, int>(list.Count);
for (int i = 0; i < N; i++)
{
    int weight = randomizer.Next(maxWeight);
    for (int j = 0; j < list.Count; j++)
    {
        if (weight < list[j].weight)
        {
            dictionary.TryGetValue(list[j].value, out int count);
            dictionary[list[j].value] = count + 1;
            break;
        }
    }
}
 
foreach ((int value, int count) in dictionary)
{
    Console.WriteLine($"{value} = {count * 100d / N:0.##}%");
}

@MuaddibFremen · 24.12.2020, 10:48 **[ТС]**

Сообщение от I2um1

надо менять веса еще в процессе генерирования

да именно менять весса в процессе рандомизации.
но за код спасибо глянем. хотя беглым взглядом это тоже самое что у меня было.

добраться до ПК еще не успел. поясните пожалйста код что делает

Сообщение от I2um1

int maxWeight = list[^1].weight;

и этот

Сообщение от I2um1

for (int i = 1; i < list.Count; i++)
{
list[i] = (list[i].value, list[i].weight + list[i - 1].weight);
}

@I2um1 · 24.12.2020, 11:53

C#
1
int maxWeight = list[^1].weight;

C# 8, индекс с конца.

C#
1
list[i] = (list[i].value, list[i].weight + list[i - 1].weight);

C# 7, кортежи.

Все равно, что:

C#
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
using System;
using System.Collections.Generic;
 
class Program
{
    static void Main()
    {
        const int N = 10000000;
 
        List<Data> list = new List<Data>
        {
            new Data(1, 10),
            new Data(2, 20),
            new Data(3, 10),
            new Data(4, 60)
        };
        for (int i = 1; i < list.Count; i++)
        {
            list[i] = new Data(list[i].Value, list[i].Weight + list[i - 1].Weight);
        }
 
        Random randomizer = new Random();
        int maxWeight = list[list.Count - 1].Weight;
        Dictionary<int, int> dictionary = new Dictionary<int, int>(list.Count);
        for (int i = 0; i < N; i++)
        {
            int weight = randomizer.Next(maxWeight);
            for (int j = 0; j < list.Count; j++)
            {
                if (weight < list[j].Weight)
                {
                    int count;
                    dictionary.TryGetValue(list[j].Value, out count);
                    dictionary[list[j].Value] = count + 1;
                    break;
                }
            }
        }
 
        foreach (KeyValuePair<int, int> pair in dictionary)
        {
            Console.WriteLine($"{pair.Key} = {pair.Value * 100d / N:0.##}%");
        }
    }
}
 
struct Data
{
    public Data(int value, int weight)
    {
        Value = value;
        Weight = weight;
    }
 
    public int Value { get; set; }
    public int Weight { get; set; }
}

Сообщение от MuaddibFremen

да именно менять весса в процессе рандомизации.

А, тогда такая реализация это позволяет. Я просто поделил прямую на 4 отрезка:
[0, 10)
[10, 30)
[30, 40)
[40, 100)

Рандомизатор по весам с вычитанием веса у выпавшего

И затем кинул случайное число [0, 100). Ничего не мешает список перестроить в процессе, главное, чтобы отрезки нужной длинны получались. Верхняя граница может быть любая, не обязательно 100.

@MuaddibFremen · 24.12.2020, 12:34 **[ТС]**

Сообщение от I2um1

list[i] = (list[i].value, list[i].weight + list[i - 1].weight);

Сообщение от I2um1

[0, 10)
[10, 30)
[30, 40)
[40, 100)

я как раз имел ввиду это. оно выстраивало отрезки.

а где ваш код не меняет значения веса?
а вижу вы просто предложили.

ну так это уже реализовано все в моем коде (ChangeWeights).
в моем методе ChangeWeights я просто раскидываю на всех.
проблема в том что как высчитывать распределение с учетом базовых весов.

Добавлено через 2 минуты

Сообщение от I2um1

int maxWeight = list[^1].weight;

на самом деле это чтото типа Last из Linq ?
но если макс значение на другой позиции то, выражение уже даст не правильный результат.

Добавлено через 1 минуту
хотя нет. в данном случае вы просто показали правую границу для рандома

@I2um1 · 24.12.2020, 13:00

Сообщение от MuaddibFremen

проблема в том что как высчитывать распределение с учетом базовых весов.

Без дополнительного списка:

C#
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
static void Main()
{
    const int N = 10000000;
 
    List<Data> list = new List<Data>
    {
        new Data(1, 10),
        new Data(2, 20),
        new Data(3, 10),
        new Data(4, 60)
    };
    Sum(list);
 
    Diff(list);
    list[1] = new Data(2, 25);
    Sum(list);
}
 
static void Sum(List<Data> list)
{
    for (int i = 1; i < list.Count; i++)
    {
        list[i] = new Data(list[i].Value, list[i].Weight + list[i - 1].Weight);
    }
}
 
static void Diff(List<Data> list)
{
    for (int i = list.Count - 1; i > 0; i--)
    {
        list[i] = new Data(list[i].Value, list[i].Weight - list[i - 1].Weight);
    }
}

Сообщение от MuaddibFremen

а где ваш код не меняет значения веса?

С дополнительным списком:

C#
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
static void Main()
{
    List<Data> original = new List<Data>
    {
        new Data(1, 10),
        new Data(2, 20),
        new Data(3, 10),
        new Data(4, 60)
    };
    List<Data> list = Sum(original);
 
    original[1] = new Data(2, 25);
    list = Sum(original);
}
 
static List<Data> Sum(List<Data> list)
{
    List<Data> result = new List<Data>(list.Count);
    result.Add(list[0]);
    for (int i = 1; i < list.Count; i++)
    {
        result.Add(new Data(list[i].Value, list[i].Weight + result[i - 1].Weight));
    }
 
    return result;
}

Сообщение от MuaddibFremen

на самом деле это чтото типа Last из Linq ?

Нет, это все равно, что, но короче:

C#
1
int maxWeight = list[list.Count - 1].Weight;

Сообщение от MuaddibFremen

но если макс значение на другой позиции то, выражение уже даст не правильный результат.

Чем не устраивает пересобрать веса?

Сообщение от MuaddibFremen

в данном случае вы просто показали правую границу для рандома

Просто один из вариантов решения, с целыми числами проще работать. При изменении вероятности одного объекта надо менять вероятность всех остальных. Через сложение, как я сделал, это проще сделать и понять.

@MuaddibFremen · 24.12.2020, 13:26 **[ТС]**

Сообщение от I2um1

list[1] = new Data(2, 25);

не ну это вы руками меняете.
я же

Сообщение от MuaddibFremen

чтобы он (вес) изменялся (вычитался) если итем выпал в рандоме, а вычитаемое распределилось равномерно между остальными с учетом изначального веса.

@I2um1 · 24.12.2020, 13:31

MuaddibFremen, пример? Обычно вероятность трогать не надо для равномерного распределения. От ситуации с подряд идущими одинаковыми значениями не избавиться в равномерном распределении.

@MuaddibFremen · 24.12.2020, 13:39 **[ТС]**

пример.

C#
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
List<Data> original = new List<Data>
    {
        new Data(1, 10),
        new Data(2, 20),
        new Data(3, 10),
        new Data(4, 60)
    };
 
int weight = randomizer.Next(maxWeight);
weight = 23;
 
// попало на 2, просчитываем вессы
 
{1, 10+5/3},
{2, 20-5},
{3, 10+5/3},
{4, 60+5/3}

во то чем я. веса меняются каждый раз как происходит рандом.
но в данном случае у меня все ОК работает.

мне же нужно прибавлять соответственно базовому весу

Добавлено через 2 минуты

Сообщение от I2um1

От ситуации с подряд идущими одинаковыми значениями не избавиться в равномерном распределении.

а нужно избавиться) какие варианты есть?

Добавлено через 5 минут

Сообщение от I2um1

в равномерном распределении

оно должно быть в целом тут

Сообщение от I2um1

Dictionary<int, int> dictionary = new Dictionary<int, int>(list.Count);

а не обязательно в выпавшей последовательности из 4 позиций за раз.
для того я и хочу уменьшать вес чтобы избежать повторений

@I2um1 · 24.12.2020, 14:02

Сообщение от MuaddibFremen

оно должно быть в целом тут

Оно-то в целом есть, но повторения все равно будут. Как в моем примере, на 4 приходится 60%. А при делении на 3 на каждой итерации будет только падать точность весов:

C#
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
using System;
using System.Collections.Generic;
 
class Program
{
    static void Main()
    {
        const int N = 100000;
 
        List<Data> original = new List<Data>
        {
            new Data(1, 10),
            new Data(2, 20),
            new Data(3, 10),
            new Data(4, 60)
        };
        List<Data> list = new List<Data>(original.Count);
        Sum(original, list);
 
        Random randomizer = new Random();
        double maxWeight = list[list.Count - 1].Weight;
        Dictionary<int, int> dictionary = new Dictionary<int, int>(list.Count);
        for (int i = 0; i < N; i++)
        {
            double weight = randomizer.NextDouble() * maxWeight;
            for (int j = 0; j < list.Count; j++)
            {
                if (weight < list[j].Weight)
                {
                    int count;
                    dictionary.TryGetValue(list[j].Value, out count);
                    dictionary[list[j].Value] = count + 1;
 
                    int index = original.FindIndex(data => data.Value == list[j].Value);
                    ChangeWeight(original, index, 5);
                    Sum(original, list);
                    break;
                }
            }
        }
 
        foreach (KeyValuePair<int, int> pair in dictionary)
        {
            Console.WriteLine($"{pair.Key} = {pair.Value * 100d / N:0.##}%");
        }
    }
 
    static void ChangeWeight(List<Data> list, int index, double value)
    {
        value = Math.Min(value, list[index].Weight);
 
        list[index] = new Data(list[index].Value, list[index].Weight - value);
        double anotherValue = value / (list.Count - 1);
        for (int i = 0; i < list.Count; i++)
        {
            if (i != index)
            {
                list[i] = new Data(list[i].Value, list[i].Weight + anotherValue);
            }
        }
    }
 
    static void Sum(List<Data> list, List<Data> result)
    {
        result.Add(list[0]);
        for (int i = 1; i < list.Count; i++)
        {
            result.Add(new Data(list[i].Value, list[i].Weight + result[i - 1].Weight));
        }
    }
}
 
struct Data
{
    public Data(int value, double weight)
    {
        Value = value;
        Weight = weight;
    }
 
    public int Value { get; set; }
    public double Weight { get; set; }
 
    public override string ToString()
    {
        return $"{Value}, {Weight}";
    }
}

Добавлено через 1 минуту
Хотя, можно вообще к весам не привязаться:
- выпала 4 с 60%, мы ей уменьшили шанс на 59.99
- выпала снова 4 с шансом 0.01%

@MuaddibFremen · 24.12.2020, 14:48 **[ТС]**

Сообщение от I2um1

static void ChangeWeight(List<Data> list, int index, double value)

это тоже самое что и я делаю) в своем коде

Сообщение от I2um1

double anotherValue = value / (list.Count - 1);

при равномерном расспределении всё идет нормально.

ну хотя бы пришли уже к этому))

фокусы начинают когда я хочу к anotherValue присобачить коэфициент в зависимости от базовых весов.

Сообщение от I2um1

list[i] = new Data(list[i].Value, list[i].Weight + anotherValue);

тоесть тут прибавить не просто вычитаемое

C#
1
2
3
4
{1, 10+5/3},
{2, 20-5},
{3, 10+5/3},
{4, 60+5/3}

а коэфициент от базового

Сообщение от I2um1

List<Data> original = new List<Data>
{
new Data(1, 10),
new Data(2, 20),
new Data(3, 10),
new Data(4, 60)
};

C#
1
2
3
4
{1, 10+5*к},  к = 10/(10+10+60)
{2, 20-5},
{3, 10+5*к},  к = 10/(10+10+60)
{4, 60+5*к}   к = 60/(10+10+60)

вот как это все правильно просчитать?

@I2um1 · 24.12.2020, 15:34

MuaddibFremen, в итоге же тоже самое получится, не? Только погрешность еще больше станет:

C#
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
using System;
using System.Collections.Generic;
using System.Linq;
 
class Program
{
    static void Main()
    {
        const int N = 1000;
 
        List<Data> original = new List<Data>
        {
            new Data(1, 10),
            new Data(2, 20),
            new Data(3, 10),
            new Data(4, 60)
        };
        List<Data> weights = new List<Data>(original);
        List<Data> list = new List<Data>(weights.Count);
        Sum(weights, list);
 
        Random randomizer = new Random();
        double maxWeight = list[list.Count - 1].Weight;
        Dictionary<int, int> dictionary = new Dictionary<int, int>(list.Count);
        for (int i = 0; i < N; i++)
        {
            double weight = randomizer.NextDouble() * maxWeight;
            for (int j = 0; j < list.Count; j++)
            {
                if (weight < list[j].Weight)
                {
                    int count;
                    dictionary.TryGetValue(list[j].Value, out count);
                    dictionary[list[j].Value] = count + 1;
 
                    int index = weights.FindIndex(data => data.Value == list[j].Value);
                    ChangeWeight(original, weights, index, 5);
                    Sum(weights, list);
                    break;
                }
            }
        }
 
        foreach (KeyValuePair<int, int> pair in dictionary)
        {
            Console.WriteLine($"{pair.Key} = {pair.Value * 100d / N:0.##}%");
        }
    }
 
    static void ChangeWeight(List<Data> original, List<Data> weights, int index, double value)
    {
        value = Math.Min(value, weights[index].Weight);
        double sum = original.Sum(x => x.Weight) - original[index].Weight;
 
        weights[index] = new Data(weights[index].Value, weights[index].Weight - value);
        for (int i = 0; i < weights.Count; i++)
        {
            if (i != index)
            {
                double anotherValue = value * original[i].Weight / sum;
                weights[i] = new Data(weights[i].Value, weights[i].Weight + anotherValue);
            }
        }
    }
 
    static void Sum(List<Data> list, List<Data> result)
    {
        result.Add(list[0]);
        for (int i = 1; i < list.Count; i++)
        {
            result.Add(new Data(list[i].Value, list[i].Weight + result[i - 1].Weight));
        }
    }
}
 
struct Data
{
    public Data(int value, double weight)
    {
        Value = value;
        Weight = weight;
    }
 
    public int Value { get; set; }
    public double Weight { get; set; }
 
    public override string ToString()
    {
        return $"{Value}, {Weight}";
    }
}

Для первых 10:

Хотя, иногда и генерирует что-то типа:

Добавлено через 3 минуты
Смутное представление финального эффекта. Может лучше как с колодой карт?
1. Кладем в колоду 54 карты с какими-то значениями
2. Мешаем
3. Вытаскиваем карту. Повтор? Кладем в конец колоды, пока в колоде не останутся повторы или она не станет пустой.

@MuaddibFremen · 24.12.2020, 16:28 **[ТС]**

Сообщение от I2um1

double anotherValue = value * original[i].Weight / sum;
weights[i] = new Data(weights[i].Value, weights[i].Weight + anotherValue);

это я тоже сделал) и у меня тоже самое

Сообщение от I2um1

погрешность еще больше станет

если запускать 10000 итераций то как бы смещаются слегка базовые числа.
вобщем там большие и меньшие идут в сторону среднего этак на 2-5%...

вот и что не так?

Добавлено через 1 минуту

Сообщение от I2um1

Может лучше как с колодой карт?
1. Кладем в колоду 54 карты с какими-то значениями
2. Мешаем
3. Вытаскиваем карту. Повтор? Кладем в конец колоды, пока в колоде не останутся повторы или она не станет пустой.

вариант интерестный, но общая картина по значениям какая будет?
да и думаю не подойдет

@I2um1 · 24.12.2020, 16:36

Сообщение от MuaddibFremen

вот и что не так?

Так все так. Как колесо не переизобретай. Получится одно и то же в итоге. Это никак не исправить:

Сообщение от I2um1

- выпала 4 с 60%, мы ей уменьшили шанс на 59.99
- выпала снова 4 с шансом 0.01%

@MuaddibFremen · 25.12.2020, 17:30 **[ТС]**

Сообщение от I2um1

Смутное представление финального эффекта

ну представим скажем игру. в игре есть дни. каждый день выпадает 4 элемента из списка.
каждый элемент по своему нужен и восстребован.
но некоторые элементы выпадают чаще, а других не хватает. что нарушает логику.

Новые блоги и статьи Все статьи Все блоги /
Кому нужен AOT? DevAlt 26.03.2026 Решил сделать простой ланчер Написал заготовку: dotnet new console --aot -o UrlHandler var items = args. Split(":"); var tag = items; var id = items; var executable = args;. . .	Отправка уведомления на почту при изменении наименования справочника Maks 24.03.2026 Программная отправка письма электронной почты на примере изменения наименования типового справочника "Склады" в конфигурации БП3. Перед реализацией необходимо выполнить настройку системной учетной. . .	модель ЗдравоСохранения 5. Меньше увольнений- больше дохода! anaschu 24.03.2026 Теперь система здравосохранения уменьшает количество увольнений. 9TO2GP2bpX4 a42b81fb172ffc12ca589c7898261ccb/ https:/ / rutube. ru/ video/ a42b81fb172ffc12ca589c7898261ccb/ Слева синяя линия -. . .	Midnight Chicago Blues kumehtar 24.03.2026 Такой Midnight Chicago Blues, знаешь?. . Когда вечерние улицы становятся ночными, а ты не можешь уснуть. Ты идёшь в любимый старый бар, и бармен наливает тебе виски. Ты смотришь на пролетающие. . .
SDL3 для Desktop (MinGW): Вывод текста со шрифтом TTF с помощью библиотеки SDL3_ttf на Си и C++ 8Observer8 24.03.2026 Содержание блога Финальные проекты на Си и на C++: finish-text-sdl3-c. zip finish-text-sdl3-cpp. zip	Жизнь в неопределённости kumehtar 23.03.2026 Жизнь — это постоянное существование в неопределённости. Например, даже если у тебя есть список дел, невозможно дойти до точки, где всё окончательно завершено и больше ничего не осталось. В принципе,. . .	Модель здравоСохранения: работники работают быстрее после её введения. anaschu 23.03.2026 geJalZw1fLo Корпорация до введения программа здравоохранения имела много невыполненных работниками заданий, после введения программы количество заданий выросло. Но на выплатах по больничным это. . .	Контроль уникальности заводского номера Maks 23.03.2026 Алгоритм контроля уникальности заводского (или серийного) номера на примере нетипового документа выдачи шин для спецтехники с табличной частью, разработанного в конфигурации КА2. Номеклатура. . .

@I2um1 Злой няш 2136 / 1505 / 565 Регистрация: 05.04.2010 Сообщений: 2,881
	24.12.2020, 13:31
	MuaddibFremen, пример? Обычно вероятность трогать не надо для равномерного распределения. От ситуации с подряд идущими одинаковыми значениями не избавиться в равномерном распределении. 0