Возьмём 3000 позиций. Тогда с довольно большой вероятностью у нас закончится какой-то элемент раньше. Например на 2900-м элементе. После чего пойдёт bcbcbcbcbcbcbc. Я это решал заполнением массива не по порядку, а случайным образом.
2009/12/23 Ruslan Zakirov <[email protected]> > Ну не совсем так. По разному, но в общем у низкочастотного эелемента > мало шансов появится в начале. > > Что понимать под равномерной тогда? Если у нас 2 элемента X и всего 20 > позиций, то на каких местах лучше разместить элементы X? > > * 1, 20? > * 5, 15? > > Все это решаемо вполне. > > 2009/12/23 Андрей Костенко <[email protected]>: > > не всё так просто. в начале у нас будет выбираться элемент с вероятностью > > 0,2. А в конце пойдут два оставшиеся с веротностью 0.5. И в конце на > больших > > длинах получается bcbcbcbcbc или acacacacac. Поэтому я и заполняю его не > по > > порядку, а слуайным образом. > > > > 2009/12/23 Ruslan Zakirov <[email protected]> > >> > >> Привет, dvhillard :) > >> > >> Введение: > >> > >> 1) сгруппируем одинаковые элементы > >> 2) введем L(g) - длина группы > >> 3) задача отсутствия повторений не решается, если существует группа i, > >> где L(G(i)) = MAX(L(G(j))) для любого j и L(G(i)) > SUM(L(G(j)))+1 для > >> люого j != i. По простецки - если группа с максимальной длинной > >> длиннее объединения всех остальных групп. Доказать элементарно. > >> 4) Введем понятие группа i в критичном состоянии, если L(G(i)) = > >> SUM(L(G(j))) + 1 где j != i. Доказательством от противного легко > >> доказывается, что в наборе не может быть две группы в критичном > >> состоянии. Понятно, что такая группа может иметь только максимальную > >> длинну во всем наборе. > >> > >> Алгоритм: > >> 0) Конец, если все группы пусты > >> 1) Если есть группа в критичном состоянии, то берем элемент из нее. к > >> пункту 0 > >> 2) Иначе выбираем "случайно" группу (пропорционально длиннам), > >> исключая группу с предыдущим элементом. К пункту 0 > >> > >> Одна и таже группа не может стать два раза подряд критичной, а значит > >> мы не сможем нарушить условие неповторения элементов. Если мы выбрали > >> элемент в пункте 2, то невозможно, что эта группа будет критичной на > >> следующем цикле, а следовательно не нарушается условие неповторения. > >> > >> Из всего вышесказанного следует, что решение существует, при > >> соблюдении условия 3. > >> > >> Вот и простой код в лоб: > >> > >> use strict; > >> use warnings; > >> > >> 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); > >> my %g; > >> $g{$_}++ foreach @e; > >> > >> my @res; > >> > >> my $last; > >> while ( keys %g ) { > >> my $pick = find_critical(); > >> unless ( defined $pick ) { > >> $pick = pick_except_last(); > >> } > >> $g{$pick}--; > >> delete $g{$pick} unless $g{$pick}; > >> push @res, $last = $pick; > >> } > >> > >> print join( ' ', @e ), "\n"; > >> print join( ' ', @res ), "\n"; > >> > >> sub find_critical { > >> my $critical; > >> my ($max, $rest) = (0, 0); > >> foreach my $e ( keys %g ) { > >> if ( $g{$e} > $max ) { > >> $rest += $max; > >> $max = $g{$e}; > >> $critical = $e; > >> } else { > >> $rest += $g{$e}; > >> } > >> } > >> return undef if $max < $rest + 1; > >> return $critical if $max == $rest + 1; > >> die "No solution, too many '$critical' elements"; > >> } > >> > >> sub pick_except_last { > >> my @tmp; > >> while ( my ($k,$v) = each %g ) { > >> next if defined $last and $last eq $k; > >> push @tmp, ($k) x $v; > >> } > >> return $tmp[ int rand @tmp ]; > >> } > >> > >> > >> > >> -- > >> Best regards, Ruslan. > >> -- > >> Moscow.pm mailing list > >> [email protected] | http://moscow.pm.org > > > > > > -- > > Moscow.pm mailing list > > [email protected] | http://moscow.pm.org > > > > > > > > -- > Best regards, Ruslan. > -- > Moscow.pm mailing list > [email protected] | http://moscow.pm.org >
-- Moscow.pm mailing list [email protected] | http://moscow.pm.org
