这是一个让我困惑（解决方案）的问题：
给定一个字符串 S，应用字符映射 Cm = {a=(m,o,p),d=(q,u),...} 并使用 C 或 C++ 打印出所有可能的组合。
该字符串可以是任意长度，字符映射的数量也会有所不同，并且不会有映射到另一个映射的映射（从而避免循环依赖）。
例如：字符串 abba 与映射 a=(e,o), d=(g,h), b=(i) 将打印：
abba,ebba,obba,abbe,abbo,ebbe,ebbo,obbe,obbo,aiba,aiia,abia,eiba,eiia,......
肯定可以实现，不是很难... 但这会产生许多字符串。
首先要注意的是你事先知道它将生成多少个字符串，因此很容易进行一些合理性检查 :)
其次，它似乎可以通过递归解决（就像许多遍历问题一样）。
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");
}
下面是输出结果：
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
是的，这段话比较长，但其中有很多与计算无关的内容（初始化、检查、打印等）。核心方法是next，它实现了递归。
编辑：这应该是最快和最简单的算法。有些人可能会对样式或可移植性提出异议；我认为这非常适合嵌入式设备，并且我已经花了足够长的时间在上面了。我将原始内容保留如下。
这使用数组进行映射。符号位用于指示映射周期的结束，因此如果要使用完整的unsigned范围，则数组类型必须大于映射类型。
在2.2GHz Core2上生成231M个字符串/秒或~9.5个周期/字符串。测试条件和用法如下。
#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;
}
原文：
不是我想要的那么短或者强大，但这里有些东西。
maptool 'aeo dgh bi' abbdstring 进行优化，从而使其变慢char* 字符串，它将以142M个字符串/秒的速度运行（约15.5个周期/字符串）char[256]映射表和另一个指定哪些字符结束一个循环的char[256]来更快地进行操作映射数据结构是一个由节点组成的循环链表数组。
#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;
}
'a' => 'e', 'o'
'b' => 'i'
对于输入字符串"abba"，我们需要一个包含四个元素的数组来表示它们的索引：
[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"
#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;
}
malloc 和 free 总是让我不舒服，特别是当它们没有成对出现在同一个方法中时。此外（但这在英语用户中很常见），有些 char 可能具有负值（用于扩展 ASCII 中的重音字符）。 - Matthieu M.使用字符映射表[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;
}
你需要做的是深度优先搜索（DFS）或者其他遍历有向无环图（DAWG）的算法。我马上会发布一些代码。
这里有一个链接到代码片段存档的地方，可以实现这个功能，链接在这里 Permute2.c。还有另一种字符串排列的变体（我猜你可以过滤掉那些不在映射中的！），请参见 'snippets' 存档...
希望这能帮到你， 最好的祝福， 汤姆。