2009/12/23 Андрей Костенко <[email protected]>: > Возьмём 3000 позиций. Тогда с довольно большой вероятностью у нас закончится > какой-то элемент раньше. Например на 2900-м элементе. После чего пойдёт > bcbcbcbcbcbcbc.
Почему? Вероятности вы определяете. Конечно такое получиться если у вас 3000 элементов A, B, C и из них только небольшая доля элементов A. Например, если 100 A на 3000 ABC, то вероятность появления хотя бы одного A в последних 30 элементах должна быть близка к 1, а иначе у вас не получиться равномерное распределение элементов. Опять же возникает вопрос. Нужно найти решение, которое наиболее близкое к равномерному? Или любое, которое более или менее равномерное? > Я это решал заполнением массива не по порядку, а случайным образом. Я пропустил решение? Я точно где-то что-то упустил и чего-то не понимаю. > > 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 > > -- Best regards, Ruslan. -- Moscow.pm mailing list [email protected] | http://moscow.pm.org
