Générer un ensemble de n-uplets Python

[ThomasPayet97436]

Bonjour, bonsoir,
Je me lance dans l'écriture d'un programme python au cours duquel je dois créer une liste dont les éléments sont tous les n-uplets d'entiers naturels compris entre 1 et m, avec n et m fixées.
Pour le cas n=2, je pense qu'une double boucle for ferait l'affaire mais comment généraliser aux autres cas ?
Merci d'avance pour votre aide
-----

[pm42]

Récursivement, c'est assez facile. Tu reçois une liste de taille n, tu la parcours et pour chaque élément, tu le retires et tu demandes la listes de n-uplets de taille n-1 de ceux qui restent.
Pour chacun d'entre eux, tu ajoutes l'élément retiré avant : tu as la liste de tous les n-uplets de taille n.

Et pour n=1, le code est trivial.

[ThomasPayet97436]

Je n'avais pas pensé à de la récursivité, génial merci j'essaie ça de suite!

[ThomasPayet97436]

Alors, je ne suis pas sûr d'avoir compris. J'aurais besoin de plus de détails s'il te plaît. Quelle liste "reçoit"-on? Pourrais-tu détailler la récursivité? Que veut-tu dire par "demander" la listes des (n-1)-uplets?

[A voir en vidéo sur Futura]

[vgondr98]

Bonjour, j'ai essayé en java.

@Test
	public void uplet(){
		List<List<Integer>> uplets = new ArrayList<List<Integer>>();
		List<List<Integer>> upletsfinal = new ArrayList<List<Integer>>();
		List<Integer> uplet;
		List<Integer> upletint;
		Scanner keby 	= new Scanner(System.in);
		System.out.println("Veuillez saisir n puis appuyer sur espace et saisiser m puis entré");
		Integer n		= keby.nextInt();
		Integer m		= keby.nextInt();
		
		keby.close();
		
		System.out.println(n);
		System.out.println(m);
		
		for (int i = 1; i <= n; i++) {
			
			//pour la 1ere iteration, on créé m arraylistes
			if (uplets.size() == 0) {
				for (int j = 1; j <= m; j++) {
					uplet = new ArrayList<Integer>();
					uplet.add(j);
					uplets.add(uplet);
				
				}
			} else {
				int taille = uplets.size();
				for (int k = 0; k < taille; k++) {

					for (int j = 1; j <= m; j++) {
						uplet = uplets.get(k);
						upletint = new ArrayList<Integer>(uplet);
						if (!upletint.contains(j)) {
							upletint.add(j);
						}
						
						uplets.add(upletint);
					
					}
					//uplets.remove(k);
					//k = k - 1;
				}
			}

		}
		for (int i = 0; i < uplets.size(); i++) {
			if (uplets.get(i).size() == n) {
				upletsfinal.add(uplets.get(i));
			}
		}
		System.out.println(upletsfinal);
		System.out.println(upletsfinal.size());
	}

Pour n = 3 et m = 4, j'obtiens 24 sous-listes ce qui est attendu si on considère qu'un n-uplets avec 3 éléments est du style [1,2,3] avec aucun chiffre en double. Si les doublons sont autorisés, il faut modifier cette ligne if (!upletint.contains(j)) {

[ThomasPayet97436]

Merci pour ta réponse, je regarde ça. Je dois prendre en compte tous les n-uplets donc ceux comme [1,1,2] ou [1,1,1] sont comptés, soit 64 n-uplets au total pour n=3 et m=4

[vgondr98]

64, c'est le nombre que j'obtiens si on peut mettre les doublons.
L'algo que j'utilise, c'est de faire n boucles.
Dans la première boucle, je créé m listes contenant 1 valeur.
Ensuite, je parcours toutes les listes créées avant et je créé m liste par listes.
[[1],[2],[3],[4]] tour 1
[[1],[2],[3],[4], [1,1],[1,2],[1,3],[1,4]...] tour 2
Cela a a l'air de fonctionner.
Il y a un petit défaut, c'est que je ne supprime pas les petites listes. Je pense qu'en le faisant, cela ferait gagner du temps.