[C# EXAM] Part 2 They are green - Обяснение на алгоритъма


-1

Здравейте колеги!

Не мога да разбера алгоритъма, който е използван в авторското решение на тази задача. Няколко пъти дебъгвам вече, но не успявам да го схвана. Пермутации, сортирания и обръщания на масиви - пълна лудница.

Може ли някой да го формулира на човешки език!




Отговори



1

Авторското решение използва следния алгоритъм за генериране на пермутации в лексикографски порядък.

(мой превод от книгата The Art of Computer Programming на Donald Knuth, част 4, глава 7.2.1.2)

Сортираме елементите във възходящ ред:

а[0] <= a[1] <= a[2] <= ... <= a[N].

Това ни е първата пермутация.

Всяка слеваща се генерира от следните стъпки:

1. Взимаме индекса на предпоследния елемент: j = N - 1.

Ако a[j] >= a[j + 1] намаляваме j с 1 докато не се изпълни условието

a[j] < a[j + 1]. Ако j < 0 значи няма повече пермутации и прекратяваме изброяването. В този момент j е най-малкия индекс, за който сме посетили всички пермутации, започващи с a[0]...a[j].

2. Взимаме индекса на последния елементо, m = N.

Ако a[j] >= a[m] намаляваме m с 1, докато не се изпълни условието a[j] < a[m]. Разменяме a[j] <-> a[m]. Преди размяната a[j + 1] >= ... >= a[N] следователно a[m] е най-малкият елемент по-голям от a[j] и след като ги разменим се формира следващата лексикографска поредица.

3. Взимаме k = j + 1 и p = N. Докато е изпълнено условието k < p разменяме a[k] <-> a[p] и увеличаваме к с 1, а p намаляваме с 1. Тук идеята е да държим всички елементи след j сортирани възходящо.

 Надявам се, че все нещо се разбира smiley


от kzhokham (102 точки)


3

Не съм гледал авторското решение, но задачата е същата като Featuring with Grisko. Moже да го погледнеш, оставил съм доста коментари. Ето и конкретно на They Are Green, но там няма коментари. Задачите са идентични. Опитай да разбереш с кода и коментарите, ако не стане мога да обясня по-подробно. Най-общо казано, съм ползвал рекурсия за да генерирам всички пермутации на входните символи, като след това проверявам дали са генерираното е валидна дума. Оптимизацията която съм описал е, че при случаите в които имаме само уникални букви решението е n! където n e броя на използваните букви. Аз съм ползвал рекурсия за да генерирам пермутациите.


от dimo.petrof (2887 точки)


0
Като допълнителна оптимизация, може да се пропусне изчисляването на Комбинации и Факториел, тъй като сме ограничени до 10. Стойностите на броя комбинации и факториел от n може да бъдат съхранени в масив. Което опростява задачата значително.
Разбира се, ако един ден програмата трябва да работи и за n = 100, то може да се направи проверка само когато n > 10 (или колкото стойности предварително имаме в масива), само тогава да изчислява.

от martin.nikolov (4535 точки)

0
Аз скоро се сетих и за още една оптимизация, но ме мързи да я правя. Да се промени малко генерацията на пермутации така, че да генерира само валидни думи и да няма нужда от проверката, както и да бъдат писани в масив. Така няма и да се генерират излишни пермутации.

от dimo.petrof (2887 точки)



1
Тая задача се е утепала за рекурсия. Само дано влезе в тайм лимита без оптимизация.
Или с list

от JulianG (5316 точки)


0
Дам, тя си е направо по рекурсивния алгоритъм с n вложени цикли за генериране на пермутации, сиреч – решилите с разбиране комбинаторните задачи със звездички, би трябвало да могат да я решат, като модифицират алгоритъма да пермутира съответните символи. На изпита бях я докарал по този начин до 40-50 точки и имах някои неща за доизкусуряване. Юлияне, тази е от нашия изпит, вечерта, впрочем.

от varbanoff (2325 точки)

0
Ако се генерират само премутации, които отговарят на условието, задачата влиза в time limit-а и дава 100/100 и с рекурсия.

от anilak (1134 точки)



0

Колеги, имам нужда от помощ с това решение http://pastebin.com/6m21FX0j . Гърми на време, а нямам и грам предтава как да го потимизирам. В решението съм ползвала кода на задача 19 от домашното по едномерни масиви.


от geniusvil (192 точки)


1

То пак като ти дава 72/100 пак е добре.

Погледни си решението, използваш ненужно много ресурси.

Памет: 107.21 MB 
Време: 0.548 s

Примерно при всяка генерирана пермутация инициализираш нов StringBuilder (това при дума с 10 символа са 3628800). Това дали е бързо?

Хеш-а е напълно излишен. Вместо да ги записваш някъде и после да проверих колко си записал (result.count), не може ли просто да си ги броиш в една променлива (примерно long). StringBuilder-а също е абсолютно излишен. Дали не може да се провери в самия char[] дали съседните букви са еднакви ?


от dimo.petrof (2887 точки)


0
Използвам HashSet защото запазва уникалните комбинации, т.е тези които не се повтарят, защото при еднакви букви на вход такива със сигурност ще има. А преди да ги сложа там проверявам дали отговарят на условието за не две еднакви съседни букви. Но ще пробвам дали проблема не е в StringBuilder. Благодаря

от geniusvil (192 точки)

0
Извинявай за HashSet-а, не бях запознат с него и се изказах прибързано и неподготвено. Разбира се, че проблема не е в него.

от dimo.petrof (2887 точки)