schon spät heute, hab's zur Übung nur schnell ins Python gehackt.
Umsetzung in C++ mit stdlib wäre dann analog. Vielleicht würde man sich
noch mehr Gedanken drüber machen, welche arrays wirklich wie oft erzeugt
werden müssen.
1 | def _generate_permutations(m, n):
|
2 | substrings = _generate_permutations(m, n-1) if n > 2 else m
|
3 |
|
4 | results = set() # hash-based set of strings
|
5 | for remainder in substrings:
|
6 | for letter in m:
|
7 | candidate = remainder + letter # new string
|
8 | candidate_sorted = "".join(sorted(remainder + letter)) # sort new string
|
9 | results.add(candidate_sorted)
|
10 | return results
|
11 |
|
12 | for perm in sorted(_generate_permutations(m="abc", n=2)):
|
13 | print(perm)
|
output:
Wenn man genug Speicher hat für den m^n Lösungsraum ist es sicherlich
effizienter, einfach erst alle m^n Lösungen mit BFS aufzulisten und dann
am Ende einen Durchlauf zu machen, bei dem alles reihenfolgeninvariant
gehasht wird. Das wäre dann O(m^n)
So ist aber die Komplexität O(m^n n log(n))
Dafür könnte man viel Herzblut die Sortierung aber vielleicht
inkrementell mit insert-sort beschleunigen, da ja immer nur ein Element
eingefügt wird.