Comment générer toutes les permutations d'une chaîne de caractères en PHP?
J'ai besoin de l'aide d'un algorithme de retour de toutes les combinaisons possibles de tous les caractères dans une chaîne.
J'ai essayé:
$langd = strlen($input);
for($i = 0;$i < $langd; $i++){
$tempStrang = NULL;
$tempStrang .= substr($input, $i, 1);
for($j = $i+1, $k=0; $k < $langd; $k++, $j++){
if($j > $langd) $j = 0;
$tempStrang .= substr($input, $j, 1);
}
$myarray[] = $tempStrang;
}
Mais qui ne retourne que la même quantité de combinaison de la longueur de la chaîne.
Dire la $input = "hey"
, le résultat serait: hey, hye, eyh, ehy, yhe, yeh
.
- Ce que vous voulez sont appelés des "permutations", pas des "combinaisons".
- Je ne pense pas que Johan signifiait combinaison dans le sens mathématique. Mais oui, vous avez raison.
- Également considérer, que vous aurez
n!
résultats. Pour une entrée de chaîne de longueur 12 (pas de duplicate caractères), c'est environ 480 millions de résultats, ce qui nécessite environ 5 GO de mémoire. - Je sais. Mais il permet d'utiliser le bon terme, lorsque vous Tapez une solution.
- Toutes les réponses ici que suggérer mandature/récursivité pour se trompent. Voir ici stackoverflow.com/questions/2529508/...
- Qu'est-ce que mal en utilisant la récursivité pour ce problème? Sûr qu'il y a plusieurs approches pour résoudre ce et le lien wiki suggéré par vous est l'un d'entre eux.
- Salut, Il y a une bibliothèque PHP qui fait tout ce dont vous avez besoin, à l'aide de générateurs et/ou des itérateurs. Trouver la lib ici: github.com/drupol/phpermutations Laissez-moi savoir si vous avez besoin d'aide.
Vous devez vous connecter pour publier un commentaire.
Vous pouvez utiliser un suivi basé sur l'approche systématique de générer toutes les permutations:
De sortie:
aa
. techniquement, il a pour afficher uniquement lesaa
. mais ici, il montreaa aa
.Ma variante (fonctionne aussi bien avec le tableau ou une chaîne d'entrée)
P. S.: Downvoter, veuillez expliquer votre position. Ce code utilise des
str_split
etarray_diff_key
fonctions standard, mais ce bout de code est la plus petit, elle met en œuvre pur queue de récursivité avec un seul paramètre d'entrée et il est isomorphe à l'entrée type de données.Peut-être qu'il va perdre des repères un peu lorsque l'on compare avec d'autres implémentations (mais la performance est en fait presque la même que dans @codaddict de réponse pour plusieurs chaînes de caractères), mais pourquoi on ne peut pas dire que l'on considère comme l'une des différentes alternatives qui a ses propres avantages?
$arg
, les permutations dans$result
ne sont pas uniques.Je mettrais tous les caractères dans un tableau, et écrire une fonction récursive qui bande out " tous les autres personnages. Si le tableau est vide, à une référence tableau transmis.
Imprime:
Ah oui,
combinaisons = ordre se complique pas d'importance.
permutations = ordre a de l'importance.
Donc bon, oh yeh sont tous de la même combinaison, mais 3 permutations comme mentionné. Montre que l'échelle des éléments va très vite. Il s'appelle factorielle, et est écrit comme 6! = 6*5*4*3*2*1 = 720 les éléments (pour 6 chaîne de caractères). 10 chaîne de caractères sera de 10! = 3628800 permutations, ce qui est un très grand tableau. Dans cet exemple, il est 3! = 3*2*1 = 6.
Mon approche utilise la récursivité et pas de boucles, veuillez vérifier et donner de la rétroaction: