вывод элементов массива по вероятностям

[antonim]

вывод элементов массива по вероятностям

пример: массив

a
a
a
a
a
a
b
b
b
c
c
c

и нужно равномерно вывести его вот таким образом

a
b
a
c
a
b
a
c
a
b
a
c


1-й шаг: для кадого я нашел вероятность вывода

теперь вопрос как вывести значения так как надо?

 

[Adelf]

У тебя есть хоть какие-нибудь мысли? Имхо, алгоритм почти на виду.

 

[dimagolov]

равомерно к вероятности не имеет никакого отношения.

 

[Adelf]

З.Ы. "Равномерно" - это по твоему как? С равномерным распределением что-то общее имеет?

(вопрос топикстартеру это)

 

[antonim]

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

 

[dimagolov]

antonim, разговора у нас не сложится, пока ты будешь тулить слово "вероятность". Если тебе нужно вывести значения, чтобы в полученном массиве они встречались с определенной вероятностью, то это задача №1, если тебе надо их распределить равномерно, то это задача №2. ОБЩЕГО МЕЖДУ НИМИ НЕТ НИЧЕГО, потому что решений у №1 бесконечное множество (в общем случае), а у №2 только одно.

Определись, какой номер тебе нужен.

 

[Adelf]

Ну в общем мой алгоритм распределил как я считал равномерно и на твоих данных получилось:

a
b
c
a
a
c
b
a
a
c
b
a

Что наверно тебе не подойдет. Похоже тебе надо, чтобы между каждыми двумя одинаковыми буквами была какая-то другая. Так чтоли.?..

 

[antonim]

Автор оригинала: dimagolov
antonim, разговора у нас не сложится, пока ты будешь тулить слово "вероятность". Если тебе нужно вывести значения, чтобы в полученном массиве они встречались с определенной вероятностью, то это задача №1, если тебе надо их распределить равномерно, то это задача №2. ОБЩЕГО МЕЖДУ НИМИ НЕТ НИЧЕГО, потому что решений у №1 бесконечное множество (в общем случае), а у №2 только одно.

Определись, какой номер тебе нужен.

посчитать вероятности - это просто первое, что пришло мне в голову. Задача - "распределить равномерно"

 

[dimagolov]

Adelf, ну куда ты торопишься? Путь ТС определиться что именно ему нужно, а уж потом поговорим о критериях равномерности

 

[antonim]

Автор оригинала: Adelf
Что наверно тебе не подойдет. Похоже тебе надо, чтобы между каждыми двумя одинаковыми буквами была какая-то другая. Так чтоли.?..

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

 

[dimagolov]

Ага. Раз распределить равномерно, то, могу на вскидку предложить такие критерии:
Для простоты терминологии заменим массив отрезком целочисленной прямой, а элементы значениями ф-ии на этой прямой. Тогда отрезок будет областью ее определения.
1. Одно и то же значение встречается а произвольном отрезке определенной длинны, который является часть области определения, одинаковое число раз. Математически наиболее строгое определение, но мало что дающее для построения алгоритма
2. Расстояния между одними и теми же элементами равны, так проще строить алгоритм.

 

[Adelf]

Ну на самом деле конечно это у меня как раз получилось равномерно а что тебе нужно мы так и не выяснили еще

Похоже тебе надо, чтобы между каждыми двумя одинаковыми буквами была какая-то другая. Так чтоли?

Ответь.

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

 

[dimagolov]

Похоже тебе надо, чтобы между каждыми двумя одинаковыми буквами была какая-то другая. Так чтоли?

это мало что общего с равномерностью имеет. Если у нас 20 A и 3 B, то равно мерно их распределить то можно, а вот сделать то, что ты хочешь - никак.

-~{}~ 11.08.09 10:09:

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

ничего подобного. ни 1-му ни 2-му критериям твое размещение не удовлетворяет. Кстати, они по логике эквивалентны, но лень доказывать строго.

 

[Adelf]

это мало что общего с равномерностью имеет. Если у нас 20 A и 3 B, то равно мерно их распределить то можно, а вот сделать то, что ты хочешь - никак.

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

 

[dimagolov]

кстати, тут идея алгоритма пришла в голову.
1. Сортируем значения по кол-ву повторений (по убыванию)
2. Строим массив из тех элементов, кол-во которых максимально
3. Теперь итерация по следующему не распределенному значению.
Очевидно, что длинна полученного после этого шага массива будет count($cur) + $curValCount и его элементы надо побить на $curValCount отрезков (т.е. длинной count($cur)/$curValCount + 1), в центре каждого надо поместить текущий элемент.
Первый индекс, в который надо вставить элемент (раздвинув текущий массив) будет (count($cur)/$curValCount + 1) / 2, второй +(count($cur)/$curValCount + 1) и т.д.

 

[Adelf]

Вообще, если действительно надо найти способ расположить так, чтобы одинаковые не повторялись или сказать что это невозможно - задача интересна.
решение похожее на эти "(count($cur)/$curValCount + 1) / 2" будто бы вертится в голове, но чет пока уловить не могу Скорей всего такое на олимпиадных точно было.

 

[dimagolov]

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

это никоим боком к задачи ТС не относится...

 

[antonim]

Adelf, можно на твой алгоритм глянуть?

 

[Adelf]

Он на работе остался

Щас вот повторил вроде. Он простой. Тупо каждая из букв "раскидывается" равными отрезками по отрезку 0, 1. И смотрим как они рассыпались в итоге.

$arr['a'] = 6;
$arr['b'] = 3;
$arr['c'] = 3;

$arr2 = array();
foreach($arr as $key => $val)
{
	for($i = 0; $i < $val; $i++)
	{
		$arr2[$key.$i] = (1.0 / ($val + 1)) * ($i + 1);
	}
}

arsort($arr2);


foreach($arr2 as $key => $val)
{
	echo $key[0].'<br />';
}

 

[dimagolov]

Adelf, у тебя на краях не равномерное распределение:
10 элементов распределятся по координатам от 1/11 до 10/11, то есть на крайних участках длинной > 1/11 всегда будет на один элемент меньше, чем на любых не крайних.

скорректируй по моей формуле про N отрезков и элемент в их середине