String và lập bản đồ nhân vật câu hỏi cho ra của guru có

Question

Dưới đây là một vấn đề thats đã cho tôi bối rối (giải pháp khôn ngoan):

Cho một str S, áp dụng ánh xạ nhân vật Cm = {a=(m,o,p),d=(q,u),...} và in ra tất cả các kết hợp có thể sử dụng C hoặc C++.

Chuỗi có thể dài bất kỳ và số ánh xạ ký tự thay đổi và sẽ không có ánh xạ ánh xạ tới bản đồ khác (do đó tránh phụ thuộc vòng tròn).

Ví dụ: string abba với ánh xạ a=(e,o), d=(g,h), b=(i) sẽ in:

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

Answer 1

Chắc chắn có thể, không thực sự khó khăn ... nhưng điều này sẽ tạo ra nhiều chuỗi chắc chắn.

Điều đầu tiên cần nhận xét là bạn biết có bao nhiêu chuỗi nó sẽ tạo ra trước đó, vì vậy nó dễ dàng để làm một số kiểm tra sanity :)

Thứ hai: nó như một giải pháp đệ quy có vẻ sẽ dễ dàng (như nhiều vấn đề về giao thông).

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"); 
} 

Và đây là kết quả:

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 

Yeah, khá dài, nhưng có rất nhiều mà không tham gia trực tiếp vào việc tính toán (khởi tạo, kiểm tra, in ấn). Các phương pháp cốt lõi là next thực hiện đệ quy.

Answer 2

Bạn có thực chất muốn làm một tìm kiếm theo chiều sâu (DFS) hoặc bất kỳ traversal khác xuống một đồ thị từ acyclic đạo (Dawg). Tôi sẽ sớm đăng một số mã.

Answer 3

Cách tôi sẽ đi về việc này là tạo một mảng các chỉ mục có độ dài bằng với chuỗi, tất cả được khởi tạo ở mức 0. Sau đó chúng tôi xử lý mảng chỉ mục này làm bộ đếm để liệt kê tất cả các ánh xạ có thể có của chuỗi nguồn của chúng tôi. Một chỉ mục 0 ánh xạ vị trí đó trong chuỗi tới ánh xạ đầu tiên cho ký tự đó, từ 1 đến giây, vv Chúng ta có thể duyệt qua chúng theo thứ tự bằng cách tăng chỉ số cuối cùng trong mảng, chuyển sang vị trí tiếp theo khi chúng ta đạt đến số lượng ánh xạ tối đa cho vị trí đó.

Để sử dụng ví dụ của bạn, chúng tôi có các ánh xạ

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

Với chuỗi đầu vào "abba", chúng ta cần một mảng Bốn yếu tố cho chỉ số của chúng tôi:

[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" 

Trước khi chúng ta bắt đầu tạo những chuỗi, chúng ta sẽ cần một nơi nào đó để lưu trữ chúng, trong C, có nghĩa là chúng tôi đang sẽ phải cấp phát bộ nhớ. May mắn thay, chúng ta biết độ dài của các chuỗi này và chúng ta có thể tìm ra số lượng các chuỗi chúng ta sẽ tạo ra - nó chỉ là sản phẩm của số ánh xạ cho mỗi vị trí.

Trong khi bạn có thể return them in an array, tôi thích sử dụng gọi lại để trả lại khi tôi tìm thấy chúng.

#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ó một liên kết đến kho lưu trữ đoạn mã, tại đây, Permute2.c. Có một biến thể của hoán vị chuỗi (tôi đoán thì bạn có thể lọc ra những người mà không có trong bản đồ!) Xem ở đây trên 'snippets' lưu trữ ...

Hope this helps, Trân trọng, Tom .

Answer 5

EDIT: Đây sẽ là bản ngã nhanh nhất và đơn giản nhất có thể. Một số có thể tranh luận với phong cách hoặc tính di động; Tôi nghĩ rằng điều này là hoàn hảo cho một điều kiểu nhúng và tôi đã dành đủ lâu trên nó rồi. Tôi để nguyên bản gốc bên dưới.

Điều này sử dụng mảng để lập bản đồ. Bit dấu được sử dụng để cho biết kết thúc của một chu trình ánh xạ, do đó, loại mảng phải lớn hơn loại ánh xạ nếu bạn muốn sử dụng phạm vi unsigned đầy đủ.

Tạo 231M chuỗi/giây hoặc ~ 9.5 chu kỳ/chuỗi trên Core2 2.2GHz. Kiểm tra điều kiện và cách sử dụng như dưới đây.

#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; 
} 

---

ORIGINAL:

Không càng ngắn hoặc mạnh mẽ như tôi muốn, nhưng đây là một cái gì đó.

• Đòi hỏi rằng chuỗi đầu vào luôn chứa chữ theo thứ tự abc đầu tiên trong mỗi thay thế thiết
• Execute a la maptool 'aeo dgh bi' abbd
• Output là ngược lại-hoặc null để Performance
• khoảng 22 chu kỳ/string (100M chuỗi/giây tại 2,2 GHz Core2)
  • NHƯNG nền tảng của tôi đang cố gắng thông minh với string s, làm chậm nó xuống
  • Nếu tôi thay đổi nó để sử dụng char* chuỗi thay vào đó, nó chạy ở chuỗi 142m/giây (~ 15,5 vòng/chuỗi)
• nên có thể đi nhanh hơn bằng cách sử dụng bảng char[256] lập bản đồ và một char[256] đó nêu rõ ký tự kết thúc một chu kỳ.

Cấu trúc dữ liệu bản đồ là một mảng các nút được liên kết trong danh sách vòng tròn.

#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

đơn giản, hoán đệ quy, với việc sử dụng char bản đồ [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; 
}