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

[Ruslan Zakirov]

Ну не совсем так. По разному, но в общем у низкочастотного эелемента
мало шансов появится в начале.

Что понимать под равномерной тогда? Если у нас 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.