how to obtain all permutation combination of two string?

Question

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

look at this exapmle:

Input= "abc", "mn"

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

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

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

Answer 1

The(My) code works: http://ideone.com/IYYVZY

It just use C++11. for C++03 see http://ideone.com/ZHXSkt

You have to change the for range loop

for (int e : v) -> for (std::size_t i = 0, size = v.size(); i != size; ++i) { int e = v[i]; ..

Answer 2

I am going to build upon the approach from anatolyg to provide a solution for n input strings, lets say for the sake of simplicity n <=10 (see where I am going?). Notice how the relative ordering for one string never change? This is the base of the algorithm

step1 : You take your string in a array or vector or whatever. for each string you assign a symbol of size one, like character 0 for the first one, 1 for the second, till 9.

steps2 : you have a function which convert the inputs to a single string (or better a vector), where each character is from the original string. In your case, the function is :

 f("abc", "mn") => "00011"

steps3 : you enumerate the permutations over the resulting string, in this case "00011". You were already in the right track with std::next_permutation()

steps4 : you iterate on each of the resulting string and use its symbol as a mask. something like

void mergewithmask(std::string& target, std::string& input, char mask )
{
 int i = 0;//target index
 int j = 0;//input index
 for(i = 0; i < target.size(); i++)
 {
   if(target[i] == mask){
      target[i] = input[j];
      j++;
   }
 }
}

so

mergewithmask("01001","abc", `0`) => "a1bc1"
mergewithmask("a1bc1","mn", `1`) => "ambcn"

In order of this approach to work you need to use symbols which don't collide with your initial inputs. Using a vector of negative numbers for instance will guarantee not colliding with a char array and a unlimited amount of input strings...

Answer 3

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

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.

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

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

Then you can use this vector with your print_towstring function.

Answer 4

I think you can do it recursively. Basically at each step you create two branches: one where you add to your string a letter from the right hand side string, and another branch where you add the first letter from the left hand side string:

    void AddNext(
      std::string const& left,
      std::string const& right,
      std::string const& current,
      std::vector< std::string >& results)
    {
      if (left.empty())
      {
        current.append(right);
        results.push_back(current);
        return;
      }
      else if (right.empty())
      {
         current.append(left);
         results.push_back(current)
         return;
      }
      else
      {
        AddNext(left, right.substr(1, right.size() -1), current + std::string(1, right[0]), results);
        AddNext(left.substr(1, left.size() -1), right, current + std::string(1, left[0]), results);
      }
}