[Algo] Mélanger un tableau/une chaine ?

v_a_n_e_s · Janvier 19, 2006, 1:48

Salut à tous,

petite question stupide d’algo, je cherche à afficher les X occurences données par un tableau de caractères

je m’explique

soit un tableau tableau [a,b,c]

je cherche une fonction qui me renverrait
a,b,c
a,c,b
b,a,c
b,c,a
c,a,b
c,b,a

je sais que c’est des probas, des maths et autres (et donc qu’en fouillant dans mes cours de DPCT je retrouverais), mais là je suis au taf et une collègue m’a demandé de lui trouver un mot avec une chaine de 7 caractères…

system · Janvier 19, 2006, 2:08

Tu veux l’algo ou la réponse à sa question ?

Parce que si c’est la réponse, dict sous linux permet de le faire simplement (je sais pas si j’ai le dico français, mais je peux regarder) et donc on peut facilement te donner sa réponse.

Et puis, pour 7 caractères, ça va quand même te faire 5040 chaînes à lire, ça fait peut-être beaucoup, non ?

v_a_n_e_s · Janvier 19, 2006, 2:13

[quote=« genji, post:2, topic: 27062 »]Tu veux l’algo ou la réponse à sa question ?

Parce que si c’est la réponse, dict sous linux permet de le faire simplement (je sais pas si j’ai le dico français, mais je peux regarder) et donc on peut facilement te donner sa réponse.

Et puis, pour 7 caractères, ça va quand même te faire 5040 chaînes à lire, ça fait peut-être beaucoup, non ?[/quote]

les 2 mon capitaine

par curiosité, l’algo

par simplicité, la chaine qui correspond aux lettres suivantes, alors

E B T T E R I

y’a ptet des fanas du scrabble ou du boggle ici, après tout

system · Janvier 19, 2006, 2:19

Mmmmh, il a rien trouvé dans le dico français + anglais, me voilà tout perplexifié.

Edit: rien trouvé non plus sur http://www.capeutservir.com/mots/anagramme.php

bishop · Janvier 19, 2006, 2:23

[quote=“vns, post:1, topic: 27062”]Salut à tous,

petite question stupide d’algo, je cherche à afficher les X occurences données par un tableau de caractères

je m’explique

soit un tableau tableau [a,b,c]

je cherche une fonction qui me renverrait
a,b,c
a,c,b
b,a,c
b,c,a
c,a,b
c,b,a
je sais que c’est des probas, des maths et autres (et donc qu’en fouillant dans mes cours de DPCT je retrouverais), mais là je suis au taf et une collègue m’a demandé de lui trouver un mot avec une chaine de 7 caractères…[/quote]

Hmm, mais c’est un algo interessant ca, ma brave dame.

v_a_n_e_s · Janvier 19, 2006, 2:24

oué bah dixit la collègue “ah bah je regarderais dans mon femme actuelle, il manquait ptet une lettre :s”

du coup ça ferait batterie :s

Totoradio · Janvier 19, 2006, 2:25

Cette chaine ne correspond a aucun mot que ce soit en anglais, français ou hollandais, come tu pourras le constater ici

Edit: grilled

v_a_n_e_s · Janvier 19, 2006, 2:45

ça retire rien au fait que si qq’un a un algo en pseudo code pour faire un anagramme, je suis preneur

parce que j’ai commencé à chercher, mais pas moyen…

j’imagine qu’on utilise une fonction récursive pour pas se casser le derche, mais pas moyen de l’écrire

un algo mastah dans le secteur ?

bishop · Janvier 19, 2006, 2:49

[quote=« vns, post:8, topic: 27062 »]ça retire rien au fait que si qq’un a un algo en pseudo code pour faire un anagramme, je suis preneur

parce que j’ai commencé à chercher, mais pas moyen…

j’imagine qu’on utilise une fonction récursive pour pas se casser le derche, mais pas moyen de l’écrire

un algo mastah dans le secteur ?[/quote]

Bon, c’est pas de l’algo, c’est du c# passque g la flemme de traduire. Pis ca t’occupera :

[code]
// Le tableau de caracteres
char[] texte = this.textBox1.Text.ToCharArray();
// Longueur du texte
int longueur = texte.Length;
// Position courante
int position = longueur-1;
// Tableau pour le résultat
ArrayList al = new ArrayList();
// Nombre max d’itérations
int iterationmax = 0;
// On ajoute le cas initial
al.Add(new string(texte));

		// Calcul du nombre max d'itération
		for (int i = longueur; i > 1; i--)
		{
			if (i == longueur)
				iterationmax = longueur;
			else
				iterationmax *= i;

		}

		// Boucle qui inverse toutes les lettres
		for (int i = 0; i < iterationmax; i++)
		{
			// reset de la position
			if (position == 0)
				position = longueur-1;

			// Inversion
			char tmp = texte[position];
			texte[position] = texte[--position];
			texte[position] = tmp;

			al.Add(texte);
			
		}[/code]

Edit : L’appli en .net 2.0 ici : www.zebishop.Com/files/Release/vns/vns.rar
Edit 2 : Moi j’ai testé et ca marche

system · Janvier 19, 2006, 2:51

Un truc du genre (pseudo-code, je fais pas de C)

list_anag = anagramme(prec, substring)

n = length(substring)

if n= 0
print prec;
else
for i = 1:n
first_char = substring(i)
anagramme([prec first_char], substring([1:i-1 i+1:n])
end
end

Bon, mon truc sent le Matlab à plein nez, ce qui est pas terrible. Je ne sais pas non plus si c’est optimal, mais je pense que ça marche.

Edit: grillé
Edit 2: comment on fait pour mettre en page un zouli nalgo ?

v_a_n_e_s · Janvier 19, 2006, 3:04

Merci bishop !

Son algo traduit en PHP donne ça (oh mon dieu quel travail surhumain j’ai du faire pour le transformer)

[code]$longueur = strlen($chaine);
$position = $longueur - 1;
$iterationmax = 0;

echo $chaine;
echo «
»;

for ($i = $longueur; $i > 1; $i–) {
if ($i == $longueur) {
$iterationmax = $longueur;
} else {
$iterationmax *= $i;
}
}

for ($i = 0; $i < $iterationmax; $i++) {
if ($position == 0) {
$position = $longueur - 1;
}
$tmp = $chaine[$position];
$chaine[$position] = $chaine[–$position];
$chaine[$position] = $tmp;

echo $chaine;
echo "<br />";

}[/code]

oué, trop dur hein

Merci encore bishop.

v_a_n_e_s · Janvier 19, 2006, 3:19

tmp = texte[position] texte[position] = texte[--position]; texte[position] = tmp;

je comprends pas trop là par contre…

ça veut dire que, dans le cas ou texte est "ABC"
si position vaut 1 (cas de la 1ère boucle)

tmp vaut B <- tmp = texte[position]
on met A à la place de B <- texte[position] = texte[–position]
puis on remet B <- texte[position] = tmp

donc si j’imprime texte à la fin de la premiere boucle, je devrais avoir
texte[0] : A
texte[1] : B
texte[2] : C

Or la 1ère ligne renvoie A C B …

j’ai décroché où ?

vanes, boulet à temps partiel.

anon10092024 · Janvier 19, 2006, 3:36

Bishop : je pense qu’il marche pas ton algo
C’est un bonne algo pour melanger les lettres par contre ^^
Et la premiere partie (le calcul du nombre d’iteration, ca revient a faire n! (n factoriel )

Afin, comme ca, a vu de nez, je suis sceptique (surtout sur la partie de permutation des lettres)

Mais je peux me tromper

v_a_n_e_s · Janvier 19, 2006, 3:53

cben76 > sisi il marche l’algo, je confirme, c’est juste que je comprends pas comment il marche

edit : ah bah non, ou alors c’est mon implémentation qui chie dans la colle…

ex :

http://192.168.1.214/scramble.php?chaine=abcd

24 possibilités : abcd abdc adbc dabc dacb dcab cdab cdba cbda bcda bcad bacd abcd abdc adbc dabc dacb dcab cdab cdba cbda bcda bcad bacd abcd

(en mettant le resultat dans un fichier texte, j’obtiens ça

mathieu@pdc:~$ sort temp | wc -l
24
mathieu@pdc:~$ sort temp | uniq | wc -l
12

y’a donc à chaque fois une occurence en double…

Phil · Janvier 19, 2006, 3:59

En base de données tu créées une table alphabet avec les 26 lettres.
Ensuite tu créées la requêtes suivantes sans jointures, ce qui revient à faire un produit cartésien select a1.lettre,a2.lettre,...,a7.lettre from alphabet a1, alphabet a2, ...alphabet a7equivalente àselect a1.lettre,a2.lettre,...,a7.lettre from alphabet a1 cross join alphabet a2 cross join ...alphabet a7En algo je suis moins sûr.
Tu fais une première boucle sur les 26 lettres puis une sous-boucle sur 26 lettres sauf celles des niveaux de boucle d’au-dessus etc… jusqu’à 7 boucles. Cela me parait trop simple ou alors le “sauf celles des niveaux de boucle d’au-dessus” doit être plus complexe que je ne le crois. ça m’étonnerait que ça fonctionne.

edit: même logique en récurssif.
Après faut pas perdre de vue que le nombre de résultats attendus est scientique. Ce sont les Anp ou Cnp. Je ne me souviens plus.

Kenny209 · Janvier 19, 2006, 5:12

Oui c’est vrai, avec l’algo de bishop j’ai moi aussi des doublons (avec “abcd”).
Et je dois dire que j’ai pas bien compris non plus le principe de son algo…

Par contre j’ai bricolé une petite fonction récursive en C pour faire le boulot:

[code]#include <stdio.h>
#include <string.h>

void swap (char tab[], int i, int j)
{
char tmp = tab[i];
tab[i] = tab[j];
tab[j] = tmp;
}

void enumeration (char tab[], int deb, int fin)
{
int i;
for (i = deb; i <= fin; i++)
{
swap(tab, deb, i);
enumeration(tab, deb+1, fin);
swap(tab, deb, i);
}
if (deb == fin)
printf("%s\n", tab);
}

int main (int argc, char **argv)
{
enumeration(argv[1], 0, strlen(argv[1])-1);
return 0;
}[/code]

Ca a l’air de fonctionner…

bishop · Janvier 19, 2006, 6:46

ah wai tiens, le mien marche pas en fait. Ca m’apprendra a faire les trucs a la va vite

system · Janvier 19, 2006, 7:16

Le programme en Matlab est donc :

% Début

function anagramme(prec, substring)

n = length(substring);

if n == 0

disp(prec); % Si on a épuisé tous les caractères, afficher la chaîne.

else

for i = 1:n % Pour tous les caractères de la liste

first_char = substring(i); % Mettre ce caractère en premier.
anagramme([prec first_char], substring([1:i-1 i+1:n])); % Recommencer l’algo avec les caractères restants

end

% Fin

et on obtient :

anagramme(‹ ›, ‹ abcd ›)
abcd
abdc
acbd
acdb
adbc
adcb
bacd
badc
bcad
bcda
bdac
bdca
cabd
cadb
cbad
cbda
cdab
cdba
dabc
dacb
dbac
dbca
dcab
dcba

Edit: apu fôte d’aurtograf

Twen · Janvier 19, 2006, 7:34

Personne pour le traduire en assembleur ?

GloP · Janvier 20, 2006, 3:24

Edit: le lourd…

Le compilateur L’interpreteur