Złożoność obliczeniowa - permutacje

0

Witam,
Mam pytanie: jaką złożoność obliczeniową ma algorytm wyszukujący wszystkie permutacje zbioru np. zbioru liczb? albo ogólnie jaką złożoność ma algorytm brute force?
Tutaj przykład takiego algorytmu:
http://code.google.com/p/google-collections/issues/attachmentText?id=71&aid=-7147814569069805842&name=Permutations.java&token=bb7229d89a54096faaa826671d5d56fc

Nie wiem za bardzo jak to ugryźć, jakby ktoś mógł pomóc to byłbym wdzięczny.

0

Może rozpisz algorytm w prostszej formie (np pseudo kodzie), aby dowiedzieć się o jaką permutacje chodzi trzeba analizować kiepsko napisany kod w Javie. Musisz ułatwić zadanie tym kto potencjalnie zechce ci pomóc.

0

Ok, ogólnie to nie musi być złożoność obliczeniowa tego kodu powyżej.
Chodzi mi o permutacje, gdzie mam daną tablice n-elementową i chce uzyskać jej
wszystkie permutacje (bez powtórzeń). Przy założeniu, że na wyjściu chce uzyskać
permutację, która będzie tablicą n-elementową. Na chłopski rozum wydaje mi się, że w przypadku
optymistycznym np. dla danych wejściowych [1, 1] złożoność obliczeniowa będzie wynosiła 1, a w przypadku pesymistycznym
np. dla danych wejściowych [1, 2, 3] ta złożoność będzie wynosić n! lub 2^n (tu mam dylemat, która odpowiedź jest właściwa).

0

Liczba permutacji ciągu n elementowego to n!, zatem ten algorytm ma złożoność n!

0

Chodzi mi o permutacje, gdzie mam daną tablice n-elementową i chce uzyskać jej
wszystkie permutacje (bez powtórzeń). Przy założeniu, że na wyjściu chce uzyskać
permutację, która będzie tablicą n-elementową.

Dla danych [1,1] złożoność obliczeniowa wynosi 0 ponieważ nie istnieje żadna permutacja dwuelementowa bez powtórzeń.
dla danych [1,2,3] złożoność obliczeniowa wynosi n! jak napisał autor postu wyżej.

0

Ja bym chętnie zobaczył dowód. Wypisanie tych permutacji wymaga n! operacji, więc złożoność jest >=n!, ale wpierw te permutacje trzeba jakoś utworzyć.

0

Nie wiem jak ten algorytm tu wklejony ale np. ten:

def permutations[T](set: Set[T]): Iterable[List[T]] = {
  if (set.isEmpty) 
     List(Nil)
  else 
     for (elem <- set; rest <- permutations(set - elem)) yield elem :: rest
}

ma złożoność n! i do tego jest zawstydzająco krótki w porównaniu z tym koszmarkiem Javowym wklejonym przez autora. :D

0

Próbowałem obejrzeć ten chwalony kod, FF odpowiedział błędem 500, Opera pokazała kod. Nie chciało mi się go analizować, ale podany na początku przykład wskazuje,że mimo nazwy permutacja kod nie całkiem generuje permutacje, on generuje wszystkie k-elementowe, różnowartościowe podciągi ciągu n-elementowego. Liczebność tego tworu wynosi C(n,k)*k!=n!/(n-k)!, C(n,k) to symbol Newtona. Jeżeli k=n, to dostajemy permutacje zbioru n-elementowego.

0
bo napisał(a)

Ja bym chętnie zobaczył dowód. Wypisanie tych permutacji wymaga n! operacji, więc złożoność jest >=n!, ale wpierw te permutacje trzeba jakoś utworzyć.

Zazwyczaj w analizie algorytmu nie liczymy operacji wejścia-wyjścia.

0

@JumpSmerf ech ale żeby móc wypisać te wszystkie permutacje to musisz je też mieć wcześniej "policzone", to znaczy że i tak złożoność musi być przynajmniej n! bo jakoś te permutacje wyznaczyliśmy. Nawet jeśli pominiemy sam fakt ich późniejszego wypisania na wyjście.

0

Złożoność dla zwracania wszystkich permutacji jest co najmniej n!, ale można nieco to obejść dostarczając leniwą implementację - tzn. taką, która zwraca iterator po wszystkich permutacjach. Samo zwrócenie iteratora da się wtedy zrobić w czasie stałym, a ostateczna złożoność będzie zależeć od tego ile permutacji użytkownik zechce przeczytać. Wliczenie wypisywania permutacji zwiększa złożoność z O(n!) do O(n * n!).

0

Ok, dzięki wielkie za odpowiedzi. Wyjaśniło mi to dość sporo.
Teraz pytanie mam jak obliczyć złożoność pamięciową takiego problemu?

0

Nie ma czegoś takiego jak złożoność pamięciowa/obliczeniowa problemu. Jest tylko złożoność algorytmu który ten problem rozwiązuje.
Jak sobie napiszesz tak ze przechowujesz te wszystkie permutacje to będzie n! a jak napiszesz tak ze po obliczeniu permutacji przerabiasz ją na następną niejako "w miejscu" to możesz mieć O(n) na przykład (zakładając że 'n' to ilość elementów zbioru)

0

Aha, tzn, że dajmy na to jak przechowuje wszystkie permutacje w pamięci to złożoność pamięciowa algorytmu będzie wynosić O(n!), a jeśli po każdej generacji i np. wypisaniu permutacji na konsole, wyczyszcze pamięć zajmowaną przez tablice zawierającą permutacje to złożoność pamięciowa będzie wynosić O(n)?

0

To jest pytanie o to czy dobrze zrozumiałem:) więc mam nadzieje, że niczym.

0
_13th_Dragon napisał(a)

Chodzi mi o permutacje, gdzie mam daną tablice n-elementową i chce uzyskać jej
wszystkie permutacje (bez powtórzeń). Przy założeniu, że na wyjściu chce uzyskać
permutację, która będzie tablicą n-elementową.

Dla danych [1,1] złożoność obliczeniowa wynosi 0 ponieważ nie istnieje żadna permutacja dwuelementowa bez powtórzeń.
dla danych [1,2,3] złożoność obliczeniowa wynosi n! jak napisał autor postu wyżej.

Myślę, że tu kolega się myli, gdyż dla danych wejściowych na wyjściu będziemy mieli jedyną permutacje [1, 1] -> jedyną możliwą, czyli złożoność będzie równa 1.
BTW. jak oszacować teoretyczną oczekiwaną złożoność obliczeniową dla takiego algorytmu?

0

Jeżeli elementy w tablicy wejściowej się mogą powtarzać (czyli mamy wielozbiór) i chodzi Ci o znalezienie liczby wszystkich unikalnych (tj. różnych od siebie) sekwencji jakie można uzyskać permutując (przestawiając) elementy tego wielozbioru to sprawa się nieco komplikuje.

Przykład:
W = (1, 1): liczba permutacji = 1: (1, 1) // tu Trippy masz racje, a _13th_Dragon nie ma racji twierdząc, że jest 0
W = (1, 2): liczba permutacji = 2: (1, 2) i (2, 1)
W = (1, 1, 2): liczba permutacji = 3: (1, 1, 2), (1, 2, 1), (2, 1, 1)

Wzór się komplikuje ponieważ w wyniku powtórzeń elementów, jak by potraktować to klasycznym sposobem generowania n! permutacji, niektóre permutacje się powtórzą. Żeby obliczyć liczbę unikalnych permutacji (tj. bez powtórzeń permutacji), dzielisz wielozbiór wejściowy na grupy takich samych elementów i zapisujesz liczność elementów w każdej grupie. Np. dla W = (1, 1, 2) będziesz mieć 2 grupy - grupę jedynek o liczności 2 i grupę dwójek o liczności 1. Powiedzmy, że liczności elementów w grupach masz w zbiorze G = { g1, g2, ... gk }, gdzie k to liczba grup, k <= n (n - liczba elementów w wielozbiorze wejściowym), g1 + g2 +... + gk = n.

Wtedy liczba permutacji wynosi:

         n! 

g1! * g2! * ... * gk!

Zmodyfikowany algorytm, który uwzględnia powtórzenia, nieco nieoptymalny, bo na listach a nie tablicach mieszających, ale łatwo przerobić:

def permutations[T](multiset: List[T]): Iterable[List[T]] = {
  if (multiset.isEmpty) 
     List(Nil)
  else 
     for (elem <- multiset.distinct; 
          rest <- permutations(multiset.diff(List(elem)))) yield elem :: rest
}

Przykład działania:

scala> permutations(List(1,2,3))
res0: Iterable[List[Int]] = List(List(1, 2, 3), List(1, 3, 2), List(2, 1, 3), List(2, 3, 1), List(3, 1, 2), List(3, 2, 1))

scala> permutations(List(1,1,2))
res1: Iterable[List[Int]] = List(List(1, 1, 2), List(1, 2, 1), List(2, 1, 1))

1 użytkowników online, w tym zalogowanych: 0, gości: 1