permute.cpp


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58


#include <cstdlib>
#include <iostream>
#include <cstring>
#include <string>
#include <vector>
#include <algorithm>
#include <iterator>

using namespace std;

void do_permute(const string& pool, string& perm, vector<string>& perms)
{
    if (pool.empty())
    {
        perms.push_back(perm);
        return;
    }

    size_t n = pool.size();
    for (size_t i = 0; i < n; ++i)
    {
        string tmp;
        tmp.reserve(n-1);
        for (size_t j = 0; j < n; ++j)
        {
            if (i == j)
                perm.push_back(pool[j]);
            else
                tmp.push_back(pool[j]);
        }
        do_permute(tmp, perm, perms);
        perm.resize(perm.size()-1); // pop back one character.
    }
}

void permute(const string& pool)
{
    vector<string> perms;
    string perm;
    perm.reserve(pool.size());
    do_permute(pool, perm, perms);

    cout << "number of permutations: " << perms.size() << endl;
    copy(perms.begin(), perms.end(), ostream_iterator<string>(cout, "\n"));
}

int main(int argc, char** argv)
{
    if (argc <= 1)
        return EXIT_FAILURE;

    size_t n = strlen(argv[1]);
    cout << "input string: " << argv[1] << " (len = " << n << ")" << endl;
    permute(string(argv[1],n));

    return EXIT_SUCCESS;
}