Génération de permutations avec répétitions

Question

Je connais itertools, mais il semble qu'il ne puisse générer que des permutations sans répétitions.

Par exemple, j'aimerais générer tous les lancers de dés possibles pour 2 dés. J'ai donc besoin de toutes les permutations de taille 2 de [1, 2, 3, 4, 5, 6], y compris les répétitions : (1, 1), (1, 2), (2, 1)... etc.

Dans la mesure du possible, je ne veux pas mettre en œuvre ce système à partir de zéro.

Answer 1

Vous êtes à la recherche de la Produit cartésien .

En mathématiques, un produit cartésien (ou ensemble produit) est le produit direct de deux ensembles.

Dans votre cas, ce serait {1, 2, 3, 4, 5, 6} x {1, 2, 3, 4, 5, 6} . itertools peut vous y aider :

import itertools
x = [1, 2, 3, 4, 5, 6]
[p for p in itertools.product(x, repeat=2)]
[(1, 1), (1, 2), (1, 3), (1, 4), (1, 5), (1, 6), (2, 1), (2, 2), (2, 3), 
 (2, 4), (2, 5), (2, 6), (3, 1), (3, 2), (3, 3), (3, 4), (3, 5), (3, 6), 
 (4, 1), (4, 2), (4, 3), (4, 4), (4, 5), (4, 6), (5, 1), (5, 2), (5, 3), 
 (5, 4), (5, 5), (5, 6), (6, 1), (6, 2), (6, 3), (6, 4), (6, 5), (6, 6)]

Pour obtenir un lancer de dés aléatoire (dans un de manière totalement inefficace ):

import random
random.choice([p for p in itertools.product(x, repeat=2)])
(6, 3)

Answer 2

Vous ne cherchez pas de permutations - vous voulez le Produit cartésien . Pour cette utilisation produit de itertools :

from itertools import product
for roll in product([1, 2, 3, 4, 5, 6], repeat = 2):
    print(roll)

Answer 3

Dans python 2.7 et 3.1, il existe une fonction itertools.combinations_with_replacement fonction :

>>> list(itertools.combinations_with_replacement([1, 2, 3, 4, 5, 6], 2))
[(1, 1), (1, 2), (1, 3), (1, 4), (1, 5), (1, 6), (2, 2), (2, 3), (2, 4), 
 (2, 5), (2, 6), (3, 3), (3, 4), (3, 5), (3, 6), (4, 4), (4, 5), (4, 6),
 (5, 5), (5, 6), (6, 6)]

Answer 4

Dans ce cas, une compréhension de la liste n'est pas particulièrement nécessaire.

Étant donné que

import itertools as it

seq = range(1, 7)
r = 2

Code

list(it.product(seq, repeat=r))

---

Détails

De manière non évidente, le produit cartésien peut générer des sous-ensembles de permutations. Cependant, il s'ensuit que :

• avec remplacement : produire toutes les permutations n r via product
• sans remplacement : filtre de ce dernier

Permutations avec remplacement, n r

[x for x in it.product(seq, repeat=r)]

Permutations sans remplacement, n !

[x for x in it.product(seq, repeat=r) if len(set(x)) == r]

# Equivalent
list(it.permutations(seq, r))  

Par conséquent, toutes les fonctions combinatoires peuvent être implémentées à partir de product :

• combinations_with_replacement mis en œuvre à partir de product
• combinations mis en œuvre à partir de permutations qui peut être mis en œuvre avec product (voir ci-dessus)

Answer 5

Voici la version c# (même si elle est demandée pour python, l'algorithme devrait être le même) juste pour référence :

La méthode ci-dessous prend en compte le nombre de fois que le dé peut être lancé pour obtenir différentes permutations. Pour la question ci-dessus, la taille devrait être '2'.

private void GetAllPermutationsOfDice_Recursive(int size, string currentValue, 
            List<string> values)
        {
            if(currentValue.Length == size)
            {
                values.Add(currentValue);
                return;
            }
            for(int i = 1; i<=6;i++)
            {
                this.GetAllPermutationsOfDice_Recursive(size, currentValue + i, values);   
            }
        }

Pour lancer les dés deux fois, la méthode ci-dessus peut être appelée comme suit :

public string[] GetAllPermutationsOfDiceOfSize_2()
        {
            List<string> values = new List<string>();
            this.GetAllPermutationsOfDice_Recursive(2, "", values);
            return values.ToArray();
        }

Voici les tests unitaires correspondants :

[TestMethod]
        public void Dice_PermutationsTests()
        {
            var v = this.GetAllPermutationsOfDiceOfSize_2();
            Assert.AreEqual(36, v.Length);
            int l = 6;
            List<string> values = new List<string>();
            for(int i = 1; i<=4; i++)
            {
                values.Clear();
                this.GetAllPermutationsOfDice_Recursive(i, "", values);
                Assert.AreEqual(l, values.Count);
                l *= 6;
            }
        }