Je veux générer toutes les variantes avec des répétitions d'une chaîne en C ++ et je préfère vivement un algorithme non récursif. J'ai monté un algorithme récursif dans le passé, mais en raison de la complexité (r ^ n) J'aimerais voir une approche itérative.
Je suis assez surpris que je n'ai pas pu trouver une solution à ce problème n'importe où sur le Web ou sur Stackoverflow.
J'ai proposé un script Python qui fait aussi ce que je veux aussi: Sortie: aaaa
aaab
aaba
aabb
abaa
abaisser
abb
abbb
baaa
baab
baba
babb
BBAA
bébut
BBBA
BBBB
Idéalement, je voudrais un programme C ++ pouvant produire la sortie exacte, en prenant exactement les mêmes paramètres. Ceci est à des fins d'apprentissage, ce ne sont pas des devoirs. J'aimerais que mes devoirs soient comme ça.
3 Réponses :
Vous pouvez y penser comme comptage, dans un radix égal au nombre de caractères de l'alphabet (prenant un soin particulier de plusieurs caractères égaux dans l'alphabet si c'est une entrée possible). Le juste effectuer une recherche sur les transformations de Radix, implémenter une cartographie de chaque "chiffre" à caractère correspondant, puis simplement faire une boucle de 0 à Word_length alphabet_size Un tel algorithme doit fonctionner de temps linéairement proportionnel au nombre de chaînes qui doivent être produites à l'aide d'une quantité constante de mémoire. démonstration en Java sortie: AAAA AAAA AAABA ... L'exemple, par exemple, est la représentation binaire des numéros 0-15.
J'ai une question exactement: ** string str = entier.tostring (i, alphabet.length); ** J'essaie de le mettre en œuvre en C ++ en faisant simplement String STD = STD :: TO_String (i) Qu'est-ce que le différence?
@Hanigoc to_string se convertit uniquement à la base 10, tandis que Tostring se convertit vers la base donnée (alphabet.length)
Voici la recette générale, non spécifique C ++ pour mettre en œuvre le produit:
Prenez la chaîne d'entrée de produit "abc .." pour générer matrice "abc .." x "abc .." . N ^ 2 Complexité.
Représenter matricielle comme multiplication de vecteur et répéter par "abc ", complexité (n ^ 2) * N , répéter.
STL comme fonction similaire pour Next_Variation. Acceptez les itérateurs de tout conteneur de type de type. Vous pouvez également utiliser Float / Doubles également. L'algorithme est-il propre est très simple. L'exigence d'itérateur est d'être en avant. Même une liste STD :: Liste <...> peut être utilisée.
template<class _Tnumber, class _Titerator >
bool next_variation
(
_Titerator const& _First
, _Titerator const& _Last
, _Tnumber const& _Upper
, _Tnumber const& _Start = 0
, _Tnumber const& _Step = 1
)
{
_Titerator _Next = _First;
while( _Next != _Last )
{
*_Next += _Step;
if( *_Next < _Upper )
{
return true;
}
(*_Next) = _Start;
++_Next;
}
return false;
}
int main( int argc, char *argv[] )
{
std::string s("aaaa");
do{
std::cout << s << std::endl;
}while (next_variation(s.begin(), s.end(), 'c', 'a'));
std::vector< double > dd(3,1);
do{
std::cout << dd[0] << "," << dd[1] << "," << dd[2] << "," << std::endl;
}while( next_variation<double>( dd.begin(), dd.end(), 5, 1, 0.5 ) );
return EXIT_SUCCESS;
}
Bienvenue dans le débordement de la pile! Bien que vous ayez peut-être résolu le problème de ce utilisateur, les réponses de codes uniquement ne sont pas très utiles pour les utilisateurs qui viennent à cette question à l'avenir. Veuillez éditer votre réponse pour expliquer pourquoi votre code résout le problème initial.
cplusplus.com/reference/algorithm/next_permutation ?
Votre question est-elle vraiment sur la manière de mettre en œuvre un produit cartésien en C ++? Comment voulez-vous être général avec la répétition et le nombre de caractères?
Je ne veux pas de permutation, je veux des variations avec des répétitions. J'ai regardé le produit cartésien, mais cela ressemble beaucoup plus que ce que je veux faire, au moins basé sur les exemples d'implémentations que j'ai trouvées jusqu'à présent.
Vous pouvez utiliser des permutations, par exemple générer un ensemble de tuples commandés (4 dans votre exemple), permorez chaque tuple pour obtenir toutes les permutations possibles. la commande n'est pas tout à fait comme si vous le souhaitez, mais vous pouvez le réparer
Il n'y a rien de mal à la solution récursive. La pile y pousse linéairement pendant que le temps de course augmente de manière exponentielle, de sorte que vous manquez de patience longtemps avant de ne pas manquer de pile.