Contenu | Rechercher | Menus

Annonce

Si vous avez des soucis pour rester connecté, déconnectez-vous puis reconnectez-vous depuis ce lien en cochant la case
Me connecter automatiquement lors de mes prochaines visites.

À propos de l'équipe du forum.

#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 wink 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 wink

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 sad

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

Maneithel a écrit :

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) wink

Hors ligne