Ich habe eine c++ vector
mit std::pair<unsigned long, unsigned long>
Gegenständen. Ich versuche, Permutationen der Objekte des Vektors mit zu erzeugen std::next_permutation()
. Ich möchte jedoch, dass die Permutationen eine bestimmte Größe haben, ähnlich der permutations
Funktion in Python, bei der die Größe der erwarteten zurückgegebenen Permutation angegeben wird.
Grundsätzlich c++
entspricht das Äquivalent von
import itertools
list = [1,2,3,4,5,6,7]
for permutation in itertools.permutations(list, 3):
print(permutation)
(1, 2, 3)
(1, 2, 4)
(1, 2, 5)
(1, 2, 6)
(1, 2, 7)
(1, 3, 2)
(1, 3, 4)
..
(7, 5, 4)
(7, 5, 6)
(7, 6, 1)
(7, 6, 2)
(7, 6, 3)
(7, 6, 4)
(7, 6, 5)
python
c++
permutation
d4rk4ng31
quelle
quelle
(1, 1)
? Python-Permutationen bieten Duplikate[(1, 1), (1, 1)]
, währendstd::next_permutation
Duplikate (nur{1, 1}
) vermieden werden .Antworten:
Sie können 2 Schleifen verwenden:
Demo
quelle
std::next_permutation
ist "unklar", da es sich um Swap (linear) handelt. Die Extraktion des Subvektors kann verbessert werden, aber ich denke nicht, dass dies die Komplexität ändert. Außerdem hängt die Anzahl der Permutationen von der Vektorgröße ab, sodass die Parameter 2 nicht unabhängig sind.std::vector<T>& v
?v
derzeit). Ich könnte an einer const-Referenz vorbeikommen und stattdessen eine sortierte Kopie im Text erstellen.Wenn Effizienz nicht das Hauptanliegen ist, können wir alle Permutationen durchlaufen und diejenigen überspringen, die sich in einem Suffix unterscheiden, indem wir nur jedes
(N - k)!
-te auswählen . Zum BeispielN = 4, k = 2
haben wir Permutationen:wo ich ein Leerzeichen für Klarheit eingefügt und jede
(N-k)! = 2! = 2
-nd Permutation mit markiert habe<
.Ausgabe:
quelle
Hier ist ein effizienter Algorithmus, der nicht
std::next_permutation
direkt verwendet wird, sondern die Arbeitspferde dieser Funktion verwendet. Das heißtstd::swap
undstd::reverse
. Als Plus ist es in lexikographischer Reihenfolge .Und wenn wir es nennen, haben wir:
Hier ist die Ausgabe:
Hier ist ausführbarer Code von ideone
quelle
bool nextPartialPermutation(It begin, It mid, It end)
Wenn Sie die Antwort von Joseph Wood mit der Iterator-Oberfläche drehen, haben Sie möglicherweise eine ähnliche Methode wie
std::next_permutation
:Demo
quelle
Dies ist meine Lösung nach einigem Nachdenken
Bitte kommentieren Sie Ihre Gedanken
quelle
permute
könnte in der Tat nurset.insert(vec);
einen großen Faktor entfernen.O(nb_total_perm * log(nb_res))
(nb_total_perm
was meistensfactorial(job_list.size())
undnb_res
Größe des Ergebnisses ist :)permutations.size()
, also immer noch zu groß. (aber jetzt behandeln Sie doppelte Eingaben im Gegensatz zu Evg)