String e la mappatura dei caratteri domanda per il guru ci

Question

Ecco un problema questo è mi ha fatto perplessi (soluzione saggia):

Data una str S, applicare le mappature dei caratteri Cm = {a=(m,o,p),d=(q,u),...} e stampare tutte le combinazioni possibili utilizzando C o C++.

La stringa può essere di qualsiasi lunghezza e il numero di mapping di caratteri varia e non ci saranno mappature mappate a un'altra mappa (evitando così dipendenze circolari).

Per fare un esempio: stringa abba con mappature a=(e,o), d=(g,h), b=(i) sarebbe stampare:

abba,ebba,obba,abbe,abbo,ebbe,ebbo,obbe,obbo,aiba,aiia,abia,eiba,eiia,...... 

Answer 1

Definitivamente possibile, non molto difficile ... ma questo genererà molte stringhe di sicuro.

La prima cosa da osservazione è che si sa quante corde sta andando a generare in anticipo, quindi è facile fare qualche controllo di integrità :)

La seconda: suona come una soluzione ricorsiva sarebbe stato facile (come molti problemi di attraversamento).

class CharacterMapper 
{ 
public: 
    CharacterMapper(): mGenerated(), mMapped() 
    { 
    for (int i = -128, max = 128; i != max; ++i) 
     mMapped[i].push_back(i); // 'a' is mapped to 'a' by default 
    } 

    void addMapped(char origin, char target) 
    { 
    std::string& m = mMapped[origin]; 
    if (m.find(target) == std::string::npos) m.push_back(target); 
    } // addMapped 

    void addMapped(char origin, const std::string& target) 
    { 
    for (size_t i = 0, max = target.size(); i != max; ++i) this->addMapped(origin, target[i]); 
    } // addMapped 

    void execute(const std::string& original) 
    { 
    mGenerated.clear(); 
    this->next(original, 0); 
    this->sanityCheck(original); 
    this->print(original); 
    } 

private: 
    void next(std::string original, size_t index) 
    { 
    if (index == original.size()) 
    { 
     mGenerated.push_back(original); 
    } 
    else 
    { 
     const std::string& m = mMapped[original[index]]; 
     for (size_t i = 0, max = m.size(); i != max; ++i) 
     this->next(original.substr(0, index) + m[i] + original.substr(index+1), index+1); 
    } 
    } // next 

    void sanityCheck(const std::string& original) 
    { 
    size_t total = 1; 
    for (size_t i = 0, max = original.size(); i != max; ++i) 
     total *= mMapped[original[i]].size(); 

    if (total != mGenerated.size()) 
     std::cout << "Failure: should have found " << total << " words, found " << mGenerated.size() << std::endl; 
    } 

    void print(const std::string& original) const 
    { 
    typedef std::map<char, std::string>::const_iterator map_iterator; 
    typedef std::vector<std::string>::const_iterator vector_iterator; 

    std::cout << "Original: " << original << "\n"; 

    std::cout << "Mapped: {"; 
    for (map_iterator it = mMapped.begin(), end = mMapped.end(); it != end; ++it) 
     if (it->second.size() > 1) std::cout << "'" << it->first << "': '" << it->second.substr(1) << "'"; 
    std::cout << "}\n"; 

    std::cout << "Generated:\n"; 
    for (vector_iterator it = mGenerated.begin(), end = mGenerated.end(); it != end; ++it) 
     std::cout << " " << *it << "\n"; 
    } 

    std::vector<std::string> mGenerated; 
    std::map<char, std::string> mMapped; 
}; // class CharacterMapper 


int main(int argc, char* argv[]) 
{ 
    CharacterMapper mapper; 
    mapper.addMapped('a', "eo"); 
    mapper.addMapped('d', "gh"); 
    mapper.addMapped('b', "i"); 
    mapper.execute("abba"); 
} 

Ed ecco l'output:

Original: abba 
Mapped: {'a': 'eo''b': 'i''d': 'gh'} 
Generated: 
    abba 
    abbe 
    abbo 
    abia 
    abie 
    abio 
    aiba 
    aibe 
    aibo 
    aiia 
    aiie 
    aiio 
    ebba 
    ebbe 
    ebbo 
    ebia 
    ebie 
    ebio 
    eiba 
    eibe 
    eibo 
    eiia 
    eiie 
    eiio 
    obba 
    obbe 
    obbo 
    obia 
    obie 
    obio 
    oiba 
    oibe 
    oibo 
    oiia 
    oiie 
    oiio 

Sì, piuttosto lunga, ma c'è un sacco che non partecipa direttamente al calcolo (inizializzazione, i controlli, la stampa). I metodi principali sono next che implementa la ricorsione.

Answer 2

Essenzialmente si vuole fare una ricerca in profondità (DFS) o qualsiasi altro attraversamento verso il basso un grafico parola aciclico (DAWG). Pubblicherò qualche codice a breve.

Answer 3

Il modo in cui farei questo è creare una serie di indici della stessa lunghezza della stringa, tutti inizializzati a zero. Quindi consideriamo questa matrice di indici come un contatore per enumerare tutti i possibili mapping della nostra stringa sorgente. Un indice 0 mappa quella posizione nella stringa alla prima mappatura per quel carattere, un 1 al secondo, ecc. Possiamo attraversarli in ordine semplicemente incrementando l'ultimo indice dell'array, portandoci alla posizione successiva quando raggiungere il numero massimo di mappature per quella posizione.

Per usare il tuo esempio, abbiamo le mappature

'a' => 'e', 'o' 
'b' => 'i' 

Con la stringa di input "abba", abbiamo bisogno di un array di quattro elementi per i nostri indici:

[0,0,0,0] => "abba" 
[0,0,0,1] => "abbe" 
[0,0,0,2] => "abbo" 
[0,0,1,0] => "abia" 
[0,0,1,1] => "abie" 
[0,0,1,2] => "abio" 
[0,1,0,0] => "aiba" 
[0,1,0,1] => "aibe" 
[0,1,0,2] => "aibo" 
[0,1,1,0] => "aiia" 
[0,1,1,1] => "aiie" 
[0,1,1,2] => "aiio" 
[1,0,0,0] => "ebba" 
[1,0,0,1] => "ebbe" 
[1,0,0,2] => "ebbo" 
[1,0,1,0] => "ebia" 
[1,0,1,1] => "ebie" 
[1,0,1,2] => "ebio" 
[1,1,0,0] => "eiba" 
[1,1,0,1] => "eibe" 
[1,1,0,2] => "eibo" 
[1,1,1,0] => "eiia" 
[1,1,1,1] => "eiie" 
[1,1,1,2] => "eiio" 
[2,0,0,0] => "obba" 
[2,0,0,1] => "obbe" 
[2,0,0,2] => "obbo" 
[2,0,1,0] => "obia" 
[2,0,1,1] => "obie" 
[2,0,1,2] => "obio" 
[2,1,0,0] => "oiba" 
[2,1,0,1] => "oibe" 
[2,1,0,2] => "oibo" 
[2,1,1,0] => "oiia" 
[2,1,1,1] => "oiie" 
[2,1,1,2] => "oiio" 

Prima di iniziare la generazione di questi stringhe, avremo bisogno di un posto in cui archiviarle, che in C significa che dobbiamo allocare memoria. Fortunatamente, conosciamo già la lunghezza di queste stringhe e possiamo calcolare il numero di stringhe che genereremo: è solo il prodotto del numero di mapping per ciascuna posizione.

Mentre è possibile return them in an array, preferisco utilizzare un callback per restituirli come li trovo.

#include <string.h> 
#include <stdlib.h> 
int each_combination( 
    char const * source, 
    char const * mappings[256], 
    int (*callback)(char const *, void *), 
    void * thunk 
) { 
    if (mappings == NULL || source == NULL || callback == NULL) 
    { 
    return -1; 
    } 
    else 
    { 
    size_t i; 
    int rv; 
    size_t num_mappings[256] = {0}; 
    size_t const source_len = strlen(source); 
    size_t * const counter = calloc(source_len, sizeof(size_t)); 
    char * const scratch = strdup(source); 

    if (scratch == NULL || counter == NULL) 
    { 
     rv = -1; 
     goto done; 
    } 

    /* cache the number of mappings for each char */ 
    for (i = 0; i < 256; i++) 
     num_mappings[i] = 1 + (mappings[i] ? strlen(mappings[i]) : 0); 

    /* pass each combination to the callback */ 
    do { 
     rv = callback(scratch, thunk); 
     if (rv != 0) goto done; 

     /* increment the counter */ 
     for (i = 0; i < source_len; i++) 
     { 
     counter[i]++; 
     if (counter[i] == num_mappings[(unsigned char) source[i]]) 
     { 
      /* carry to the next position */ 
      counter[i] = 0; 
      scratch[i] = source[i]; 
      continue; 
     } 
     /* use the next mapping for this character */ 
     scratch[i] = mappings[(unsigned char) source[i]][counter[i]-1]; 
     break; 
     } 
    } while(i < source_len); 

done: 
    if (scratch) free(scratch); 
    if (counter) free(counter); 
    return rv; 
    } 
} 
#include <stdio.h> 
int print_each(char const * s, void * name) 
{ 
    printf("%s:%s\n", (char const *) name, s); 
    return 0; 
} 
int main(int argc, char ** argv) 
{ 
    char const * mappings[256] = { NULL }; 
    mappings[(unsigned char) 'a'] = "eo"; 
    mappings[(unsigned char) 'b'] = "i"; 

    each_combination("abba", mappings, print_each, (void *) "abba"); 
    each_combination("baobab", mappings, print_each, (void *) "baobab"); 

    return 0; 
} 

Answer 4

C'è un collegamento all'archivio dei frammenti che lo fa, qui, Permute2.c. V'è un'altra variante della permutazione stringa (Credo che si potrebbe poi filtrare quelli che non sono nella mappa!) Vedi qui sul 'snippets' archivio ...

Spero che questo aiuti, i migliori saluti, Tom .

Answer 5

MODIFICA: Questo dovrebbe essere l'algo più veloce e più semplice possibile. Alcuni potrebbero discutere con lo stile o la portabilità; Penso che questo sia perfetto per una cosa di tipo embedded e ho già passato abbastanza tempo. Lascio l'originale qui sotto.

Questo utilizza un array per la mappatura. Il bit di segno viene utilizzato per indicare la fine di un ciclo di mappatura, pertanto il tipo di matrice deve essere maggiore del tipo mappato se si desidera utilizzare l'intervallo completo unsigned.

Genera stringhe 231 M/sec o ~ 9.5 cicli/stringa su Core2 2,2 GHz. Condizioni di prova e utilizzo come di seguito.

#include <iostream> 
using namespace std; 

int const alphabet_size = CHAR_MAX+1; 
typedef int map_t; // may be char or short, small performance penalty 
int const sign_bit = 1<< CHAR_BIT*sizeof(map_t)-1; 
typedef map_t cmap[ alphabet_size ]; 

void CreateMap(char *str, cmap &m) { 
    fill(m, m+sizeof(m)/sizeof(*m), 0); 
    char *str_end = strchr(str, 0) + 1; 
    str_end[-1] = ' '; // space-terminated strings 
    char prev = ' '; 
    for (char *pen = str; pen != str_end; ++ pen) { 
     if (* pen == ' ') { 
      m[ prev ] |= sign_bit; 
      prev = 0; 
     } 
     m[ * pen ] = * pen; 
     if (prev != ' ') swap(m[prev], m[ *pen ]); 
     prev = *pen; 
    } 
    for (int mx = 0; mx != sizeof(m)/sizeof(*m); ++ mx) { 
     if (m[mx] == 0) m[mx] = mx | sign_bit; 
    } 
} 

bool NextMapping(char *s, char *s_end, cmap &m) { 
    for (char *pen = s; pen != s_end; ++ pen) { 
     map_t oldc = *pen, newc = m[ oldc ]; 
     * pen = newc & sign_bit-1; 
     if (newc >= 0) return true; 
    } 
    return false; 
} 

int main(int argc, char **argv) { 
    uint64_t cnt = 0; 
    cmap m; 
    CreateMap(argv[1], m); 
    char *s = argv[2], *s_end = strchr(s, 0); 
    do { 
     ++ cnt; 
    } while (NextMapping(s, s_end, m)); 
    cerr << cnt; 
    return 0; 
} 

---

ORIGINALE:

Non più breve o robusto come mi piacerebbe, ma qui è già qualcosa.

• richiede che la stringa di input contiene sempre il primo in ordine alfabetico lettera di ogni sostituzione set
• Eseguire alla maptool 'aeo dgh bi' abbd
• uscita è in retromarcia-lessicografico ordine
• prestazioni di circa 22 cicli/corda (100M stringhe/sec a 2,2 GHz Core2)
  • ma la mia piattaforma sta cercando di essere intelligente con string s, rallentandolo
  • Se cambio in modo da utilizzare char* stringhe, invece, funziona a stringhe 142m/sec (~ 15,5 cicli/string)
• dovrebbe essere possibile andare più veloce utilizzando una tabella char[256] mappatura e un'altra char[256] specificare quale i personaggi terminano un ciclo.

La struttura di dati della mappa è una matrice di nodi collegati in elenchi circolari.

#include <iostream> 
#include <algorithm> 
using namespace std; 

enum { alphabet_size = UCHAR_MAX+1 }; 

struct MapNode { 
    MapNode *next; 
    char c; 
    bool last; 
    MapNode() : next(this), c(0), last(false) {} 
}; 

void CreateMap(string s, MapNode (&m)[ alphabet_size ]) { 
    MapNode *mprev = 0; 
    replace(s.begin(), s.end(), ' ', '\0'); 
    char *str = const_cast<char*>(s.c_str()), *str_end = str + s.size() + 1; 
    for (char *pen = str; pen != str_end; ++ pen) { 
     if (mprev == 0) sort(pen, pen + strlen(pen)); 
     if (* pen == 0) { 
      if (mprev) mprev->last = true; 
      mprev = 0; 
      continue; 
     } 
     MapNode &mnode = m[ * pen ]; 
     if (mprev) swap(mprev->next, mnode.next); // link node in 
     mnode.c = * pen; // tell it what char it is 
     mprev = &mnode; 
    } 
     // make it easier to tell that a node isn't in any map 
    for (MapNode *mptr = m; mptr != m + alphabet_size; ++ mptr) { 
     if (mptr->next == mptr) mptr->next = 0; 
    } 
} 

bool NextMapping(string &s, MapNode (&m)[ alphabet_size ]) { 
    for (string::iterator it = s.begin(); it != s.end(); ++ it) { 
     MapNode &mnode = m[ * it ]; 
     if (mnode.next) { 
      * it = mnode.next->c; 
      if (! mnode.last) return true; 
     } 
    } 
    return false; 
} 

int main(int argc, char **argv) { 
    MapNode m[ alphabet_size ]; 
    CreateMap(argv[1], m); 
    string s = argv[2]; 
    do { 
     cerr << s << endl; 
    } while (NextMapping(s, m)); 
return 0; 
} 

Answer 6

semplice, permute ricorsiva, con l'utilizzo di carta char [256]

char *map [256]; 

/* permute the ith char in s */ 
perm (char *s, int i) 
{ 
    if (!s) return; 

    /* terminating condition */ 
    if (s[i] == '\0') { 
     /* add "s" to a string array if we want to store the permutations */ 
     printf("%s\n", s); 
     return; 
    } 

    char c = s[i]; 
    char *m = map [c]; 
    // printf ("permuting at [%c]: %s\n", c, m); 
    int j=0; 
    /* do for the first char, then use map chars */ 
    do { 
     perm (s, i+1); 
     s[i] = m[j]; 
    } while (m[j++] != '\0'); 
    /* restore original char here, used for mapping */ 
    s[i] = c; 

    return; 
} 

int main() 
{ 
    /* map table initialization */ 
    map['a'] = "eo\0"; 
    map['b'] = "i\0"; 
    map['d'] = "gh\0"; 

    /* need modifyable sp, as we change chars in position, sp="abba" will not work! */ 
    char *sp = malloc (10); 
    strncpy (sp, "abba\0", 5); 

    perm (sp, 0); 
    return 0; 
}