Appel aux informaticiens de passage.
Je recherche un script PHP qui permette de permutter les elements d'un tableau et de creer un autre tableau pour chaque permutation possible. Un petit exemple valant mieux qu'un long discours, je vous montre.
J'ai un tableau (ou une chaine de caracteres, je suis pas sectaire) qui contient ceci: |S|A|T|
Je voudrais un script qui me sorte les tableaux suivants :
- |S|A|T|
- |S|T|A|
- |T|A|S|
- |T|S|A|
- |A|S|T|
- |A|T|S|
Si mes notions de logique ne m'ont pas toutes quitté, le nombre de tableaux resultants doit etre egal à factorielle n, où n est le nombre d'elements du tableau. (Je sens que je suis en train de me lancer dans une usine à gaz, moi...)
18 réactions
1 De Fitz - 30/01/2008, 10:08
Je suis pas informaticien, je n'ai pas ça en php, désolé.
La vrai possible difficulté arrive si tu as redondances d'éléments dans ton tableau initial. Sinon tu as bien n! vecteurs et l'algorithme de remplissage du tableau résultant n x !n est simple (i.e. celui que tu as utilisé pour faire ton tableau manuellement). Par contre, par définition, puisque tu veux un comptage exhaustif tu ne peux pas couper à une complexité en n!, donc gare si n! n'est pas petit...
2 De balmeyer - 30/01/2008, 10:36
A court de temps aujourd'hui, mais si tu n'as pas de solution d'ici quelques heures, je me ferai un plaisir de t'aider (je n'utilise pas beauceaup le php, voilà pourquoi je ne peux répondre sur le champs). @+
3 De Spica - 30/01/2008, 10:43
Mais dans quoi tu te lances toi ? T'es en train de craquer des mots de passes ou de calculer les prochains numéros du loto ?
4 De Ziggy - 30/01/2008, 10:51
Tu dois construire une fontion récurrente qui s'appelle elle-même.
Cette fonction F retourne une matrice de n colonnes et n! lignes (chaque ligne représente l'un des tableaux que tu cherches).
Soient x1,..., xn les éléments.
Le cas n=1 est trivial et la fonction doit le distinguer.
Pour n > 1, F(x1,..., xn) est obtenue par la concaténation de n tableaux T(i) de (n-1)! lignes et n colonnes, où la première colonne de T(i) est xi répété (n-1) fois, et les colonnes suivantes sont données par F(x1,...,xk,...xn ; k≠i) qui a bien la dimension (n-1) colonnes et (n-1)! lignes.
L'algo s'auto-appelle automatiquement autant de fois qu'il faut pour remplir toute la matrice.
CQFD (enfin je crois, moi pas informaticien).
5 De Ziggy - 30/01/2008, 11:03
Bien lire à la 12ème ligne "xi répété (n-1)! fois" et non "(n-1) fois".
J'ajoute que la concaténation doit être verticale.
6 De TarValanion - 30/01/2008, 11:23
Fitz : Les elements redondants ne me genent pas. Je comparerai tous les tableaux à la fin pour supprimer les doublons.
Balmeyer : ok, merci! Je suis pas pressé, de toutes façons.
Spica : Pas du tout, c'est jsute pour le fun.
Ziggy : je vais regarder ça pendant ma pause.
7 De kheyliana - 30/01/2008, 11:25
sans ça, tu contactes mon homme, il pourrait peut être t'aider
8 De bmayer - 30/01/2008, 14:38
Peux tu preciser ton besoin, stp ?
9 De Wizmaster - 30/01/2008, 15:20
Toi, je sais ce que tu veux en faire ! Tricheur ! C'est de tête qu'il faut chercher ça ! :Þ
10 De TarValanion - 30/01/2008, 16:16
Kheyli : On verra, si je trouves pas ailleurs.
Bmayer : Ben, il me faut un script qui fasse toutes les permutations possibles d'une chaine ou d'un tableau. Comme dans l'exemple ci-dessus.
Wizmaster : T'es là, toi? Je croyais que tu boudais.
11 De Flo - 30/01/2008, 19:21
http://www.phpcs.com/codes/TROUVER-...
12 De TarValanion - 31/01/2008, 07:42
Flo : Merci, ca me fait bien avancer. Je l'avais vu, mais sans pouvoir le tester. Et comme les commentaires en dessous semblaient dire que ca valait pas grand chose, j'avais laissé tomber.
13 De Ziggy - 31/01/2008, 10:08
T'avais eu raison Tarval : l'algo proposé est faux, ou du moins pas exhaustif. Regarde le commentaire de l'administrateur qui dit qu'il faut un programme récursif (ce que je te suggérais)...
14 De TarValanion - 31/01/2008, 11:19
Effectivement, ca marche pas, il en manque... Grrrrr!
15 De ZeuBeuBeu - 31/01/2008, 11:59
Bon j'ai trouvé une fonction qui marche sur le net, par contre elle est super cracra et pas bien documentée donc rapido en deux minutes j'ai rajouté comment on s'en sert :
<?php
//D'après cette page :
// http://forum.hardware.fr/hfr/Progra...
// Fonction cracra avec ajout d'un pipe séparateur
function combi2($niveau=0,$s="",&$myuse)
{
global $array_ask,$array_ret,$myproductid;
if($niveau<count($array_ask))
{
for($x=0;$x<count($array_ask);$x++)
{
if(!(in_array($x,$myuse)))
{
$myuse$niveau=$x;
combi2($niveau+1,$s.$array_ask$x."|",$myuse);
}
}
$myuse$niveau=-1;
}
else
{
$array_ret = substr($s,0,-1);
$s="";
unset($myuse);
}
}
// Arobase pour s'éviter les ouareunaingues
$array_ask = array('A','A','C');
$array_ret = array();
@combi2();
echo '<h2>Tableau de test</h2><pre>'; print_r($array_ask); echo '</pre>';
// Version intégrale
$plop = array_map(create_function('$e','return explode(\'|\',$e);'),$array_ret);
echo '<h2>Combinaisons intégrales</h2><pre>'; print_r($plop); echo '</pre>';
// Version sans doublon
$drudru = array_values(array_unique($array_ret));
$drudru = array_map(create_function('$e','return explode(\'|\',$e);'),$drudru);
echo '<h2>Combinaisons sans doublon</h2><pre>'; print_r($drudru); echo '</pre>';
?>
16 De ZeuBeuBeu - 31/01/2008, 12:01
Le méchant Dotclear a mangé mes crochets
Je t'envoie le fichier par mail du coup.
17 De balmeyer - 31/01/2008, 16:55
Désolé ! pas eu le temps ! Je reviendrais voir si c'est toujours d'actualité.
18 De tableau - 06/05/2008, 11:36
Merci je recherchais justement un bout de code comme ca !
Sympa