Comment générer une séquence en Python et C ++

Dans le problème D d'AtCoder073 expliqué dans cet article, le problème de génération de n! (N <= 8) séquences et d'opération sur chacune d'elles. eu. La génération de séquence se fait souvent avec AtCoder, mais il est facile d'oublier comment l'écrire, je vais donc la résumer ici.

[1] Pour Python

Utilisez les permutations dans le module itertools. Ici, considérons la génération de toutes les séquences d'ordre dans lesquelles l'ordre est réorganisé pour le tableau contenant 0 à 3.

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

Comme mentionné ci-dessus, vous pouvez voir que l'ordre du tableau qui est un objet itérable (le premier argument des permutations est un objet itérable) est réorganisé et la séquence ** entière stockée dans le taple est générée. .. Vous pouvez également spécifier r dans l'expression $ _n P _r $ dans le deuxième argument des permutations (r = n par défaut, où $ _n P _2 $ est obtenu à partir de r = 2).

[2] Pour C ++

Utilisez next_permutation dans la bibliothèque d'algorithmes. Encore une fois, considérons la génération de toutes les séquences dans lesquelles l'ordre est réorganisé pour le tableau contenant 0 à 3. En Python, je pensais générer toutes les séquences, mais en C ++, je prends la méthode de génération ** de la séquence suivante ** en appliquant la fonction next_permutation avec la fonction triée ascendante comme première séquence. Ensuite, si l'ordre auquel la fonction next_permutation est appliquée est le dernier ordre (trié par ordre décroissant), il revient au premier ordre. De plus, à ce stade, false est renvoyé si la séquence à laquelle la fonction next_permutation est appliquée n'est pas la dernière séquence et true est renvoyé si la séquence est la dernière séquence. Par conséquent, en utilisant l'instruction do-while utilisant la valeur de retour, toutes les séquences peuvent être utilisées. Vous pouvez faire quelque chose. De plus, lorsque vous utilisez l'instruction do-while, vous ne pouvez pas faire fonctionner toutes les séquences sauf si vous commencez par la première séquence, mais si vous calculez à l'avance le nombre de séquences, vous pouvez appliquer la fonction next_permutation pour ce nombre de fois. Vous pouvez faire quelque chose avec toutes les séquences.

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
int main() {
  int n=4;
  vector<int> v(n);
  //Fonction qui peut être stockée par incréments de 1, pratique
  iota(v.begin(), v.end(), 0);
  do{
    //v est dans l'ordre suivant
    for(int i=0;i<n;i++){
          //Une certaine opération
    }
  }while(next_permutation(v.begin(),v.end()));
}

[3] Résumé

Enfin, je voudrais résumer les points importants concernant la génération d'ordres dans chaque cas de Python et C ++.

① Pour Python ** - Utilisez les permutations du module itertools -Générer toutes les rues en tapple (non destructif) -Accédez à chaque séquence avec une instruction for **

② Pour C ++ ** - Utilisez next_permutation de la bibliothèque d'algorithmes ・ Remplacer par l'ordre suivant (destructif) -Accès avec l'instruction do_ while lors du démarrage d'un ordre trié croissant En partant d'autres séquences, calculez le nombre de séquences et accédez en quelques minutes **