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))