[C#] Arrays - 19 задача


0
19.* Write a program that reads a number N and generates and prints all the permutations of the numbers [1 … N]. Example:

  n = 3 -> {1, 2, 3}, {1, 3, 2}, {2, 1, 3}, {2, 3, 1}, {3, 1, 2}, {3, 2, 1}




Отговори



3

Моето решение е реализирано, чрез използване на материала взет до момента.

За целта използвам всички възможни вариации, обръщам ги от десетична в N-тична бройна система, като след това отделям тези с повтарящи се елементи.

Ето това е кода цък, в него има добавени коментари как работи.


от bankoff (3997 точки)


0
пич тва е супер идеино мислех и аз да го правя на броина система ама сега видях как си решил проблема по интересното е как си стигнал до идеята и/или от къде е този алгоритъм много е сериозен!

от ludmil.d (490 точки)


0

GitHub

Задачата е с рекурсия - използвам помощен bool масив (всяко число трябва да се използва само 1 път) и всеки път викам метода за следващото число от вектора който се търси (вектор наричам конкретната пермутация - то си е масив с n брой елементи). Ако се стигне до индекс = големината на вектора значи вектора е готов и се показва на конзолата.


от dzhenko (3893 точки)


2

Това определено беше задачата, над която мислих най-дълго време от всички домашни досега :) Най-вече, защото е първата, в която ползвам рекурсия без да гледам вече готов алгоритъм - http://git.io/VRvzmA Беше приятно обаче :)

Направих метод, на който подавам списък с числата от 1 до N. След това, числата се добавят с цикъл към един празен стринг, при условие, че не са вече добавени.
При прибавяне на число, рекурсивно се прибавят още, тъй като има проверка дали вече не са добавени.
При достигане на нужния брой числа в една пермутация, тя се принтира. Ако не са достигнати, но стрингът не е празен, се "изрязва" последният елемент от него преди да се завърти цикалът отново, понеже искаме да сложим нов на негово място.

Т. е. в началото имаме празен стринг, после имаме първото число, после рекурсивно второто и третото (ако са 3 общо). След това принтираме, режем последните два елемента и слагаме ново второ число и така докато не използваме всички. После режем всичките 3 елемента и слагаме ново първо число и т.н.

Не знам дали го обясних добре, но следейки кода и при наличие на желание, ще се разбере ;)

Приветствам подобрения по кода :) Май мога да изкарам списъка с елементите като "глобална променлива", не да го подавам всеки път, тъй като е един вид "read only", например. 


от georgiwe (720 точки)


0
Еми честита първа рекурсия :) Доста компактно решение се е получило.

от stoianpp (415 точки)

0
И аз много харесах решението. Като дебъгвам рекурсии, ги разбирам, но нещо не мога да ги мисля още.

от d.brezoev (212 точки)


0


И на мен това ми беше една от най-трудните задачи. Доста време рових из нета докато открия лесен и удобен за имплементация алгоритъм. В крайна сметка се спрях на алгоритъма на Johnson-Trotter. Идеята е числата да се сортират по големина. След това на всяко число се дава посока (в началото всичики "гледат" на ляво). След това най-голямото число, което може да се премести в посоката в която гледа се премества с една стъпка, ако не може то се премества следващото по големина и т.н. За да може да се премести числото трябва числото към което "гледа" да е по-малко от него. След като се премести едно число посоките на всички по-големи числа се обръщат и всичко почва от начало. Алгоритъма приключва когато нито едно число не може да се премести.

Решението не е с рекурсия и може да го видите тук


от wnvko (3123 точки)


2

Мисля, че се получи добро решение, след двучасово мислене. Наистина трудна задача за неопитни "рекурсисти" :) http://pastebin.com/S4HCR0aa

 

от stoianpp (415 точки)


0

Ето че и аз я преборих тази задача, след като изгледах лекцията за рекурсия. 
Първо инициализирам празен масив, в който да вкарвам числата от 1 до N.
В рекурсивния метод си правя дъно на рекурсията (която е когато се опитаме да сложим число на индекс извън масива).
Използвам структурата лист за да следя кои числа съм въвел в масива. Т.е. като вкарам число в масива, вкарвам го и в листа. Преди да вкарам числото в масива, проверям дали не участва и в листа. И извиквам рекурсивния метод, за следващия индекс. Важното е на връщане  от рекурсията да си премахвам числата от листа. http://pastebin.com/LZ8ZVHvh


от d.brezoev (212 точки)


0
Това с проверката дали числото е в листа ... не е добра идея. Ами ако имаш повтарящи се числа във входа?

от JulianG (5316 точки)

0
Прав си, пермутациите на {1,2,3} са различни от тези на {1,2,2,3}. Ще го помисля това допълнително. Но конкретно в задачата условието е такова че няма да има повтарящи се елементи за вход.

от d.brezoev (212 точки)



0
Гадна задача. За пръв път ми се налага да използвам рекурсия и се справям ужасно. Решението ми изобщо не работи.
ето какво написах - http://pastebin.com/mJMYQWdc
Трябва ми помощ. Някой може ли да ми обясни какво пропускам?

от lokiko91 (790 точки)