Permutation en panne :-(

[inviteb4f1ec9f]

Bonjour tout le monde,


Je m’arrache les cheveux sur un problème qui me semble logique mais dont je n’arrive pas à trouver une solution.

Pardon de ma bêtise et peut-être de poster ce message dans le mauvais forum.

Je cherche à trouver toutes les solutions de permutations possibles d’une série.

Pour une série de 4 chiffres : 1234, il y a 5 séries possible : 1243 / 1423 / 1432 / 1342 / 1324

Mon raisonnement est déjà bancal pour une série de 5 (je crois) mais je suis tres loin du compte pour 6 ou plus. Le nombre de solution est donc factorielle n! (nb de combinaison pour 5 chiffres : 5 * 4 * 3 * 2 = 120) (Désolé je suis nul en math)

Voilà le début de code que j’ai écris (en PHP) mais après de longues réflexions sur le papier et de nombreuse recherche sur Internet je ne trouve pas,
1/ le raisonnement pour 6 chiffres ou plus
2/ le bout de code qui viendrait me faire comprendre l’algorithme pour afficher toutes les solutions de 1 à n chiffres (en langage non objet).

Je ne fais pas varier le chiffre 1, c'est voulu, je le garde en 1ère place.

<?php
$max = 6;
$c = "";
for ($i=1;$i<=$max;$i++)
{
$point[$i] = $i;
$c = $c.$point[$i];
}

$r=0; $d[$r] = 0;
while ($d[$r] != $c)
{
for ($w=1;$w<3;$w++)
{
for ($i=1;$i<$max-1;$i++)
{
$temp = $point[$max-$i];
$point[$max-$i] = $point[$max-$i+1];
$point[$max-$i+1] = $temp;

$r++; $d[$r] = "";
for ($j=1;$j<=$max;$j++)
{
$d[$r] = $d[$r].$point[$j];
}
echo "$r : "; echo $d[$r];
echo "<br>";
}
}
}
?>


Merci de votre aide.
-----

[invite97a92052]

Je ne fais pas varier le chiffre 1, c'est voulu, je le garde en 1ère place.

Dans ce cas, il n'y a plus n! possibilités.
Pour un nombre à n chiffres, il y a donc (n-1)! possibilités si je comprends bien ce que tu veux.

Mais pour 1234, je compte 6 possibilités :
1234
1243
1342
1324
1423
1432

Si tu me confirmes, je posterai l'algorithme itératif (non objet) que j'ai écrit en C, et qui réalise toutes les permutations possibles sur un nombre non fixé de chiffres/lettres. Tu devras juste adapter pour ne pas faire changer le 1 de place.

Mais je ne suis pas sur que ce soit ce que tu veux.

PS : oui, tu as du te tromper de forum !

[inviteb4f1ec9f]

Oui en effet il y a 24 solutions pour une série 1234.

1234
1243
1423
1432
1342
1324

Ce qui représente 24 binômes (6*4). Je disais 5, car il j'omettais la 1ere, mais il est exact qu'elle représente une combinaison, bien entendu.

En, effet je ne souhaite pas permuter le 1er chiffre. (C'est un détail).

Le but est de trouver, d'une manière exhaustive (et brutale) tous les chemins possibles en entre plusieurs points. (Parcours du point 1 et vers le 2 puis vers les 3 puis vers le 4 (et retour au 1), parcours du point 1 puis vers le 2, vers le 4, puis vers le 3 (et retour au 1), etc....)

Merci pour ta réponse

[invite97a92052]

Ok

Voici le code en question (ça fait 2-3 ans que je le poste sur plein de forums, et il est toujours pas sur google alala !)

Il ne prend en compte que 23 caractères au maximum (c'est énorme, ça génererait un fichier de plus 600000 milliards de Giga octets ), et enregistre les résultats dans bidule.txt (dans le même dossier que l'exécutable).

Pour un nombre n de caractères, j'avais remarqué qu'on pouvait sortir toutes les permutations en imbriquant n-1 boucles.
Pour n non fixé, ça se complique pas mal, il faut donc faire un "tableau dynamique de boucles" pour simuler l'effet des n-1 boucles imbriquées.

Si tu as besoin d'aide ou d'explications, pas de problèmes (car ce code ne parle pas forcément de lui même !)

Il existe aussi des versions récursives de l'algorithme, mais qui sont peut-être moins efficaces (enfin bon, ça dépend de beaucoup de choses... !)

#include <stdio.h> 
#include <string.h> 
#include <stdlib.h> 

void permute(char* const); 

int main(void) { 
    char s[24];
    size_t fin; 

    puts("Entrer les lettres :"); 
    fgets(s, sizeof s, stdin); 
     
    fin = strlen(s)-1; 
     
    if(s[fin] == '\n') 
        s[fin] = '\0'; 
    if(s[0] == '\0') 
        return 0; 

    permute(s); 

    return 0; 
} 


void permute(char* const s) { 
    char 
        c, 
        *pRotation; 
    const unsigned 
        longueurchaine = strlen(s), 
        maxcurseur = longueurchaine-1; 
    unsigned 
        *boucle = calloc(longueurchaine, sizeof *boucle); 
    size_t 
        curseur=0; 
    FILE 
        *fSortie = fopen("bidule.txt", "w"); 


    if(fSortie == NULL) { 
        if(boucle == NULL) 
            return; 
        free(boucle); 
        return; 
    } 
    if(boucle == NULL) { 
        fclose(fSortie); 
        return; 
    } 
     
    boucle[0] = longueurchaine; 


    /* ALGO : c'est cette boucle qui est interessante :*/ 
	while(boucle[0]) {  
		if(boucle[curseur]) {  
			while(curseur < maxcurseur) {  
				++curseur;  
				boucle[curseur] = longueurchaine-curseur;  
			} 
			fputs(s, fSortie);
			fputc('\n', fSortie);  
		}  
		else { 
			--curseur; 
			pRotation = s+curseur;
			c = *pRotation;  
			while(*pRotation = pRotation[1]) // ATTENTION, ceci est une affectation suivie d'un test logique pour savoir si la rotation est finie ou non.
				++pRotation;  
			*pRotation = c;  
		}  
		--boucle[curseur];
	}
     
    free(boucle); 
    fclose(fSortie); 
}

[A voir en vidéo sur Futura]

[inviteb4f1ec9f]

Merci bcp, c'est super.

Je vais tenter de décrypter ton code et l'adapter à ma 'sauce'.

Juste en qq mots, si ce n'est pas trop te demander, peux tu, en français, décrire ton raisonnement pour assurer la permutation de tous les membres d'une série en français (parce que j'en ai usé des feuilles de papier à ecire mes sequences pour tenter de trouver la recursivité du raisonnement.
Ou pour être encore plus clair, peux tu ecrire juste l'organigramme de ton raisonnement.

Quoiqu'il en soit, merci bcp, je vais étudier ça

Bien à toi

P.S
Pardon si je n'etais pas exactement dans le bon forum mais la réponse fut prompt et j'en suis sur, brillante

[invite97a92052]

Content que ça puisse te servir !

Voici comment trouver les permutations à la main (avant de parler de l'algo) :
Déjà, on choisit un sens arbitraire de rotation. Je prendrai la droite.

Imaginons une séquence ABCD
0) première permutation : ABCD

1) ensuite, on va permuter les 2 dernieres lettres (rotation de gauche à droite, c'est le sens que j'ai choisi. mais pour 2 lettres le sens n'est pas important, c'est vrai)
CD devient donc DC
on a donc ABDC

2) ensuite, on refait une rotation des 2 dernières lettres, et on fait juste derrière une rotation des 3 dernières
ABDC redevient ABCD, qui se transforme en ADBC
ADBC

3) on permute les 2 dernières :
ADCB

4) on repermute les 2 dernieres et on permute les 3 dernieres
ADCB -> ADBC -> ACDB

5) les 2 dernieres :
ACDB -> ACBD

6) les 2 dernieres, les 3 dernieres et les 4 dernieres :
ACBD -> ACDB -> ABCD -> DABC

(etc, etc, je ne vais pas faire les 24 !)

"mathématiquement", à l'étape X, on cherche x le plus grand possible tel que X = k*(x!) (k entier), et on permute les 2 dernières lettres, les 3 dernières... jusqu'aux x+1 dernières lettres

"informatiquement", on se fiche de toutes ses formules, ça se fait tout seul en imbriquant n-1 boucles "for", la boucle n° 1 bouclant n fois, la n°2 n-1 fois... et la n° n-1 boucle 2 fois.
(on pourrait mettre une boucle n° n mais ce n'est plus une vraie boucle puisqu'exécutée une seule fois)
Sachant qu'à la fin de la boucle n° i, une rotation de 1 cran vers la droite (ou la gauche donc) des n-i+1 dernières lettres se charge de parachever l'algorithme.

Mais pour n non fixé, impossible d'imbriquer des boucles !
Ici je crée donc un tableau de boucles (pour faire la simulation des boucles imbriquées), et le programme "sait" dans quelle boucle il se trouve à tout instant (c'est le rôle de la variable "curseur"), pour savoir le nombre de lettres à permuter.


Le programme s'arrête quand la boucle la plus globale (boucle n° 0 dans le programme, car en C les indices commencent à 0) à été exécutée n fois.
Quand aux autres boucles, leur compteur est réinitialisé en sortie de boucle à sa valeur initiale pour le prochain passage. La boucle 0 n'est jamais réinitialisée, la boucle 1, n fois, la 2 n*(n-1) fois... etc (on retrouve bien le n*(n-1)*(n-2)*...*3*2*1 = n!

Voilà, j'espère t'avoir un peu éclairci.

Je suis à ta disposition pour toute autre questions et au cas ou je n'ai pas été très clair !