Liste de combinaison de p parmi n éléments

Version imprimable

Je me suis inspiré de ceci http://www.developpez.net/forums/d42...s/#post5735783 pour la version php :

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
<?php
	// construction recursive des listes possibles
	function partition($index, $p, $n, $ordered, $liste) {
		if ($index>=$p) {// la liste est construite -> FIN
			for ($i=0;$i<count($liste);$i++) {
				$res = $liste[$i];
				echo " - ".$res;
			}
			echo"<br>";
		}
		// ajoute un nouvel element candidat dans la liste
		// - sans ordre -> candidat: tous les elements
		// - avec ordre -> candidat: seulement les elements supérieurs au précédent
		$start=1;
		if ($ordered && $index>0) {
			$start = $liste[$index-1]+1;
		}
		for($i=$start;$i<=$n;$i++) {
			$liste[$index] = $i;
			partition($index+1, $p, $n, $ordered, $liste);
		}
	}
	partition(0, 7, 16, true, array());
?>

On obtient toutes les combinaisons de 7 éléments parmi 16.

26/01/2011, 11h08
Benjamin Delespierre
Hello

On pourrait changer ça:
Code:

1 2 3 4 5 6 7 // la liste est construite -> FIN for ($i=0;$i<count($liste);$i++) { $res = $liste[$i]; echo " - ".$res; } echo"<br>";
en
Code:

1 2 echo implode(' - ', $liste) . '<br />';
et puis peut être changer sa signature:

Code:

function partition($index, $p, $n, $ordered = true, $liste = array())

Mais bon, c'est cosmétique :)

C'est effectivement plus propre.

Un autre code, mais cette fois, ce n'est pas parmi la suite continue des n premiers nombres, mais parmi n éléments qui n'ont aucun lien entre eux :

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
 
$liste2 = array("banane",5,"escalier",9,11);
 
function partition2($index, $p, $n, $ordered, $liste) {
	global $liste2;
	if ($index>=$p) {// la liste est construite -> FIN
		echo implode(" - ", $liste)."<br/>";
		return;
	}
	// ajoute un nouvel element candidat dans la liste
	// - sans ordre -> candidat: tous les elements
	// - avec ordre -> candidat: seulement les elements supérieurs au précédent
	$start=0;
	if ($ordered && $index>0) {
		$start = array_search($liste[$index-1], $liste2) + 1;
	}
	for($i=$start;$i<$n;$i++) {
		$liste[$index] = $liste2[$i];
		partition2($index+1, $p, $n, $ordered, $liste);
	}
}
partition2(0, 4, count($liste2), $ordered = true, $liste = array());

Et on obtient :

Code:

1
2
3
4
5
banane - 5 - escalier - 9
banane - 5 - escalier - 11
banane - 5 - 9 - 11
banane - escalier - 9 - 11
5 - escalier - 9 - 11