add permutaion sequence

kuring · kuring · commit 35ef94269a00 · 2015-04-26T12:47:31.000+08:00
diff --git a/README.md b/README.md
@@ -123,7 +123,7 @@ LeetCode C++ Solutions
 |[Unique Paths II](https://oj.leetcode.com/problems/unique-paths-ii/)| [C++](./src/uniquePaths/uniquePaths.II.cpp)|Medium|yes|
 |[Unique Paths](https://oj.leetcode.com/problems/unique-paths/)| [C++](./src/uniquePaths/uniquePaths.cpp)|Medium|yes|
 |[Rotate List](https://oj.leetcode.com/problems/rotate-list/)| [C++](./src/rotateList/rotateList.cpp)|Medium|yes|
-|[Permutation Sequence](https://oj.leetcode.com/problems/permutation-sequence/)| [C++](./src/permutationSequence/permutationSequence.cpp)|Medium|
+|[Permutation Sequence](https://oj.leetcode.com/problems/permutation-sequence/)| [C++](./src/permutationSequence/permutationSequence.cpp)|Medium|yes|
 |[Spiral Matrix II](https://oj.leetcode.com/problems/spiral-matrix-ii/)| [C++](./src/spiralMatrix/spiralMatrix.II.cpp)|Medium|yes|
 |[Length of Last Word](https://oj.leetcode.com/problems/length-of-last-word/)| [C++](./src/lengthOfLastWord/lengthOfLastWord.cpp)|Easy|yes|
 |[Insert Interval](https://oj.leetcode.com/problems/insert-interval/)| [C++](./src/insertInterval/insertInterval.cpp)|Hard|
diff --git a/src/permutationSequence/permutation_sequence.cpp b/src/permutationSequence/permutation_sequence.cpp
@@ -0,0 +1,55 @@
+#include <string>
+#include <iostream>
+#include <vector>
+
+using namespace std;
+
+string getPermutation(int n, int k, string &str)
+{
+    cout << "n=" << n << " k=" << k << " str=" << str << endl;
+    if (k == 1 || str.length() == 1)
+    {
+        return str;
+    }
+    int number = 1;
+    for (int i=1; i<n; i++)
+    {
+        number *= i;
+    }
+    string result;
+    int site = (k - 1) / number;
+    result += str[site];
+    str.erase(site, 1);
+
+    if (site != 0)
+    {
+        k = (k - 1) % number + 1;
+    }
+    result += getPermutation(n - 1, k, str);
+    return result;
+}
+
+/**
+ * 采用递归方式实现，需要找到规律
+ * 貌似该种算法就是康托编码
+ */
+string getPermutation(int n, int k)
+{
+    string str;
+    if (n <= 0 && k < 0)
+    {
+        return str;
+    }
+    for (int i=1; i<=n; i++)
+    {
+        str += (char)(i + '0');
+    }
+
+    return getPermutation(n, k, str);
+}
+
+int main()
+{
+    cout << getPermutation(4, 7) << endl;
+    return 1;
+}
