Загадки математики

[1kvolt]

9 минут назад, Игорь сказал:

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

Так я и описал же. Есть массив объектов и массив их весов. Из первого нужно выбирать случайным образом объекты с учётом их весов из второго.

Вопрос совсем не житейский, просто в программке одной понадобилось. Хобби у меня такое - программированием всякой фигни баловаться. 

11 минут назад, Игорь сказал:

может,и верное. 

Видишь ли, в программной реализации оно выглядит "некрасиво". И меня не покидает чувство, что я что-то упускаю, чего-то не знаю, и поэтому моё решение такое неизящное. Поэтому и обратился к вам, камрадам с верхними инженерными образованиями, чтобы либо найти это изящное решение, либо убедиться в его отсутствии. 

И да, я знаю, что некоторые вещи в математике иначе чем неизящно тупо в лоб не решаются.

[Игорь]

13 минут назад, 1kvolt сказал:

Вопрос совсем не житейский, просто в программке одной понадобилось.

если не житейский- точно не помогу. 

14 минут назад, 1kvolt сказал:

Видишь ли, в программной реализации оно выглядит "некрасиво".

респект тебе. Как бывший программист,понимаю,что такое "некрасиво". К сожалению,тут помощи от меня не жди.

[1kvolt]

3 минуты назад, Игорь сказал:

К сожалению,тут помощи от меня не жди.

Вредный ты. Как бывший программист, мог бы и помочь. 

[Peterson]

Первым действием создаётся массив или список размерностью в сумму всех весов.

[1kvolt]

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

Собственно, мой алгоритм такой:

- суммируем все веса;

- берём случайное число n от 0 до суммы всех весов;

- и тут надо посмотреть, на область какого веса выпало n и какому элементу этот вес соответствует, т.е. получить индекс элемента с этим весом в массиве элементов - и именно на этом шаге я в затыке.  Я использую цикл, перебирающий индексы весов (и, соответственно, индексы соответствующих весам элементов), в котором с нуля на каждом шаге прибавляю к временной переменной следующий вес с текущим индексом и сравниваю её с выпашим n; если n меньше-равно этой переменной суммы уже перебранных весов, то цикл прерывается, а индекс, на котором остановились, - искомый.

В принципе, цикл быстрый, всего лишь операция сложения, операция сравнения и приращение индекса, но мне не нравится само его наличие в принципе. Я подозреваю существование како-нито элегантной формулы, по которой можно рассчитать область выпадения случайного n и соответствуещего этой области индекса. Поэтому и спросил. 

[Peterson]

24 минуты назад, 1kvolt сказал:

Я подозреваю существование како-нито элегантной формулы, по которой можно рассчитать область выпадения случайного n и соответствуещего этой области индекса.

Так у тебя веса - неизвестны.

25 минут назад, 1kvolt сказал:

- и тут надо посмотреть, на область какого веса выпало n и какому элементу этот вес соответствует, т.е. получить индекс элемента с этим весом в массиве элементов - и именно на этом шаге я в затыке.  Я использую цикл, перебирающий индексы весов (и, соответственно, индексы соответствующих весам элементов), в котором с нуля на каждом шаге прибавляю к временной переменной следующий вес с текущим индексом и сравниваю её с выпашим n; если n меньше-равно этой переменной суммы уже перебранных весов, то цикл прерывается, а индекс, на котором остановились, - искомый.

В принципе, цикл быстрый, всего лишь операция сложения, операция сравнения и приращение индекса, но мне не нравится само его наличие в принципе.

Если веса - целочисленные, то после создания массива/списка (красный, красный, красный, синий, синий, зеленый)у тебя одна операция - случайное число сразу дает тебе элемент.

[1kvolt]

Только что, Peterson сказал:

Так у тебя веса - неизвестны.

Вообще-то, известны конечно же. Как иначе ты будешь выбирать элемент в соответствии с его весом, если вес неизвестен? 

1 минуту назад, Peterson сказал:

Если веса - целочисленные, то после создания массива/списка (красный, красный, красный, синий, синий, зеленый)у тебя одна операция - случайное число сразу дает тебе элемент.

Мне в этом подходе не нравятся два момента: 1) обязательность целочисленных весов (но это довольно минорный момент, не очень важный, хотя тоже может сыграть роль) и 2) быстрое разрастание такого вспомогательного массива при росте размера массивов элементов и их весов - и это сильно напряжный момент, потому что размерчик массива равен произведению кол-ва элементов на сумму всех их весов.

Я дал примерчик с тремя цветами и весами [1, 2, 3] просто для понимания задачи, на практике запросто может понадобиться выбор из массива из 100 элементов с развесовкой от 1 до 100, например. И вспомогательный массивчик получится весьма... массивным.  Что будет на массиве элементов из, скажем, 1000? А из 10000?

Кроме того, заполнение самого вспомогательного массива - тоже цикл, хотя и быстрый - всего с одной операцией присвоения. Но количество повторений может быть просто огромным!

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

В любом случае, я хочу узнать, нет ли ещё более простого и удобного способа определить область выпадения случайного числа какой-нибудь формулой из теорвера. 

[DimProsh]

21 час назад, 1kvolt сказал:

использую цикл, перебирающий индексы весов (и, соответственно, индексы соответствующих весам элементов), в котором с нуля на каждом шаге прибавляю к временной переменной следующий вес с текущим индексом и сравниваю её с выпашим n; если n меньше-равно этой переменной суммы уже перебранных весов, то цикл прерывается, а индекс, на котором остановились, - искомый.

А если у тебя несколько элементов с одинаковым весом? Потребуется дополнительная процедура проверки на такой случай и последующего выбора из таких элементов... 

[1kvolt]

2 часа назад, DimProsh сказал:

А если у тебя несколько элементов с одинаковым весом? Потребуется дополнительная процедура проверки на такой случай и последующего выбора из таких элементов...

Нет, не потребуется. Смотри, мы как бы составляем отрезок длиной в сумму всех весов, потом случайно выбираем на нём точку, а потом начиная с нуля прыгаем по отрезку вперёд на расстояние очередного веса и каждый раз проверяем, прошли ли мы точку или нет. Если ещё не прошли, то прыгаем на величину следующего веса. Если прошли, то последний прыжок был тем, в который попала точка, и значит последний вес - искомый. При этом не имеет значения, равны веса или нет. Если они равны, мы просто будем прыгать по отрезку на одинаковую величину.

Вот, картинку нарисую:

даны элементы [red, green, blue, white] и их веса [1, 2, 3, 2].

0-|--|---|x-

  r   g   b   w

х - случайная точка (допустим, выпавшая на последний кусочек отрезка, соответствующий элементу white с весом 2, и равная 7). Начинаем прыгать:

index = 0, jump = 1, т.е. берём первый вес и прыгаем на его величину 1; проверяем точку: (7 <= 1)? Нет, прыгаем дальше;

index = 1, jump = jump + 2 = 3, т.е. к величине предыдущего прыжка добавляем следующий вес; проверяем точку: (7 <= 3)? Нет, дальше (заметь, если бы точка выпала на этом кусочке, т.е. была бы 2 или 3, то алгоритм правильно бы выбрал именно этот элемент как искомый, хотя его вес совпадает с весом последнего элемента);

index = 2, jump = jump + 3 = 6; проверяем (7 <= 6)? Нет, дальше;

index = 3, jump = jump + 2 = 8; проверяем (7 <= 8)? Да! Значит текущий index - тот самый, на который выпала случайная точка, т.е. искомый, т.е. наш элемент с индексом 3, т.е. white.

Собственно, вот функция на JS, которая у меня получилась и которой я пользуюсь сейчас:

Спойлер

// Функция, получающая массив весов набора элементов и возвращающая индекс элемента, выбранного случайным образом из набора с учётом его веса
function rndWeightEltIndex(eltWeights) {
    let eltWeightRange = eltWeights.reduce(function(total, num) {
        return total + num;
    });
    let rndPointer = rndRoundNum(0, eltWeightRange);
    let eltIndex = 0;
    let nextLimit = eltWeights[0];
    for (eltIndex = 0; eltIndex < eltWeights.length; eltIndex++) {
        if (rndPointer <= nextLimit) {
            break;
        } else {
            nextLimit += eltWeights[eltIndex + 1];
        }
    }
    return eltIndex;
}

 

// Функция, возвращающая целое случайное число от min до max включительно
function rndRoundNum(min, max) {
    return Math.floor(Math.random() * (max - min + 1)) + min;
}

 

Изменено 6 июня, 2021 пользователем 1kvolt

[1kvolt]

Я немного доработал функцию.  Вот новая, более лучшая, версия:

Спойлер

// Функция, получающая массив весов набора элементов и возвращающая индекс элемента, выбранного случайным образом из набора с учётом его веса
    function rndWeightEltIndex(eltWeights) {
        let eltWeightRange = eltWeights.reduce(function(total, num) {
            return total + num;
        });
        let rndPointer = Math.random() * eltWeightRange;
        let eltIndex = 0;
        let nextLimit = 0;
        for (eltIndex = 0; eltIndex < eltWeights.length; eltIndex++) {
            nextLimit += eltWeights[eltIndex];
            if (rndPointer < nextLimit) {
                break;
            }
        }
        return eltIndex;
    }