/*
ссылки:
Walker's alias method
Wiki:         https://goo.gl/lT15mg
Объяснение: http://goo.gl/p9ke8Q
Код:         http://goo.gl/F8SGKf
*/

; вероятности в виде процентных соотношений:
obj := {A: 20, B: 30, C: 50}
Random, peek, 1, 100
for k, v in obj, sum := 0
   sum += v
until sum >= peek
MsgBox, % k

; общий случай:
obj := {A: 2, B: 3, C: 5}
for k, v in obj, _sum := 0
   _sum += v

Random, peek, 1, _sum
for k, v in obj, sum := 0
   sum += v
until sum >= peek

MsgBox, % k

; проверка:
obj := {A: 2, B: 3, C: 5}
for k, v in obj, _sum := 0
   _sum += v

test := {A: 0, B: 0, C: 0}
Loop 10000  {
   Random, peek, 1, _sum
   for k, v in obj, sum := 0
      sum += v
   until sum >= peek && test[k]++
}

MsgBox, % test.A "`n" test.B "`n" test.C

; алгоритм на основе диапазонов значений
obj := {A: 2, B: 3, C: 5}

for k, v in obj, sum := 0
   sum += v

Random, rand,, 1.
for k, v in obj, prev := 0
    prev += v/sum  ; создаём диапазон для каждого ключа
until rand <= prev ; и сразу проверяем, не попал ли rand в него
   
MsgBox, % k

; проверка алгоритма
SetBatchLines, -1
obj := {A: 20, B: 78.5, C: 1.5}

for k, v in obj, sum := 0
   sum += v

test := {A: 0, B: 0, C: 0}
Loop % N := 100000  {
   Random, rand,, 1.
   for k, v in obj, prev := 0
      prev += v/sum
   until rand <= prev && test[k]++
}
   
MsgBox, % "A — " Round(test.A/N*100, 1) "%`nB — " Round(test.B/N*100, 1) "%`nC — " Round(test.C/N*100, 1) "%"

; ===============================================================================================
;	Класс Probability
;	Эмулирует генерацию "ситуации", вероятность которой может быть задана.
;	
;	Создаёт объект, метод Gen() которого возвращает булево значение, означающее, была ли
;		"ситуация" сгенерирована.
; ===============================================================================================
Class Probability
{
	; ===========================================================================================
	;	prob		- ( float ) Опиционально. В интервале от 0 до 100, обозначающий процент
	;					удачных срабатываний. Со значением по умолчанию, Gen() — всегда
	;					возвращает "True"
	; ===========================================================================================
	__New(prob := 100.0) {
		this.prob := prob > 100 ? 100 : prob < 0 ? 0 : prob
	}
	
	Gen() {
		Random, r, 0.0, 100.0
		Return r <= this.prob
	}
}

; ===============================================================================================
;	Класс ProbabilityList
;	Формирует список из данных, которые затем можно получить с некоторой вероятностью,
;		устанавливаемой при добавлении данных.
; ===============================================================================================
Class ProbabilityList
{
	__New() {
		this._available_probability := 100.0
        this._count := 0
        this._storage := []
		this._last_prob := []
	}
	; ===========================================================================================
	;	Добавляет в список элемент.
	;	item		- ( any ) Данные, добавляемые в список.
	;	prob		- ( float ) Значение ожидания в интервале от 0 до 100, обозначающее щанс, с
	;					которым элемент может быть получен.
	;	Все методы добавляющие элемент в список, имеют этот же набор рагументов.
	; ===========================================================================================
	AddItem(item, prob) {
        this._storage.Push({ "item": item, "prob": new Probability(prob) })
		this._available_probability -= prob
        this._count += 1
	}
	
	; ===========================================================================================
	;	Добавляет в список элемент, учитывая максимально возможный шанс получения элементов
	;		списка равный 100% и распределяя этот пулл вероятности между всеми элементами списка
	;		согласно заявленному ожиданию. Таким образом, в список поместится не больше
	;		элементов, чем сумманый шанс получить каждый из них, опираясь на шанс ожидания.
	;	
	;	Следующие далее методы имеют это же поведение за исключением следующей особености:
	;	
	;		Попытки вместить элементы с шансом превышающим этот лимит — будут проигнорированы,
	;			кроме того случая, когда ещё есть "неизрасходованная" его часть, а добавляемый
	;			элемент ожидается с превышением этого значения. В этом случае, элемент всё же
	;			будет помещён в список, но будет установлен со значением этого остатка.
	; ===========================================================================================
	AddItemWhileAvailable(item, prob) {
		if (this._available_probability == 0 || prob <= 0)
            return -1
			
		prob := prob > this._available_probability ? this._available_probability : prob
		this._storage.Push({ "item": item, "prob": new Probability(prob) })
		this._count += 1
		this._available_probability -= prob
		return this._available_probability
	}
	
	; ===========================================================================================
	;	Добавляет в список элемент.
	;	
	;	Особенностью этого метода является заполнение всей оставшейся части из доступного лимита
	;		вероятности, установкой этого значения для последнего переданного элемента.
	;	
	;	Например: В список добавляется элемент "А" с ожидаемой вероятностью 7%, но
	;		устанавливается со значением 100%, так как доступный лимит ещё не начал
	;		расходоваться. Следующий элемент, "Б" добавляемый с вероятностью 30%, будет
	;		установлен со значением 93%, а элемент "А" — получит свои 7% на шанс. И так далее
	;		пока есть неизрасходованный лимит.
	; ===========================================================================================
	AddItemWhileAvailable_WithFilling(item, prob) {
		if (this._available_probability == 0 || prob <= 0)
            return -1
		if (this._count)
            this._storage[ this._count ].prob := new Probability(this._last_prob[ this._count ])
			
		this._storage.Push({ "item": item, "prob": new Probability(this._available_probability) })
		
		prob := prob > this._available_probability ? this._available_probability : prob
		this._count += 1
		this._last_prob.Push( prob )
		this._available_probability -= prob
		return this._available_probability
	}
	
	; ===========================================================================================
	;	Добавляет в список элемент.
	;	
	;	При добавлении первого элемента, создаётся элемент со значением, равным нулю и весь
	;		оставшейся лимит вероятности будет проецироваться на него. Таким образом, элементы
	;		всегда можно получать с ожидаемой частотой, даже если общая вероятность их получить
	;		меньше доступного лимита.
	; ===========================================================================================
	AddItemWhileAvailable_WithZeroFilling(item, prob) {
		if (this._available_probability == 0 || prob <= 0)
            return -1
		
		prob := prob > this._available_probability ? this._available_probability : prob
		this._storage.Push({ "item": item, "prob": new Probability(prob) })
		this._available_probability -= prob
		
		if (!this._count) {
			this._storage.Push({ "item": 0, "prob": new Probability(this._available_probability) })
			this._count += 1
		} else
			this._storage[ 2 ].prob := new Probability(this._available_probability)
		
		this._count += 1
		return this._available_probability
	}
	
	; ===========================================================================================
	;	Получает случайный элемент списка, согласно ожидаемой вероятности.
	; ===========================================================================================
	GetItem() {
		if (!this._count)
			return -1
		Loop {
			Loop,% this._count {
				Random, r, 1,% this._count
				if ((item := this._storage[ r ]).prob.Gen())
					return item.item
			}
		}
	}
	
	; ===========================================================================================
	;	Удаляет элемент из списка по значению, освобождая занимаемый им лимит.
	; ===========================================================================================
	RemoveItemByItem(item) {
		For index, value in this._storage {
			if (value.item == item) {
				this._available_probability += value.prob.prob
				if (this._last_prob.Count())
					this._last_prob.RemoveAt(index)
				this._storage.RemoveAt(index)
				this._count -= 1
				return true
			}
		} return false	
	}
	
	; ===========================================================================================
	;	Удаляет элемент из списка по индексу, освобождая занимаемый им лимит.
	; ===========================================================================================
	RemoveItemByIndex(index) {
		value := this._storage.RemoveAt(index)
		if (value != "") {
			this._available_probability += value.prob.prob
			if (this._last_prob.Count())
				this._last_prob.RemoveAt(index)
			this._count -= 1
			return true
		} return false
	}
}

#NoEnv
#SingleInstance, Force

ListLines, Off
SetBatchLines, -1
#Include Probability.ahk

count := 100000
ww := 500

current_test_number := 1
tests := ["", "DoFullProbListTest"
			, "DoOverflowProbListTest"
			, "DoOverflowProbListTest_WithAvailable_Prob"
			, "DoDeficitProbListTest_WithAvailable_Prob"
			, "DoDeficitProbListTest_WithAvailable_Prob_AndFilling"
			, "DoDeficitProbListTest_WithAvailable_Prob_AndZeroFilling"]

Gui, 1: Font, s10 w700 c099aaa, Consolas
Gui, 1: Add, Edit, r20 w%ww% v_edit
Gui, 1: Add, Button, w%ww% v_do_next gDoNext, Do Next
Gui, 1: Show

probs := [ 12.7, 4, 98.2, 37.447, 0.2 ]
For i, prob in probs {
	p := new Probability(prob)
	t := f := 0
	Loop,% count
		p.Gen() ? t += 1 : f += 1
	str .= Format("Из {} попыток и с вероятностью {}%, выпало:`nПоложительных "
		. "{}`nОтрицательных {}`n=======================`n", count, prob, t, f)
}
GuiControl, Text, _edit,% str

Return

DoNext:
	if (current_test_number + 1 > tests.Count()) {
		MsgBox Done!
		Return
	} current_test_number += 1
	GuiControl, Disable, _do_next
	GoSub,% tests[ current_test_number ]
Return

DoFullProbListTest:
	str := "Создание списка из элементов, сумма вероятностей использования"
			. " которых равна 100%.`nГенерация в цикле из " . count
			. " итераций:`n"
	GuiControl, Text, _edit,% str
	result := {}
	p_list := new ProbabilityList()
	values := [ 43, 33, 12, 6, 3, 1.5, 1, 0.5 ]
	For i, value in values {
		key := value . "%"
		p_list.AddItem(key, value)
		result[ key ] := 0
	}

	Loop,% count
		result[ p_list.GetItem() ] += 1

	str .= PrintResult(result)
	GuiControl, Text, _edit,% str
	GuiControl, Enable, _do_next
Return

DoOverflowProbListTest:
	str := "Создание списка из элементов, сумма вероятностей использования"
			. " которых превышает 100%.`nГенерация в цикле из " . count
			. " итераций:`n"
	GuiControl, Text, _edit,% str
	result := {}
	p_list := new ProbabilityList()
	values := [ 42, 21, 3.7, 27, 11, 84, 100, 2 ]
	For i, value in values {
		key := value . "%"
		p_list.AddItem(key, value)
		result[ key ] := 0
	}

	Loop,% count
		result[ p_list.GetItem() ] += 1

	str .= PrintResult(result)
		. "`n`nТеперь значения явно не соответствуют ожидаемым вероятностям,"
		. " но, как видно, срабатывания распределяются пропорционально этим "
		. "значениям. Это так же заметно по кратным значениям 21, 42 и 84%."
	GuiControl, Text, _edit,% str
	GuiControl, Enable, _do_next
Return

DoOverflowProbListTest_WithAvailable_Prob:
	str := "Создание списка из элементов, сумма вероятностей использования"
			. " которых превышает 100%, но уже учитывая этот аспект.`nГене"
			. "рация в цикле из " . count . " итераций:`n"
	GuiControl, Text, _edit,% str
	result := {}
	p_list := new ProbabilityList()
	values := [ 42, 21, 3.7, 27, 11, 84, 100, 2 ]
	For i, value in values {
		key := value . "%"
		avlb := p_list.AddItemWhileAvailable(key, value)
		result[ key ] := 0
		if (avlb == 0)
			Break
	}

	Loop,% count
		result[ p_list.GetItem() ] += 1

	str .= PrintResult(result)
		. "`n`nВ этот раз вероятности были рассчитаны корректно, но список"
		. " вместил в себя только пять элементов, поместившихся в лимит. "
		. "К тому же, последний из них(в этом списке он первый) — должен"
		. " был рассчитываться с 11% вероятностью, но был рассчитан с те"
		. "м, что ему осталось от лимита, занятого элементами, попавшими"
		. " в список перед ним(100 - (42 + 21 + 3.7 + 27 = 93.7) = 6.3%)."
	GuiControl, Text, _edit,% str
	GuiControl, Enable, _do_next
Return

DoDeficitProbListTest_WithAvailable_Prob:
	str := "Создание списка из элементов, суммы вероятностей использования"
			. " которых(12 + 2.5 + 13.7 + 24.123 + 0.666 = 52.989) не хват"
			. "ает до 100%.`nГенерация в цикле из " . count . " итераций:`n"
	GuiControl, Text, _edit,% str
	result := {}
	p_list := new ProbabilityList()
	values := [ 12, 2.5, 13.7, 24.123, 0.666 ]
	For i, value in values {
		key := value . "%"
		avlb := p_list.AddItemWhileAvailable(key, value)
		result[ key ] := 0
		if (avlb == 0)
			Break
	}

	Loop,% count
		result[ p_list.GetItem() ] += 1

	str .= PrintResult(result)
		. "`n`nКак и в позапрошлом примере, срабатывания распределяются "
		. "пропорционально значениям, но всё же не отвечают ожиданиям."
	GuiControl, Text, _edit,% str
	GuiControl, Enable, _do_next
Return

DoDeficitProbListTest_WithAvailable_Prob_AndFilling:
	str := "Создание списка из элементов, суммы вероятностей использования"
			. " которых(12 + 2.5 + 13.7 + 24.123 + 0.666 = 52.989) не хват"
			. "ает до 100%, чуть больше 47%.`nГенерация в цикле из " . count
			. " итераций:`n"
	GuiControl, Text, _edit,% str
	result := {}
	p_list := new ProbabilityList()
	values := [ 12, 2.5, 13.7, 24.123, 0.666 ]
	For i, value in values {
		key := value . "%"
		avlb := p_list.AddItemWhileAvailable_WithFilling(key, value)
		result[ key ] := 0
		if (avlb == 0)
			Break
	}

	Loop,% count
		result[ p_list.GetItem() ] += 1

	str .= PrintResult(result)
		. "`n`nТеперь, каждый элемент попавший в список последним, заполняет"
		. " собой всё доступное 'пространство' вероятности, независимо от то"
		. "го, с какой ожидаемой вероятностью он попал в этот список. Наприм"
		. "ер, первый элемент, всегда имеет 100% вероятности быть полученным"
		. " из списка, даже если ожидается, что его вероятность = 5%. Но есл"
		. "и в список попадает следующий элемент, первый, получает свои 5% н"
		. "а шанс, а второму достаются остальные 95%."
	GuiControl, Text, _edit,% str
	GuiControl, Enable, _do_next
Return

DoDeficitProbListTest_WithAvailable_Prob_AndZeroFilling:
	str := "Создание списка из элементов, суммы вероятностей использования"
			. " которых, как и прежде(12 + 2.5 + 13.7 + 24.123 + 0.666 = 5"
			. "2.989), не хватает до 100%, чуть более 47%.`nГенерация в ц"
			. "икле из " . count . " итераций:`n"
	GuiControl, Text, _edit,% str
	result := {0: 0}
	p_list := new ProbabilityList()
	values := [ 12, 2.5, 13.7, 24.123, 0.666 ]
	For i, value in values {
		key := value . "%"
		avlb := p_list.AddItemWhileAvailable_WithZeroFilling(key, value)
		result[ key ] := 0
		if (avlb == 0)
			Break
	}

	Loop,% count
		result[ p_list.GetItem() ] += 1

	str .= PrintResult(result)
		. "`n`nВ этот раз, оставшуюся вероятность заполняет собой элемент, "
		. "возвращающий ноль. Если из списка нужно получать элементы строго"
		. " соответствуя ожиданиям, то возвращаемый ноль можно просто отбрас"
		. "ывать из результатов."
	GuiControl, Text, _edit,% str
	GuiControl, Enable, _do_next
Return

GuiClose:
	ExitApp

PrintResult(result) {
	str := "{`n    "
	For k, v in result
		str .= Format("'{}':`t{}`n    ", k, v)
	return RTrim(str, " ") . "}"
}