Finished permutation code.

1 files changed, 45 insertions, 3 deletions

diff --git a/permute.cpp b/permute.cpp
index 561f9da..741455f 100644
--- a/permute.cpp
+++ b/permute.cpp
@@ -3,20 +3,62 @@
 #include <iostream>
 #include <cstring>
 #include <string>
+#include <vector>
+#include <algorithm>
 
 using namespace std;
 
-void do_permute(const char* s, size_t, string& buf)
+struct string_printer : unary_function<void, string>
 {
+    void operator()(const string& s)
+    {
+        cout << s << endl;
+    }
+};
+
+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;
+        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);
+    }
 }
 
 void permute(const char* s, size_t n)
 {
+    vector<string> perms;
     for (size_t i = 0; i < n; ++i)
     {
-        string buf;
-        buf.push_back(s[i]);
+        string remain, perm;
+        for (size_t j = 0; j < n; ++j)
+        {
+            if (i == j)
+                perm.push_back(s[j]);
+            else
+                remain.push_back(s[j]);
+        }
+        do_permute(remain, perm, perms);
+        perm.resize(perm.size()-1);
     }
+
+    cout << "number of permutations: " << perms.size() << endl;
+    for_each(perms.begin(), perms.end(), string_printer());
 }
 
 int main(int argc, char** argv)