cout permutation of three or more string

Question

suppose I have been given strings "abc", "def" and "ghi", I want to generate all the possible combination of word generated by picking from these strings. for eg for "abc", "def" and "ghi"

we should get

"adg","adh","adi","aeg","aeh","aei","afg","afh","afi", "bdg","bdh","bdi","beg","beh","bei","bfg","bfh","bfi", "cdg","cdh","cdi","ceg","ceh","cei","cfg","cfh","cfi"

How to Do it.

my attampt...

        vector<string> wordset;
        
        for(int i = 0; i < digits.size(); i++ )
        {
            wordset.push_back( latters[digits[i] - '0'] );
        }

                   
        for(int i = 0; i < wordset.size()-2; i++ )
        {
            string word = wordset[i];
            for(int j = 0; j < word.size(); j++ )
            {
                string combn = "";
                combn += word[j];
                                
                for(int k = 0; k < wordset[i+1].size(); k++ )
                {
                    combn += wordset[i+1][k];

                    for(int l = 0; l < wordset[i+2].size(); l++ )
                    {
                        combn += wordset[i+2][l];

                        ans.push_back(combn);
                        combn = "";
                        combn += word[j];
                        combn += wordset[i+1][k];

                    }

                }
            }
        }

If the want the size of `wordset` to be variable, recursion would help a lot... — Serge Ballesta, Oct 28 '21 at 07:27
It is not permutation but [cartesian product](https://en.wikipedia.org/wiki/Cartesian_product). — Jarod42, Oct 28 '21 at 08:19

score 0 · Accepted Answer · answered Oct 28 '21 at 08:02

This is one example where recursion allows simpler code: you just have to combine all characters from the first word with the permutations of the other ones.

In C++ it could be:

#include <vector>
#include <string>

using std::vector;
using std::string;

// using an array will allow to simply process the end of the array
vector<string> permuts(const string* arr, size_t sz) {
    vector<string> ret;
    switch (sz) {
    case 1:   // one single word: return its individual chars as strings
        for (char c : arr[0]) {
            string str(1, c);
            ret.push_back(str);
        }
    case 0:   // empty array gives an empty vector
        return ret;
    default:
        ;
    }
    // combine chars from first word with permuts of others
    vector<string> tmp = permuts(arr + 1, sz - 1);
    for (char c : arr[0]) {
        for (const string& str : tmp) {
            string str2 = string(1, c) + str;
            ret.push_back(str2);
        }
    }
    return ret;
}

// the version using a vector just delegates to the one using an array
vector<string> permuts(const vector<string>& wordset) {
    return permuts(wordset.data(), wordset.size());
}

`permuts` can be renamed `cartesian_product`. – Jarod42 Oct 28 '21 at 08:22 — Jarod42, Oct 28 '21 at 08:22

cout permutation of three or more string

1 Answers1