Генерація множини всіх підмножин рекурсією

Основи мови Java

23 aug 2014 18:54

Допоможіть розібратися з цим моментом (має вирішувати рекурсивним методом):

Наприклад, є клас AudioTrack з тривалістю треку в секундах duration.

Метод класу приймає список треків та максимальну тривалість плей аркуша в секундах. Тривалість кожного з прийнятих треків у вхідному аркуші не більше максимальної тривалості ПлейЛіста в секундах (maxPlayListDuration). На виході повинні вийти всі можливі комбінації треків, загальна тривалість яких не перевищує maxPlayListDuration. Комбінації можуть бути різними, як з одного треку, так і двох, трьох і так далі. Вхідний список також може складатися від одного і більше треків.

Правильні комбінації такі: Вхід - трек1, трек2, трек3

Вихід: трек1 трек2 трек3 трек1, трек2 трек2, трек3 трек1, трек3 трек1, трек2, трек3

Так неправильно: трек1, трек2 трек2, трек1 трек3, трек3, трек3 (тобто йде відбір за вмістом, а не від перестановки).

Змінено:23 Сер 2014 16:34

23 aug 2014 20:12

Хм. Ну, а що саме вам не зрозуміло? Завдання досить чітко описане. Пишіть, якщо будуть питання – показуйте код і задавайте :)

У методі перебираєте всі треки починаючи із заданого і для кожного з них викликаєте цей же метод, передаючи йому цей трек і суму, що виходить. Загалом досить прямолінійно вирішується. Тобто. якось так:

Залишилося лише умови відсікання та складання до списку додати.

Змінено:23 aug 2014 13:15

24 aug 2014 00:02

Хм. Ну, а що саме вам не зрозуміло? Завдання досить чітко описане. Пишіть, якщо будуть питання – показуйте код і задавайте :)

У методі перебираєте всі треки починаючи із заданого і для кожного з них викликаєте цей же метод, передаючи йому цей трек і суму, що виходить. Загалом досить прямолінійно вирішується. Тобто. якось так:

Залишилося лише умови відсікання та складання до списку додати.

Дякую, намагаюся перетравити інформацію :)

Тут, зважаючи на все, лежить в основі алгоритм "Багато всіх підмножин", в англійській літературі "power set". Переглянув багато інформації, але виразного наочного прикладу ніхто на java не наводить.

У даному пості людина на простому прикладі навів цей алгоритм з рекурсією, але, на жаль, на пітоні.

Було б чудово якби хтось навів цей алгоритм рекурсією на простих даних. А то зовсім він не піддається:)

Для List [10, 20, 30] Отримаємо List > :

24 aug 2014 00:30

Було б чудово якби дехто цей дуже простий алгоритм обдумав і написав самостійно, а не намагався злизати звідки :)

Ви ж, мабуть, намагаєтеся програму навчитися - самі розумієте тут важливо розбиратися і винаходити самостійно - зате потім все буде дуже легко.

Вам насправді не всі підмножини потрібні, тому у вас ще буде відсікання.

Можете спробувати вирішити такі підзавдання:

1. Рекурсивно згенерувати перелік різних комбінацій по 3 з N треків (можливо з повторами), тобто.

трек1, трек1, трек1 трек1, трек1, трек2 трек1, трек1, трек3 трек1, трек1, трек4 трек1, трек2, трек1 . трек4, трек4, трек4

2. Переробити так, щоб повторів був. Для цього достатньо щоб усередині комбінації кожен наступний трек був більшим (за номером)

трек1, трек2, трек3 трек1, трек2, трек4 . трек2, трек3, трек4

3.Переробити цей алгоритм щоб виводилися тільки комбінації у яких сумарний час менший за заданий.

4. Переробити алгоритм, що вийшов, щоб комбінації не обмежувалися 3 треками, а заходили вглиб рекурсії поки не вийдуть за межі часу.

Якось так. Звичайно тут кілька зайвої роботи вийде, зате рекурсія в голові добре осяде.

---