[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}




Отговори



14

http://pastebin.com/hhpGQLnr

Малко разяснения:

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

Ако имаме само числата 1 и 2, ще имаме просто смяната на местата им: 1,2 и 2,1.

Приемаме, че пермутацията на числата от 1 до N е всеки елемент + пермутацията на останалите числа. Пример:

Пермутацията на 1, 2, 3, 4 е:

1 + пермутацията на 2, 3 и 4.

2 + пермутацията на 1, 3 и 4.

3 + пермутацията на 1, 2 и 4.

4 + пермутацията на 1, 2 и 3.

Създаваме си масив от числа, които искаме да пермутираме, в нашия случай от 1 до N.

Рекурсията ще действа така:

1. Проверяваме дали текущия елемент не е стигнал края на масива. Ако това условие е изпълнено, това е края на рекурсията и принтираме масива (текущата пермутация).

2. Ако не е изпълнено, за всички елементи от текущия елемент до края на масива сменяме местата с всеки поотделно (чрез отделен метод, който по референция сменя две променливи в масив).

3. Извикваме рекурсивно метода за следващия елемент, тоест почваме от точка 1 отново.

4. За да продължим от там до където сме стигнали, преди рекурсивното извикване, е нужно отново да сменим местата на елементите (тоест да ги върнем обратно както си бяха).

След като сме имплементирали този метод, извикваме го с масива, нулевия елемент и индекса на последния елемент.

Е, като че ли работи нормално :D


от ivaylo.kenov (30760 точки)


0
Логиката ми е идентична, но решението ми се различава малко. При мен само един while цикъл обхожда оставащите елементи от масива. Борих се няколко часа с тази задача и съм доволен, че въобще стигнах до решение :) http://pastebin.com/T8fqTFwT

от FeRt1 (2866 точки)


8

Ето и моите решения: вариации, комбинации, пермутацииРазгледайте разликите. Решенията са с рекурсия.

Ако някой е забравил комбинаториката - bg.wikipedia.org/wiki/Комбинаторика.


от jasssonpet (6814 точки)


0
браво, отново много изчистени и хубави решения :)

от boncho.vylkov (1923 точки)


0

А вариант само с цикли няма ли?

Аз успях да го докарам до това: http://pastebin.com/NFjw2Vjy но не вади всички комбинаци...


от Mitko_Mitev (1276 точки)


0
Има няколко. Виж тук: http://anton5rov.wordpress.com/2013/01/20/permutations-with-iterative-algorithm/ Принципът е същият, както на Penka Borukova. Обясненията и реализацията се различават малко.

от AntonPetrov (654 точки)


0

Едно решение пак с рекурсия, но по Heap's algorithm.

http://pastebin.com/vmzhcWqA

 

Ако някой му се чете за различните алгоритми за генериране на пермутации, на мен ми беше доста полезно това: http://www.cs.princeton.edu/~rs/talks/perms.pdf


от sylviapsh (302 точки)


0

 

здравейте,
ето и моето решение http://pastebin.com/wv8zUa4h 
аз използвах метода Distinct(), за да направя проверката за уникални стойности



0

Едно решение без особени претенции.

http://pastebin.com/CXtQ6FHh


от vanina_nenova (327 точки)


1
Ето го и моето решение: http://pastebin.com/PCrMTPfY
Идеята:
1)Намира се индекс k: array[k] < array[k + 1]
2)Намира се индекс l: array[k] < array[l] (очевидно l >= k + 1)
3) Разменяме array[k] и array[l]
4) Reverse-ваме елементите от k + 1 до края на масива
И това се повтаря докато съществува такъв индекс k. Като резултат се получават лексикографски наредени пермутации. Ето допълнителна информация: http://en.wikipedia.org/wiki/Permutation#Generation_in_lexicographic_order

от PBorukova (1129 точки)


2
Това е почти директно от 19 глава в учебника (първия пример от "Генериране на подмножества" с HashSet):
http://pastebin.com/cStWyVqn

от neofitov (235 точки)


0

Използвам алгоритъма Generation in lexicographic order. Първо изчислявам пермутацията на числата посредством факториел в метод. След, което ги обхождам в друг метод със цикъл с дължината стойността получена от изчислението на факториела.

http://pastebin.com/EseSpMWw


от Gerya (1079 точки)


1

В досегашните решения на задачите 16,17,18 ставаше чрез генерирането на всички възможни комбинации от еденици и нули.

За генерирането на всички пермутации (в случая без повторение) има два подхода ако се тръгне от по-опростеното решение на 20та задача

- с булев масив който да индикира дали сме използвали числото (индекса)

- с допълнителна функция която да размества числата

На мен повече ми допада решението с булевия масив. Дадените решения са супер и не мисля да ги повтарям : )

А това е решение с разместваща функция на текст (взето някъде от нета)

http://pastebin.com/NeuSKd2R

Ако са ви интересни този род задачи бих ви препоръчал тази тема:

http://telerikacademy.com/Courses/Courses/Details/4


от stanev.plamen (1143 точки)