Выбор случайных элементов списка в Перле (С заданными частотами)

[TRON]

Мне нужно сгенерировать строку определенной длины из букв массива @letters. Буквы должны быть расположены случайно и каждая буква должна встречаться со своей определенной частотой, которая не равна 1/@letters. Функция rand(@letters) в Перле выдает случайное значение, меньше размера массива, но (как я понял) с равной вероятностью для каждого элемента массива.

Единственное, что пока пришло в голову: синтезировать на основании массива @letters (а точнее хэша %letters, где каждой букве сопоставлена требуемая частота) новый массив из, допустим 1000-10000 элементов, в котором содержание букв будет пропорционально требуемой частоте, но они будут расположены неслучайным образом. А затем на основании этого массива сгенерировать нужную строку.

А нельзя-ли как-то элегантнее решить эту проблему? Может есть способ численно задать частоту каждого элемента списка для функции rand?

P.S. Прошу не пинать если вопрос слишком прост, а ответ очевиден. Перл - мой первый язык и я только начал его изучать.

[sarutobi]

TRON
Задача классическая и решение классическое.
функция rand (как и любая функция рандомизации) выдает равновероятное случайное число из диапазона 0..1. Вам нужно определить свою функцию на основе rand
myrand(@p)
которая принимает на вход массив вероятностей появления элементов. Условия, накладываемое на @p - сумма всех его элементов равна 1, каждый элемент находится в диапазоне 0..1
внутри функции вы вызываете rand и смотрите, в какой диапазон попало выбранное случайное число. Если оно меньше 1 элемента @p - возвращается 1, если меньше суммы первых n элементов @p - возвращается n.
Оптимизации можете дописать сами

[v04bvs]

Круто, я этот алгоритм знал, мне он никогда не нравился из за линейной сложности, а сейчас я допёр, что тут классно двоичное дерево поиска подходит