我有两个词，我想获得这些词的组合的所有排列。性格从每个字符串的相对顺序必须是preserved

I have two words, and I want obtain all permutation of the combination of these words. The relative order of character from each string has to be preserved

看看这个exapmle：

look at this exapmle:

Input= "abc", "mn"

Output= "abcmn", "abmnc", "amnbc", "mnabc", "mabcn", "manbc", "mabnc", "ambnc", "ambcn", "abmcn"

我搜索stackoverflow.com，并达到以下code，但它不工作！

I search stackoverflow.com, and achieve the following code, but it doesn't work!

void print_towstring(const std::vector<int>& v, const std::string& s1, const std::string& s2)
{
    std::size_t i1 = 0;
    std::size_t i2 = 0;

    for (int i : v) {
        std::cout << ((i == 0) ? s1[i1++] : s2[i2++]);
    }
    std::cout << std::endl;
}

void towstring(const std::string& s1, const std::string& s2)
{
    std::vector<int> v(s1.size(), 0);

    v.insert(v.end(), s2.size(), 1);
    do
    {
        print_towstring(v, s1, s2);
    } while (std::next_permutation(v.begin(), v.end()));
}

int main(int argc, char *argv[])
{
    towstring("abc", "mn");
    return 0;
}

我

怎么能写排列组合算法的C ++？

how can I write algorithm of permutation combination in c++ ?

推荐答案

看来你可以重新present了排列组合，由一系列的0和1的，其中每个数字说明从字符串拿下性格，像这样的：

It seems that you can represent a "permutation combination" by a sequence of 0's and 1's, where each number tells from which string to take next character, like this:

00101 - means abmcn

所以，你现在有能力生产所有这样的字符串为0的给定数目和1的（3和2在你的例子），一个给定的数字。要做到这一点，我想，最简单的办法是遍历的0和1的所有组合，并扔掉那些不为1的所需要的数量。

So, you now have to produce all such strings that have a given number of 0's and a given number of 1's (3 and 2 in your example). To do it, I guess, the easiest would be to iterate over all combinations of 0's and 1's, and throw away those that don't have the needed number of 1's.

我喜欢重新present比特串由多个，从最低位显著，例如，启动00101对应

I like to represent a string of bits by a number, starting from the least significant bit, e.g. 00101 corresponds to

0 * 2^0 +
0 * 2^1 +
1 * 2^2 +
0 * 2^3 +
1 * 2^4 = 20

（警告：这将只在有限的字符串大小 - 高达32 - 或任何位数 INT 已对长字符串，执行可以适应到64位，但它是不值得的，因为这将是太慢了呢）

(warning: this will only work for a limited string size - up to 32 - or whatever number of bits int has. For longer strings, the implementation could be adapted to 64 bits, but it's not worth it, because it would be too slow anyway)

要获得一个给定的位，从这样一个数字：

To get a given bit from such a number:

int GetBit(int n, int b)
{
    return (n >> b) & 1;
}

要这样的数字转换成一个向量：

To convert such a number to a vector:

void ConvertNumberToVector(int n, std::vector<int>& v)
{
    for (int b = 0; b < v.size(); ++b)
        v[b] = GetBit(n, b);
}

然后就可以用这个载体与你的 print_towstring 的功能。