[Moscow.pm] Равномерная, рандомная сортировка

[Андрей Костенко]

Возьмём 3000 позиций. Тогда с довольно большой вероятностью у нас закончится
какой-то элемент раньше. Например на 2900-м элементе. После чего пойдёт
bcbcbcbcbcbcbc.
Я это решал заполнением массива не по порядку, а случайным образом.

2009/12/23 Ruslan Zakirov <ruslan.zakirov на gmail.com>

> Ну не совсем так. По разному, но в общем у низкочастотного эелемента
> мало шансов появится в начале.
>
> Что понимать под равномерной тогда? Если у нас 2 элемента X и всего 20
> позиций, то на каких местах лучше разместить элементы X?
>
> * 1, 20?
> * 5, 15?
>
> Все это решаемо вполне.
>
> 2009/12/23 Андрей Костенко <andrey на kostenko.name>:
> > не всё так просто. в начале у нас будет выбираться элемент с вероятностью
> > 0,2. А в конце пойдут два оставшиеся с веротностью 0.5. И в конце на
> больших
> > длинах получается bcbcbcbcbc или acacacacac. Поэтому я и заполняю его не
> по
> > порядку, а слуайным образом.
> >
> > 2009/12/23 Ruslan Zakirov <ruslan.zakirov на gmail.com>
> >>
> >> Привет, 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
> >> moscow-pm на pm.org | http://moscow.pm.org
> >
> >
> > --
> > Moscow.pm mailing list
> > moscow-pm на pm.org | http://moscow.pm.org
> >
> >
>
>
>
> --
> Best regards, Ruslan.
> --
> Moscow.pm mailing list
> moscow-pm на pm.org | http://moscow.pm.org
>
----------- следущая часть -----------
Вложение в формате HTML было извлечено&hellip;
URL: <http://mail.pm.org/pipermail/moscow-pm/attachments/20091223/8bc97ba4/attachment-0001.html>