Hate, …
WarCraft 3

Таблица случайных чисел без повторений [LUA]

Добавлен , опубликован
Алгоритмы, Наработки и Способности
Способ реализации:
Lua
Тип:
Алгоритм
Версия Warcraft:
1.30+
Иногда может понадобиться иметь набор случайных чисел в определенном промежутке без повторений значений
поэтому было придумано это чудовище
Lua code 
---@param min integer
---@param max integer
---@param count integer|nil
function GetRandomIntTable(min, max, count)
	local keys = {}
	local out  = {}
	
	if min == max then return { min } end
	if max < min then min, max = max, min end
	local limit = math.abs(max - min) + 1
	count       = count == nil and limit or math.min(limit, count)
	if limit <= count then
		local ints = {}
		for i = min, max do
			table.insert(ints, i)
		end
		for _ = 1, limit do
			table.insert(out, table.remove(ints, math.random(1, #ints)))
		end
		return out
	else
		while #out < count do
			local i = math.random(min, max)
			if keys[i] == nil then
				keys[i] = true
				table.insert(out, i)
			end
		end
		return out
	end
end
Использовать можно как
local a = GetRandomIntTable(1, 5, 10)
for i = 1, #a do
    print(a[i])
end
где первое число минимальное значение, второе максимальное, третье количество значений
каждая ячейка таблицы будет содержать свою уникальную цифру в пределах значений и не больше чем их диапазон, например { 4, 1, 3, 5, 2 }.
функция GetRandomIntTable(min, max, count) может работать как GetRandomIntTable(200, 100, 5) так и как GetRandomIntTable(100, 200, 5) или GetRandomIntTable(100, 200), работает так же и с отрицательными значениями
,
24 янв 2020
2 472
`
ОЖИДАНИЕ РЕКЛАМЫ...
0
Показать
28
0
Показать
GetRandomIntTable(1, 5, 10)
Как тут выйдет 10 значений?
Обе границы включены?
0
Показать
26
0
Показать
PT153:
Как тут выйдет 10 значений?
никак, он возьмет максимум из доступных в таком случае
0
Показать
28
0
Показать
То есть все значения из промежутка в случайной последовательности?
0
Показать
26
0
Показать
да, если задаешь GetRandomIntTable(1, 5, 10) то может выпасть например { 4, 1, 3, 5, 2 }
0
Показать
25
0
Показать
Я, конечно, не шарю в LUA, но выглядит как комбайн какой-то.
Неужели там все так плохо?
Ну, типа, даже в абстрашной пышке аналогичный код будет выглядеть типа такого:
function build(int $min, int $max, int $count)
{
$result = [];
while (count($result) < $count) {
$result[random_int($min, $max)] = 0;
}

return array_keys($result);
}
0
Показать
26
0
Показать
исключает ли твой вариант повторений?
0
Показать
25
0
Показать
Конечно)
У тебя не могут быть 2 одинаковых ключа, а генерит оно именно их)
Просто похожую задачку как-то на собесе давали.
Тут есть избыточность, конечно, потому что оно может, теоретически, 5 раз в ряд генерить одно и тоже значение, но не думаю, что это очень критично.
Но у меня это ассоциативный массив, возвращаются ключи которого. Если в LUA они тоже есть такое, то это куда более деликатное решение данной задачи. Имхо, конечно)
1
Показать
28
1
Показать
NanO:
Тут есть избыточность, конечно, потому что оно может, теоретически, 5 раз в ряд генерить одно и тоже значение, но не думаю, что это очень критично.
Вообще-то, критично для производительности, могут выпадать повторения ключей, что замедлит генерацию, и чем больше ключей уже сделано, чем выше шанс их повторения.
Алгоритм, что зависит только от числа элементов и производительности функции рандома.
  1. Генерируем массив Vals от min до max, включая концы промежутка.
  2. top = #Vals
  3. Если #Vals < length, то lenght = #Vals.
  4. Для а = 1 по length делаем.
    а. i = rand(1, top)
    b. result[a] = Vals[i]
    c. Vals[i] = Vals[top]
    d. top = top - 1
  5. return result
0
Показать
25
0
Показать
PT153:
Вообще-то, критично для производительности, могут выпадать повторения ключей, что замедлит генерацию, и чем больше ключей уже сделано, чем выше шанс их повторения.
Тут уже зависит от кейсов использования, поэтому критичность варьируется, но я с тобой согласен.
0
Показать
30
0
Показать
PT153:
Алгоритм, что зависит только от числа элементов и производительности функции рандома.
Вообщето он реализован, и он плох в случае GetRandomIntTable(-100500, 100500, 10)
Загруженные файлы
0
Показать
22
0
Показать
а чем в плох заранее заносить в массив а потом из рандома получаем результат 1 очередь и берем последную значение в массиве и перенести в который был результат и так цикл выполнит ровно столько и нужен рандомить
0
Показать
30
0
Показать
NanO:
Ну, типа, даже в абстрашной пышке аналогичный код будет выглядеть типа такого:
Так через ключи массива и здесь реализовано
И попробуй на пыхе выполнить build(-1,-5,10)
Загруженные файлы
0
Показать
28
0
Показать
NazarPunk:
он плох в случае GetRandomIntTable(-100500, 100500, 10)
Хм, верно. Тут уж нужно замерять производительность, и смотреть, какой способ лучше.
алло 
        -- while true do
            -- if #out >= count then return out end
        while #out < count do  -- вот так лучше
            local i = math.random(min, max)
            if keys[i] == nil then
                keys[i] = true
                table.insert(out, i)
            end
        end
        return out
Чтобы оставить комментарий, пожалуйста, войдите на сайт.