#1 Le 18/04/2012, à 18:42
- Maneithel
[RÉSOLU] Algo de mélange de deux chaînes
Salut tout le monde !
Je cherche un algo qui m'avait l'air plus simple que ça au début Je voudrais mélanger deux chaînes str et sep, telles que str contient un chaîne de caractère quelconque et sep contient un nombre de "*" donné, par exemple :
str = "str"
sep = "**"
Il m'intéresse d'en extraire tous les "mélanges possibles", conservant l'ordre des caractères de str, comme par exemple
res[10][5] = {
s,t,r,*,*,
s,t,*,r,*,
s,t,*,*,r,
s,*,t,r,*,
s,*,t,*,r,
s,*,*,t,r,
*,s,t,r,*,
*,s,t,*,r,
*,s,*,t,r,
*,*,s,t,r
}
ici, "10" est en fait le nombre de combinaison de 2 étoiles parmi 5 caractères total et "5" est le nombre de caractères au total.
Pour une fonction faisant ce boulot avec une chaîne de caractère de longueur quelconque et un nombre de "*" quelconque aussi (mais plus petit ou égal à la longueur de str).
des idées ?
EDIT: Moi je fais ça en C++ mais je prends les idées peu importe le langage
Dernière modification par Maneithel (Le 18/04/2012, à 22:20)
Hors ligne
#2 Le 18/04/2012, à 19:29
- pingouinux
Re : [RÉSOLU] Algo de mélange de deux chaînes
Bonsoir,
Voici comment je verrais l'algorithme :
On génère toutes les combinaisons possibles de 2 éléments (2 = nb d'éléments de sep) choisis parmi les 5 premiers entiers (5 = nb d'éléments de str + nb d'éléments de sep)
Dans chaque combinaison, les deux entiers indiquent la position des éléments de sep dans le résultat. Les autres positions sont remplies dans l'ordre avec les éléments de str.
Par exemple, avec le tirage {3,5}, on génère s,t,*,r,* (* en position 3 et 5)
J'espère que c'est assez clair, sinon je peux détailler.
Dernière modification par pingouinux (Le 18/04/2012, à 19:32)
Hors ligne
#3 Le 18/04/2012, à 20:33
- Maneithel
Re : [RÉSOLU] Algo de mélange de deux chaînes
Je suis pas sûr que je saisis... est-ce que tu prends en considération une taille variable de sep ?
j'en comprends :
Soit n, la taille de str, et m, la taille de sep, n <= m.
On cherche les k = (n+m)C(m) façons de placer les étoiles dans str.
Tu propose de générer k combinaisons de m entiers a_1, a_2, ..., a_m, chacun différents au sein d'une même combinaison et compris dans l'intervalle [0,n+m].
Jusque là, ça roule. Mais je vois mal comment les générer
Hors ligne
#4 Le 18/04/2012, à 21:45
- pingouinux
Re : [RÉSOLU] Algo de mélange de deux chaînes
Par exemple, en python :
#! /usr/bin/python
# -*- coding: utf-8 -*-
from itertools import combinations
str="str"; sep="**"; n=len(str); m=len(sep)
combin=combinations(range(0,n+m),2)
for k in combin :
resul=""; p_str=0; p_sep=0
for i in range(n+m) :
if i in k : resul+=sep[p_sep]; p_sep+=1
else : resul+=str[p_str]; p_str+=1
print("%s"%",".join(resul))
Hors ligne
#5 Le 18/04/2012, à 22:19
- Maneithel
Re : [RÉSOLU] Algo de mélange de deux chaînes
Woa, je dois vraiment apprendre le python.
Je saisie trèèèès bien maintenant! Il me reste à implémenter un version c++ de intertools.combinations.
Merci infiniment !
Hors ligne
#6 Le 18/04/2012, à 22:57
- Bousky
Re : [RÉSOLU] Algo de mélange de deux chaînes
Moi je serais parti sur un comptage binaire :
- bit à 0 = prend un caractère de la première chaine
- bit à 1 = prend un caractère de la deuxième chaine
Après il suffit d'incrémenter un entier et d'enlever certains cas (du genre 0, càd que la première chaine).
Bon après pour générer des chaines de plus de 64 caractères c'est moins pratique.
Linux qui plante complètement ? Plus rien ne répond ? On peut toujours le redémarrer proprement :
Alt + SysRq + REISUB (Retourne En Islande Sur Un Bateau !)
Hors ligne
#7 Le 19/04/2012, à 00:44
- Maneithel
Re : [RÉSOLU] Algo de mélange de deux chaînes
Je saisis mal, Bousky, j'ai vraiment l'impression qu'on s'en sort pas sans aller chercher toutes les combinaisons même avec ta technique.
Bon, voici quelque chose de laid, aussi laid que peut l'être le C++. C'est d'autant plus laid parce qu'on y trouve des morceau de STL et de Qt en même temps. Le principe est là quand même.
D'abord, j'ai trouvé sur un autre forum StackOverflow cette fonction proposé par l'utilisateur Maciej Hehl. Le lien est bon, plusieurs personnes proposent plusieurs solutions en plusieurs langages (ça fait plusieurs plusieurs !).
Elle prend en paramètre l'itérateur de début et de fin d'un contenant de l’ensemble duquel on veut tirer les combinaisons et la taille de chaque combinaison. Elle retourne un
std::vector< std::vector <Fci> >
Fci étant le type d'itérateur qu'on lui a passé en paramètre. Elle nécessite d'inclure <vector> et <stdexcept>.
template <typename Fci> // Fci - forward const iterator
std::vector<std::vector<Fci> >
enumerate_combinations(Fci begin, Fci end, unsigned int combination_size)
{
if(begin == end && combination_size > 0u)
throw std::invalid_argument("empty set and positive combination size!");
std::vector<std::vector<Fci> > result; // empty set of combinations
if(combination_size == 0u) return result; // there is exactly one combination of
// size 0 - emty set
std::vector<Fci> current_combination;
current_combination.reserve(combination_size + 1u); // I reserve one aditional slot
// in my vector to store
// the end sentinel there.
// The code is cleaner thanks to that
for(unsigned int i = 0u; i < combination_size && begin != end; ++i, ++begin)
{
current_combination.push_back(begin); // Construction of the first combination
}
// Since I assume the itarators support only incrementing, I have to iterate over
// the set to get its size, which is expensive. Here I had to itrate anyway to
// produce the first cobination, so I use the loop to also check the size.
if(current_combination.size() < combination_size)
throw std::invalid_argument("combination size > set size!");
result.push_back(current_combination); // Store the first combination in the results set
current_combination.push_back(end); // Here I add mentioned earlier sentinel to
// simplyfy rest of the code. If I did it
// earlier, previous statement would get ugly.
while(true)
{
unsigned int i = combination_size;
Fci tmp; // Thanks to the sentinel I can find first
do // iterator to change, simply by scaning
{ // from right to left and looking for the
tmp = current_combination[--i]; // first "bubble". The fact, that it's
++tmp; // a forward iterator makes it ugly but I
} // can't help it.
while(i > 0u && tmp == current_combination[i + 1u]);
// Here is probably my most obfuscated expression.
// Loop above looks for a "bubble". If there is no "bubble", that means, that
// current_combination is the last combination, Expression in the if statement
// below evaluates to true and the function exits returning result.
// If the "bubble" is found however, the ststement below has a sideeffect of
// incrementing the first iterator to the left of the "bubble".
if(++current_combination[i] == current_combination[i + 1u])
return result;
// Rest of the code sets posiotons of the rest of the iterstors
// (if there are any), that are to the right of the incremented one,
// to form next combination
while(++i < combination_size)
{
current_combination[i] = current_combination[i - 1u];
++current_combination[i];
}
// Below is the ugly side of using the sentinel. Well it had to haave some
// disadvantage. Try without it.
result.push_back(std::vector<Fci>(current_combination.begin(),
current_combination.end() - 1));
}
}
Voici un exemple (pas propre) d'utilisation.
int main{
// La chaîne str dans laquelle on doit insérer les séparateurs
QString str = "str";
// Les séparateurs
QString sep = "**";
// Leurs tailles respectives
int n = str.size(); int m = sep.size();
// Un liste des nombres de 0 à n+m-1 (pour ressemblance avec exemple python)
vector<int> rangeSTL;
QList<int> range;
for(int i = 0; i < n+m; i++) {
range << i;
rangeSTL.push_back(i);
}
// Liste des combinaisons (voir la définition de enumerate_combinations)
// i.e. toutes les façons de choisir m items parmi les n+m
vector< vector< vector<int>::iterator > > combin
= enumerate_combinations(rangeSTL.begin(),rangeSTL.end(),m);
// Conversion d'iterator en int (pour clareté)
QList< QList<int> > combinaisons;
for(int i = 0; i < combin.size(); i++){
QList<int> buff;
for(int j = 0; j < combin[i].size(); j++){
buff.push_back( *combin[i][j] );
}
combinaisons.push_back(buff);
}
// Reprise de l'algo en python de pingouinux
foreach(QList<int> k, combinaisons){
QString resul = "";
int p_str = 0; int p_sep = 0;
foreach(int i, range){
if(k.contains(i)) resul += sep[p_sep++];
else resul += str[p_str++];
}
cout << resul.toStdString() << endl;
}
}
Et voici la sortie :
**str
*s*tr
*st*r
*str*
s**tr
s*t*r
s*tr*
st**r
st*r*
str**
Hors ligne
#8 Le 19/04/2012, à 01:36
- Bousky
Re : [RÉSOLU] Algo de mélange de deux chaînes
Je saisis mal, Bousky, j'ai vraiment l'impression qu'on s'en sort pas sans aller chercher toutes les combinaisons même avec ta technique.
Le principe de ma technique est simplement de faire « i++ » pour passe d'une combinaison à la suivante.
Et d'ailleurs, n'est-ce pas toi qui demande à lister toutes les combinaisons ?
Dernière modification par Bousky (Le 19/04/2012, à 01:41)
Linux qui plante complètement ? Plus rien ne répond ? On peut toujours le redémarrer proprement :
Alt + SysRq + REISUB (Retourne En Islande Sur Un Bateau !)
Hors ligne
#9 Le 19/04/2012, à 05:32
- pingouinux
Re : [RÉSOLU] Algo de mélange de deux chaînes
@Bousky #6 :
Ta méthode est une possibilité, mais il faut ne garder que les nombres constitués de trois bits à 0, et deux bits à 1
(dans l'exemple avec "str" et "**")
Hors ligne
#10 Le 19/04/2012, à 07:39
- Maneithel
Re : [RÉSOLU] Algo de mélange de deux chaînes
Bousky -> Ok, comme un masque. C'est vrai que dans ce cas, il te faudrait filtrer le nombre de bits à 1.
À propos, si vous êtes curieux du contexte, googlez "An HMM for detecting spam mail" signé par José Gordillo et Eduardo Conde .(attention, papier très peu coopératif ici)
Hors ligne