CODEWITHSUNDEEP
c++performancealgorithmpermutation
Ali
Ali

Reputation: 5476

C++: Listing the permutations of a string

I would like to ask all my fellow programmers regarding only efficiency. I am currently solving problems that could be asked in job interviews and I've come across with the famous permutations of a string. The code I've written below might be the most common thing in programming history, however, I do not know it's status since I haven't checked for any solution.

Long story would the short the program I've coded below be a suitable solution? Or can it be made even more efficient. Asking because if I came across one day I would like to be sure that I've implement one of the best approaches for this problem.

#include <iostream>
using namespace std;

int fac(int num)
{
    int result=1;
    for(int i=1;i<=num;i++)
        result*=i;
    return result;
}

int main(int argc, const char * argv[])
{
    string str="abcd";
    int limit=fac(str.size());
    int mod=str.size();
    for(int i=0;i<limit;i++){
        swap(str[i%mod],str[(i+1)%mod]);
        cout<<str<<endl;
    }
    return 0;
}

Upvotes: 3

Views: 411

Answers (4)

btilly
btilly

Reputation: 46399

The answer to your question is NO. You should not worry about the efficiency of any proposed solution until you know that it works. And this one does not work.

The following demonstrates that fact.

ben-tillys-macbook-pro:ton btilly$ cat foo.cc
#include <iostream>
using namespace std;

int fac(int num)
{
    int result=1;
    for(int i=1;i<=num;i++)
        result*=i;
    return result;
}

int main(int argc, const char * argv[])
{
    string str="abcd";
    int limit=fac(str.size());
    int mod=str.size();
    for(int i=0;i<limit;i++){
        swap(str[i%mod],str[(i+1)%mod]);
        cout<<str<<endl;
    }
    return 0;
}
ben-tillys-macbook-pro:ton btilly$ g++ foo.cc
ben-tillys-macbook-pro:ton btilly$ ./a.out | wc
      24      24     120
ben-tillys-macbook-pro:ton btilly$ ./a.out | sort -u | wc
      12      12      60
ben-tillys-macbook-pro:ton btilly$ ./a.out | grep bdc
ben-tillys-macbook-pro:ton btilly$

Upvotes: 0

Smi
Smi

Reputation: 14316

You could use recursion:

#include <iostream>
#include <tchar.h>
#include <string>

using namespace std;

void swap(char &first, char &second) {
    char tmp = first;
    first = second;
    second = tmp;
}

void enumPermutations(string &p, int m)
{
    if (m == p.size() - 1)
        cout << p << endl;
    else
        for (int j = m; j < p.size(); j++) {
            swap(p[j], p[m]);
            enumPermutations(p, m+1);
            swap(p[j], p[m]);
        }
}

int _tmain(int argc, _TCHAR* argv[])
{
    string str = "abcd";
    enumPermutations(str, 0);
    getchar();
    return 0;
}

(compiled and tested in Visual Studio).

Upvotes: 1

Ali
Ali

Reputation: 5476

I've figured out the solution by using a std::map. Don't think it is that inefficient;

#include <iostream>
#include <map>
#include <vector>
using namespace std;

int fac(int num)
{
    int result=1;
    for(int i=1;i<=num;i++)
        result*=i;
    return result;
}
int main(int argc, const char * argv[])
{
    string str="aabb";
    int limit=fac(str.size());
    int mod=str.size();
    std::map<string,bool>T;
    vector<string>permutations;
    for(int i=0;i<limit;i++){
        if(T[str]==0){
            permutations.push_back(str);
            T[str]=1;
        }
        swap(str[i%mod],str[(i+1)%mod]);
    }
    for(int i=0;i<permutations.size();i++)
        cout<<permutations[i]<<endl;
    return 0;
}

Upvotes: 0

djechlin
djechlin

Reputation: 60758

Doesn't handle duplicated letters within the string, e.g. "aaabbb".

Upvotes: 1

Related Questions