Здравейте колеги!
Не мога да разбера алгоритъма, който е използван в авторското решение на тази задача. Няколко пъти дебъгвам вече, но не успявам да го схвана. Пермутации, сортирания и обръщания на масиви - пълна лудница.
Може ли някой да го формулира на човешки език!
Авторското решение използва следния алгоритъм за генериране на пермутации в лексикографски порядък.
(мой превод от книгата 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 сортирани възходящо.
Надявам се, че все нещо се разбира 
Не съм гледал авторското решение, но задачата е същата като Featuring with Grisko. Moже да го погледнеш, оставил съм доста коментари. Ето и конкретно на They Are Green, но там няма коментари. Задачите са идентични. Опитай да разбереш с кода и коментарите, ако не стане мога да обясня по-подробно. Най-общо казано, съм ползвал рекурсия за да генерирам всички пермутации на входните символи, като след това проверявам дали са генерираното е валидна дума. Оптимизацията която съм описал е, че при случаите в които имаме само уникални букви решението е n! където n e броя на използваните букви. Аз съм ползвал рекурсия за да генерирам пермутациите.
Колеги, имам нужда от помощ с това решение http://pastebin.com/6m21FX0j . Гърми на време, а нямам и грам предтава как да го потимизирам. В решението съм ползвала кода на задача 19 от домашното по едномерни масиви.
То пак като ти дава 72/100 пак е добре.
Погледни си решението, използваш ненужно много ресурси.
Памет: 107.21 MB
Време: 0.548 s
Примерно при всяка генерирана пермутация инициализираш нов StringBuilder (това при дума с 10 символа са 3628800). Това дали е бързо?
Хеш-а е напълно излишен. Вместо да ги записваш някъде и после да проверих колко си записал (result.count), не може ли просто да си ги броиш в една променлива (примерно long). StringBuilder-а също е абсолютно излишен. Дали не може да се провери в самия char[] дали съседните букви са еднакви ?
