Возьмём 3000 позиций. Тогда с довольно большой вероятностью у нас закончится какой-то элемент раньше. Например на 2900-м элементе. После чего пойдёт bcbcbcbcbcbcbc.<div>Я это решал заполнением массива не по порядку, а случайным образом.<br>
<br><div class="gmail_quote">2009/12/23 Ruslan Zakirov <span dir="ltr"><<a href="mailto:ruslan.zakirov@gmail.com">ruslan.zakirov@gmail.com</a>></span><br><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex;">
Ну не совсем так. По разному, но в общем у низкочастотного эелемента<br>
мало шансов появится в начале.<br>
<br>
Что понимать под равномерной тогда? Если у нас 2 элемента X и всего 20<br>
позиций, то на каких местах лучше разместить элементы X?<br>
<br>
* 1, 20?<br>
* 5, 15?<br>
<br>
Все это решаемо вполне.<br>
<div class="im"><br>
2009/12/23 Андрей Костенко <<a href="mailto:andrey@kostenko.name">andrey@kostenko.name</a>>:<br>
</div><div><div></div><div class="h5">> не всё так просто. в начале у нас будет выбираться элемент с вероятностью<br>
> 0,2. А в конце пойдут два оставшиеся с веротностью 0.5. И в конце на больших<br>
> длинах получается bcbcbcbcbc или acacacacac. Поэтому я и заполняю его не по<br>
> порядку, а слуайным образом.<br>
><br>
> 2009/12/23 Ruslan Zakirov <<a href="mailto:ruslan.zakirov@gmail.com">ruslan.zakirov@gmail.com</a>><br>
>><br>
>> Привет, dvhillard :)<br>
>><br>
>> Введение:<br>
>><br>
>> 1) сгруппируем одинаковые элементы<br>
>> 2) введем L(g) - длина группы<br>
>> 3) задача отсутствия повторений не решается, если существует группа i,<br>
>> где L(G(i)) = MAX(L(G(j))) для любого j и L(G(i)) > SUM(L(G(j)))+1 для<br>
>> люого j != i. По простецки - если группа с максимальной длинной<br>
>> длиннее объединения всех остальных групп. Доказать элементарно.<br>
>> 4) Введем понятие группа i в критичном состоянии, если L(G(i)) =<br>
>> SUM(L(G(j))) + 1 где j != i. Доказательством от противного легко<br>
>> доказывается, что в наборе не может быть две группы в критичном<br>
>> состоянии. Понятно, что такая группа может иметь только максимальную<br>
>> длинну во всем наборе.<br>
>><br>
>> Алгоритм:<br>
>> 0) Конец, если все группы пусты<br>
>> 1) Если есть группа в критичном состоянии, то берем элемент из нее. к<br>
>> пункту 0<br>
>> 2) Иначе выбираем "случайно" группу (пропорционально длиннам),<br>
>> исключая группу с предыдущим элементом. К пункту 0<br>
>><br>
>> Одна и таже группа не может стать два раза подряд критичной, а значит<br>
>> мы не сможем нарушить условие неповторения элементов. Если мы выбрали<br>
>> элемент в пункте 2, то невозможно, что эта группа будет критичной на<br>
>> следующем цикле, а следовательно не нарушается условие неповторения.<br>
>><br>
>> Из всего вышесказанного следует, что решение существует, при<br>
>> соблюдении условия 3.<br>
>><br>
>> Вот и простой код в лоб:<br>
>><br>
>> use strict;<br>
>> use warnings;<br>
>><br>
>> my @e = qw(a a a a a b b b c c c c d e e e e e e e e e e e e e e);<br>
>> my %g;<br>
>> $g{$_}++ foreach @e;<br>
>><br>
>> my @res;<br>
>><br>
>> my $last;<br>
>> while ( keys %g ) {<br>
>> my $pick = find_critical();<br>
>> unless ( defined $pick ) {<br>
>> $pick = pick_except_last();<br>
>> }<br>
>> $g{$pick}--;<br>
>> delete $g{$pick} unless $g{$pick};<br>
>> push @res, $last = $pick;<br>
>> }<br>
>><br>
>> print join( ' ', @e ), "\n";<br>
>> print join( ' ', @res ), "\n";<br>
>><br>
>> sub find_critical {<br>
>> my $critical;<br>
>> my ($max, $rest) = (0, 0);<br>
>> foreach my $e ( keys %g ) {<br>
>> if ( $g{$e} > $max ) {<br>
>> $rest += $max;<br>
>> $max = $g{$e};<br>
>> $critical = $e;<br>
>> } else {<br>
>> $rest += $g{$e};<br>
>> }<br>
>> }<br>
>> return undef if $max < $rest + 1;<br>
>> return $critical if $max == $rest + 1;<br>
>> die "No solution, too many '$critical' elements";<br>
>> }<br>
>><br>
>> sub pick_except_last {<br>
>> my @tmp;<br>
>> while ( my ($k,$v) = each %g ) {<br>
>> next if defined $last and $last eq $k;<br>
>> push @tmp, ($k) x $v;<br>
>> }<br>
>> return $tmp[ int rand @tmp ];<br>
>> }<br>
>><br>
>><br>
>><br>
>> --<br>
>> Best regards, Ruslan.<br>
>> --<br>
>> Moscow.pm mailing list<br>
>> <a href="mailto:moscow-pm@pm.org">moscow-pm@pm.org</a> | <a href="http://moscow.pm.org" target="_blank">http://moscow.pm.org</a><br>
><br>
><br>
> --<br>
> Moscow.pm mailing list<br>
> <a href="mailto:moscow-pm@pm.org">moscow-pm@pm.org</a> | <a href="http://moscow.pm.org" target="_blank">http://moscow.pm.org</a><br>
><br>
><br>
<br>
<br>
<br>
</div></div>--<br>
<div><div></div><div class="h5">Best regards, Ruslan.<br>
--<br>
Moscow.pm mailing list<br>
<a href="mailto:moscow-pm@pm.org">moscow-pm@pm.org</a> | <a href="http://moscow.pm.org" target="_blank">http://moscow.pm.org</a><br>
</div></div></blockquote></div><br></div>