c++ - C++: 文字列の順列の一覧表示

Question

同僚のプログラマー全員に、効率だけについて質問したいと思います。私は現在、就職の面接で尋ねられる可能性のある問題を解決しており、有名なstringの順列に出くわしました。以下に書いたコードは、プログラミングの歴史の中で最も一般的なものかもしれませんが、解決策を確認していないため、ステータスがわかりません。

長い話ですが、私が以下にコーディングした短いプログラムは適切な解決策でしょうか? または、さらに効率的にすることはできますか。いつか出くわしたら、この問題に対する最良のアプローチの1つを実装したことを確認したいので、尋ねます。

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

Answer 1

再帰を使用できます：

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

(Visual Studio でコンパイルおよびテスト済み)。

Answer 2

文字列内で重複する文字を処理しません"aaabbb"。

Answer 3

あなたの質問に対する答えはNOです。提案されたソリューションが機能することがわかるまでは、その効率について心配する必要はありません。そして、これは機能しません。

以下はその事実を示しています。

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$ 

Answer 4

を使用して解決策を見つけましたstd::map。それが非効率だとは思わないでください。

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