Compte tenu d'une chaîne de longueur 'n'. Comment puis-je obtenir toutes les sous-séquences de la longueur R (R <= N). Je pensais à le faire en utilisant une programmation dynamique mais je ne pouvais pas trouver une bonne solution. Je veux un pseudo code pour cela.
par exemple. Compte tenu de la chaîne "ABC" et R = 2.
sortie: ab Ba acteur Californie avant JC cb
Merci d'avance
3 Réponses :
Il est important de voir la différence entre toutes les substrings possibles (séquence contiguë) et généralement des sous-séquences (pas nécessairement contiguës).
Si cela est vrai, ce que vous avez demandé est appelé combinaisons , et il est Nice d'abord pour estimer combien d'entre eux vous avez donné la longueur de votre chaîne et la taille de votre recherche.
Un algorithme récursif est la meilleure approche ici: cela vous permet d'avoir une longueur de votre recherche en tant que variable. Vous trouverez une réponse parfaite dans Un autre thread Ici.
Je ne dirais pas qu'un algorithme récursif est la "meilleure" approche; C'est peut-être le plus évident. Si les cordes sont très longues, une approche récursive conduira à un débordement de la pile.
@Olicharlesworth C'est l'inconvénient commun de chaque algorithme récursif, non spécifiquement de celui-ci, comme confirmé par le nom de ce site, à la manière suivante :-)
IMO Un algorithme récursif est un bon point de départ pour trouver une solution à un problème. Après avoir trouvé la solution récursive, il peut toujours être transformé en une solution itérative (si cela est pour une raison quelconque nécessaire).
@Christianmammer De mon expérience d'entretiens d'embauche, ils posent souvent les questions qui impliquent d'abord un algorithme récursif avec une discussion ultérieure sur ses avantages et ses contras et, sur demande, sa transformation à une itérative.
Essayez le code suivant (pas de pseudo code mais compréhensible, j'espère):
#include <iostream>
#include <cstdio>
#include <string>
#include <cstring>
#include <vector>
#include <algorithm>
using namespace std;
string S;
int n;
vector<string> L;
void F(int index, int length, string str)
{
if (length == 0) {
L.push_back(str);
} else {
for (int i = index; i < n; i++) {
string temp = str;
temp += S[i];
F(i + 1, length - 1, temp);
}
}
}
int main()
{
S = "abcde"; // replace with your string
n = S.length();
int k = 3; // or what you want
F(0, k, string(""));
int count = 0;
for (int i = 0; i < int(L.size()); i++) {
string temp = L[i];
sort(temp.begin(), temp.end());
do {
cout << temp << endl;
count++;
} while (next_permutation(temp.begin(), temp.end()));
}
cout << endl << "count = " << count << endl;
return 0;
}
public static void combinations(String suffix,String prefix){
if(prefix.length()<0)
return;
System.out.println(suffix);
for(int i=0;i<prefix.length();i++) {
combinations(suffix+prefix.charAt(i),prefix.substring(i+1,prefix.length()));
}
}
//call above function like: combinations("","abcd");
Avec une boucle? Il n'y a que
N-R + 1 de ces sous-séquences.des sous-séquences contiguës ou non contiguës?
Je veux dire toutes les permutations NPR.
npr = Nombre de façons d'obtenir un sous-ensemble commandé d'éléments K à partir d'un ensemble de n éléments
Oui, une liste contenant NPR no des chaînes devrait être la sortie
Je ne pense pas que BA soit à la recherche de l'ABC