In dem in [diesem Artikel] erläuterten D-Problem von AtCoder073 (https://qiita.com/DaikiSuyama/items/ee09c6d3dea1f3f49246) wird das Problem der Erzeugung von n! (N <= 8) -Sequenzen und der Bearbeitung jeder dieser Sequenzen erläutert. hätten. Die Sequenzgenerierung erfolgt häufig mit AtCoder, aber es ist leicht zu vergessen, wie man sie schreibt. Deshalb fasse ich sie hier zusammen.
Verwenden Sie Permutationen im Modul itertools. Betrachten wir hier die Generierung aller Reihenfolgefolgen, in denen die Reihenfolge für das Array mit 0 bis 3 neu angeordnet wird.
>>> import itertools
>>> t=[i for i in range(4)]
>>> itertools.permutations(t)
<itertools.permutations object at 0x104dc0af0>
>>> list(itertools.permutations(t))
[(0, 1, 2, 3), (0, 1, 3, 2), (0, 2, 1, 3), (0, 2, 3, 1), (0, 3, 1, 2), (0, 3, 2, 1), (1, 0, 2, 3), (1, 0, 3, 2), (1, 2, 0, 3), (1, 2, 3, 0), (1, 3, 0, 2), (1, 3, 2, 0), (2, 0, 1, 3), (2, 0, 3, 1), (2, 1, 0, 3), (2, 1, 3, 0), (2, 3, 0, 1), (2, 3, 1, 0), (3, 0, 1, 2), (3, 0, 2, 1), (3, 1, 0, 2), (3, 1, 2, 0), (3, 2, 0, 1), (3, 2, 1, 0)]
>>> list(itertools.permutations(t,2))
[(3, 2), (3, 1), (3, 0), (2, 3), (2, 1), (2, 0), (1, 3), (1, 2), (1, 0), (0, 3), (0, 2), (0, 1)]
Wie oben erwähnt, können Sie sehen, dass die Reihenfolge des Arrays, das ein iterierbares Objekt ist (das erste Argument für Permutationen ist ein iterierbares Objekt), neu angeordnet wird und die gesamte im Taple gespeicherte ** Sequenz generiert wird. .. Sie können r auch im Ausdruck $ _n P _r $ im zweiten Argument der Permutationen angeben (standardmäßig r = n, wobei $ _n P _2 $ aus r = 2 erhalten wird).
Verwenden Sie next_permutation in der Algorithmusbibliothek. Betrachten wir noch einmal alle Sequenzen, in denen die Reihenfolge für das Array mit 0 bis 3 neu angeordnet wurde. In Python dachte ich daran, alle Sequenzen zu generieren, aber in C ++ verwende ich die Methode zum Generieren der nächsten Sequenz, indem ich die Funktion next_permutation mit der aufsteigenden sortierten als erste Sequenz anwende. Wenn dann die Reihenfolge, auf die die Funktion next_permutation angewendet wird, die letzte Reihenfolge ist (absteigend sortiert), kehrt sie zur ersten Reihenfolge zurück. Zu diesem Zeitpunkt wird außerdem false zurückgegeben, wenn die Sequenz, auf die die Funktion next_permutation angewendet wird, nicht die letzte Sequenz ist, und true wird zurückgegeben, wenn die Sequenz die letzte Sequenz ist. Daher können unter Verwendung der do-while-Anweisung unter Verwendung des Rückgabewerts alle Sequenzen verwendet werden. Du kannst etwas tun. Wenn Sie die do-while-Anweisung verwenden, können Sie nicht alle Sequenzen ausführen, es sei denn, Sie beginnen mit der ersten Sequenz. Wenn Sie jedoch im Voraus berechnen, wie viele Sequenzen vorhanden sind, können Sie die Funktion next_permutation so oft anwenden. Sie können mit allen Sequenzen etwas anfangen.
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
int main() {
int n=4;
vector<int> v(n);
//Funktion, die bequem in Schritten von 1 gespeichert werden kann
iota(v.begin(), v.end(), 0);
do{
//v ist in der folgenden Reihenfolge
for(int i=0;i<n;i++){
//Einige Operationen
}
}while(next_permutation(v.begin(),v.end()));
}
Abschließend möchte ich die wichtigen Punkte zur Auftragsgenerierung in Python und C ++ zusammenfassen.
① Für Python ** - Verwenden Sie die Permutationen des itertools-Moduls -Generieren Sie alle Straßen in Tapple (zerstörungsfrei) -Zugreifen Sie auf jede Sequenz mit einer for-Anweisung **
② Für C ++ ** - Verwenden Sie next_permutation aus der Algorithmusbibliothek ・ Ersetzen Sie durch die folgende Reihenfolge (destruktiv) -Zugriff mit der Anweisung do_while, wenn von einer aufsteigenden sortierten Reihenfolge ausgegangen wird Wenn Sie von anderen Sequenzen ausgehen, berechnen Sie die Anzahl der Sequenzen und greifen Sie für Minuten zu **
Recommended Posts