не всё так просто. в начале у нас будет выбираться элемент с вероятностью 0,2. А в конце пойдут два оставшиеся с веротностью 0.5. И в конце на больших длинах получается bcbcbcbcbc или acacacacac. Поэтому я и заполняю его не по порядку, а слуайным образом.<br>

<br><div class="gmail_quote">2009/12/23 Ruslan Zakirov <span dir="ltr">&lt;<a href="mailto:ruslan.zakirov@gmail.com">ruslan.zakirov@gmail.com</a>&gt;</span><br><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex;">

Привет, 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)) &gt; 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) Если есть группа в критичном состоянии, то берем элемент из нее. к пункту 0<br>
2) Иначе выбираем &quot;случайно&quot; группу (пропорционально длиннам),<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( &#39; &#39;, @e ), &quot;\n&quot;;<br>
print join( &#39; &#39;, @res ), &quot;\n&quot;;<br>
<br>
sub find_critical {<br>
    my $critical;<br>
    my ($max, $rest) = (0, 0);<br>
    foreach my $e ( keys %g ) {<br>
        if ( $g{$e} &gt; $max ) {<br>
            $rest += $max;<br>
            $max = $g{$e};<br>
            $critical = $e;<br>
        } else {<br>
            $rest += $g{$e};<br>
        }<br>
    }<br>
    return undef if $max &lt; $rest + 1;<br>
    return $critical if $max == $rest + 1;<br>
    die &quot;No solution, too many &#39;$critical&#39; elements&quot;;<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>
<font color="#888888"><br>
<br>
<br>
--<br>
Best regards, Ruslan.<br>
</font><div><div></div><div class="h5">--<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>