forum.opennet.ru - "Алгоритм рассортировки плейлиста." (6)

форумы

помощь

поиск

регистрация

майллист

вход/выход

слежка

"Алгоритм рассортировки плейлиста."

Форум Программирование под UNIX (Perl)
Вариант для распечатки		Пред. тема \| След. тема
Изначальное сообщение		[ Отслеживать ]

"Алгоритм рассортировки плейлиста."	+/–
Сообщение от Azudim (??) on 22-Май-11, 14:05
Добрый день! Подскажите может кто сталкивался с похожей задачей: Дано: 3 аудио трека. Трек 1: Длительность 20с. Количество повторов: 3 раза. Трек 2: 10с x 5раз. Трек 3: 7c x 7раз. Из этих треков формируется плей-лист, включающий каждый трек заданное количество раз. Общая длина трека получается: 20x3+10x5+7x7 = 159c Задача - алгоритм сортировки плейлиста таким образом, что бы каждый трек был максимально удален от своих повторов (от самого себя). При это сам плейлист будет постоянно повторяться, и удаление треков должно учитывать предыдущий и следующий проигрыш трека. Т.е. треки в плейлисте надо перемешать так, что бы Трек{n} не повторялся в ряд, а был рассредоточен по плейлисту.
Ответить \| Правка \| Cообщить модератору

Оглавление

Алгоритм рассортировки плейлиста., NuINu, 21:53 , 22-Май-11, (1)
Алгоритм рассортировки плейлиста., cryo, 22:34 , 22-Май-11, (2)

Алгоритм рассортировки плейлиста., Azudim, 23:21 , 22-Май-11, (3)

Алгоритм рассортировки плейлиста., ACCA, 00:59 , 23-Май-11, (4)

Алгоритм рассортировки плейлиста., Azudim, 16:31 , 13-Июн-11, (5)

Алгоритм рассортировки плейлиста., ACCA, 22:14 , 13-Июн-11, (6)

Сообщения по теме [Сортировка по времени | RSS]

1. "Алгоритм рассортировки плейлиста." +/–

Сообщение от NuINu (??) on 22-Май-11, 21:53

>[оверквотинг удален]
>  Трек 2: 10с x 5раз.
>  Трек 3: 7c x 7раз.
>  Из этих треков формируется плей-лист, включающий каждый трек заданное количество раз.
>  Общая длина трека получается: 20x3+10x5+7x7 = 159c
>  Задача - алгоритм сортировки плейлиста таким образом, что бы каждый трек
> был максимально удален от своих повторов (от самого себя). При это
> сам плейлист будет постоянно повторяться, и удаление треков должно учитывать предыдущий
> и следующий проигрыш трека.
>  Т.е. треки в плейлисте надо перемешать так, что бы Трек{n} не
> повторялся в ряд, а был рассредоточен по плейлисту.
казалось бы при чем тут перл?
ну ладно, знание перла вам тут не поможет.
Я бы решил эту задачку используя теорию графов. почитайте, может что нибудь и сделаете.

Ответить | Правка | ^ к родителю #0 | Наверх | Cообщить модератору

2. "Алгоритм рассортировки плейлиста." +/–

Сообщение от cryo (ok) on 22-Май-11, 22:34

Правильно советут. Начните не с выбора языка, а с решения задачи математически.
Попробуйте применить методы решения задачи коммивояжера, только целью должен быть самый длинный, а не короткий путь.
Методы решения можно поискать в учебниках по оптимизации.
Начните здесь
http://ru.wikipedia.org/wiki/%D0%97%D0%B...
http://ru.wikipedia.org/wiki/%D0%9E%D0%B...
Методов решения задачи много. Но если вам не нужен _абсолютно_ лучший вариант, а достаточно просто хорошего решения, посмотрите в сторону
http://roboforum.ru/wiki/%D0%93%D0%B5�...

Ответить | Правка | ^ к родителю #0 | Наверх | Cообщить модератору

3. "Алгоритм рассортировки плейлиста." +/–

Сообщение от Azudim (??) on 22-Май-11, 23:21

Perl как тэг был выбран от ощущения, что тут то серьезные люди остались =)
пока копаю в сторону "Алгоритмы и методы решения задач составления
расписаний и других экстремальных задач
на графах больших размерностей", но увы математическим образованием блеснуть не могу..

Ответить | Правка | ^ к родителю #2 | Наверх | Cообщить модератору

4. "Алгоритм рассортировки плейлиста." +/–

Сообщение от ACCA (ok) on 23-Май-11, 00:59

> пока копаю в сторону "Алгоритмы и методы решения задач составления
> расписаний и других экстремальных задач
> на графах больших размерностей", но увы математическим образованием блеснуть не могу..
Динамическое программирование, рекурсия с запоминанием пути.

my @c = (3,5,7);
my @pl = ();
sub trial
{
    my $t = shift;
    push @pl, $t;
    $c[$t]--;
    for (my $nxt = 0; $nxt < 3; $nxt++) {
        next if ($t == $nxt || $c[$nxt] < 1);
        trial($nxt);
    }
    print join(' ', @pl),"\n" if (@pl > 14 && $pl[0] != $pl[14]);
    $c[$t]++;
    pop @pl;
}
for (my $i=0;$i< 3; $i++) {
    trial($i);
}

Получаешь 450 возможных решений, находишь оптимум.
Ты недостаточно хорошо определил метрику для оптимизации. Разберись, что и в чём ты меряешь, когда говоришь о "максимальном удалении" для всей кучи.

Ответить | Правка | ^ к родителю #3 | Наверх | Cообщить модератору

5. "Алгоритм рассортировки плейлиста." +/–

Сообщение от Azudim (??) on 13-Июн-11, 16:31

> Получаешь 450 возможных решений, находишь оптимум.
Не совсем понял, что значит результат 450 ?
Если считать что будет 3+5+7=15 проигрышей роликов, то количество уникальных комбинаций
их последовательности будет 43589145600.
Для n количества повторов количество комбинаций получаю по формуле
   F{n} = F{n-1}*n
my @f = (); my $n = 15;  $f[3] = 3;
   for (my $i = 4; $i < $n; $i++) {
    $f[$i] = $f[$i-1]*$i;
   }
print $f[$n];
это как я понял классическая задача динамического программирования, аля числа Фибоначчи.

Ответить | Правка | ^ к родителю #4 | Наверх | Cообщить модератору

6. "Алгоритм рассортировки плейлиста." +/–

Сообщение от ACCA (ok) on 13-Июн-11, 22:14

>  Если считать что будет 3+5+7=15 проигрышей роликов, то количество уникальных комбинаций
>  их последовательности будет 43589145600.
Не всякая последовательность роликов удовлетворяет уже известным условиям. Выбрось те, в которых есть повторы или получится повтор при зацикливании.
Разберись в коде - динамические алгоритмы нельзя просто просматривать, придётся понять, для чего нужно каждое условие. Либо верить, что все они правильные.

Ответить | Правка | ^ к родителю #5 | Наверх | Cообщить модератору

Архив | Удалить

Рекомендовать для помещения в FAQ | Индекс форумов | Темы | Пред. тема | След. тема

Партнёры:

Хостинг:

Закладки на сайте
Проследить за страницей

Created 1996-2024 by Maxim Chirkov
Добавить, Поддержать, Вебмастеру

1. "Алгоритм рассортировки плейлиста."	+/–
Сообщение от NuINu (??) on 22-Май-11, 21:53
>[оверквотинг удален] > Трек 2: 10с x 5раз. > Трек 3: 7c x 7раз. > Из этих треков формируется плей-лист, включающий каждый трек заданное количество раз. > Общая длина трека получается: 20x3+10x5+7x7 = 159c > Задача - алгоритм сортировки плейлиста таким образом, что бы каждый трек > был максимально удален от своих повторов (от самого себя). При это > сам плейлист будет постоянно повторяться, и удаление треков должно учитывать предыдущий > и следующий проигрыш трека. > Т.е. треки в плейлисте надо перемешать так, что бы Трек{n} не > повторялся в ряд, а был рассредоточен по плейлисту. казалось бы при чем тут перл? ну ладно, знание перла вам тут не поможет. Я бы решил эту задачку используя теорию графов. почитайте, может что нибудь и сделаете.
Ответить \| Правка \| ^ к родителю #0 \| Наверх \| Cообщить модератору

2. "Алгоритм рассортировки плейлиста."	+/–
Сообщение от cryo (ok) on 22-Май-11, 22:34
Правильно советут. Начните не с выбора языка, а с решения задачи математически. Попробуйте применить методы решения задачи коммивояжера, только целью должен быть самый длинный, а не короткий путь. Методы решения можно поискать в учебниках по оптимизации. Начните здесь http://ru.wikipedia.org/wiki/%D0%97%D0%B... http://ru.wikipedia.org/wiki/%D0%9E%D0%B... Методов решения задачи много. Но если вам не нужен _абсолютно_ лучший вариант, а достаточно просто хорошего решения, посмотрите в сторону http://roboforum.ru/wiki/%D0%93%D0%B5�...
Ответить \| Правка \| ^ к родителю #0 \| Наверх \| Cообщить модератору


	3. "Алгоритм рассортировки плейлиста."	+/–
	Сообщение от Azudim (??) on 22-Май-11, 23:21
	Perl как тэг был выбран от ощущения, что тут то серьезные люди остались =) пока копаю в сторону "Алгоритмы и методы решения задач составления расписаний и других экстремальных задач на графах больших размерностей", но увы математическим образованием блеснуть не могу..
	Ответить \| Правка \| ^ к родителю #2 \| Наверх \| Cообщить модератору


	4. "Алгоритм рассортировки плейлиста."	+/–
	Сообщение от ACCA (ok) on 23-Май-11, 00:59
	> пока копаю в сторону "Алгоритмы и методы решения задач составления > расписаний и других экстремальных задач > на графах больших размерностей", но увы математическим образованием блеснуть не могу.. Динамическое программирование, рекурсия с запоминанием пути. my @c = (3,5,7); my @pl = (); sub trial { my $t = shift; push @pl, $t; $c[$t]--; for (my $nxt = 0; $nxt < 3; $nxt++) { next if ($t == $nxt \|\| $c[$nxt] < 1); trial($nxt); } print join(' ', @pl),"\n" if (@pl > 14 && $pl[0] != $pl[14]); $c[$t]++; pop @pl; } for (my $i=0;$i< 3; $i++) { trial($i); } Получаешь 450 возможных решений, находишь оптимум. Ты недостаточно хорошо определил метрику для оптимизации. Разберись, что и в чём ты меряешь, когда говоришь о "максимальном удалении" для всей кучи.
	Ответить \| Правка \| ^ к родителю #3 \| Наверх \| Cообщить модератору


	5. "Алгоритм рассортировки плейлиста."	+/–
	Сообщение от Azudim (??) on 13-Июн-11, 16:31
	> Получаешь 450 возможных решений, находишь оптимум. Не совсем понял, что значит результат 450 ? Если считать что будет 3+5+7=15 проигрышей роликов, то количество уникальных комбинаций их последовательности будет 43589145600. Для n количества повторов количество комбинаций получаю по формуле F{n} = F{n-1}n my @f = (); my $n = 15; $f[3] = 3; for (my $i = 4; $i < $n; $i++) { $f[$i] = $f[$i-1]$i; } print $f[$n]; это как я понял классическая задача динамического программирования, аля числа Фибоначчи.
	Ответить \| Правка \| ^ к родителю #4 \| Наверх \| Cообщить модератору


	6. "Алгоритм рассортировки плейлиста."	+/–
	Сообщение от ACCA (ok) on 13-Июн-11, 22:14
	> Если считать что будет 3+5+7=15 проигрышей роликов, то количество уникальных комбинаций > их последовательности будет 43589145600. Не всякая последовательность роликов удовлетворяет уже известным условиям. Выбрось те, в которых есть повторы или получится повтор при зацикливании. Разберись в коде - динамические алгоритмы нельзя просто просматривать, придётся понять, для чего нужно каждое условие. Либо верить, что все они правильные.
	Ответить \| Правка \| ^ к родителю #5 \| Наверх \| Cообщить модератору