String concatenation is BAD!!!!
So here was tonight’s problem, from our friend LeetCode: https://leetcode.com/problems/permutation-sequence/description/
The set [1,2,3,…,n] contains a total of n!
unique permutations.
By listing and labeling all of the
permutations in order,
We get the following sequence (ie, for n = 3):
We get the following sequence (ie, for n = 3):
- "123"
- "132"
- "213"
- "231"
- "312"
- "321"
Given n and k,
return the kth permutation sequence.
Note: Given n will be between 1 and 9 inclusive.
It is an interesting one because it asks precisely for the
kth permutation sequence. I’m sure there must be a clever way to generate the
kth one in O(1) but I decided to generate them all (given the small n) until we
get to the kth one. Here was my first implementation: a recursive depth-first
search without pruning until we get to the kth sequence:
public class Solution
{
public
string GetPermutation(int n, int k)
{
string
set = "";
for
(int i = 1; i <= n; i++)
set
+= i.ToString();
int
index = 0;
string
result = "";
bool[]
used = new bool[n];
_GetPermutation("",
set, ref used, ref index, k, ref result);
return
result;
}
private
bool _GetPermutation(string current,
string set,
ref bool[] used,
ref int index,
int k,
ref string result)
{
if
(current.Length == set.Length)
{
index++;
if
(index == k)
{
result
= current;
return
true;
}
return
false;
}
for
(int i = 0; i < set.Length; i++)
{
if
(!used[i])
{
used[i]
= true;
if
(_GetPermutation(current +
set[i].ToString(), set, ref used, ref index, k, ref result)) return
true;
used[i]
= false;
}
}
return
false;
}
}
It works, but when I submitted I got the infamous error: Time Limit Exceeded. I had a hunch that
the problem was simply in the highlighted line: the code is suffering from an insane number of
string concatenations, probably happening tens of thousands of times. Now there
will be times when such situation will be near inevitable but certainly it is
not the case here. Given that the length of our string never surpasses 9
characters, we can easily change that string to a fixed array, do all the manipulation/indexation
with the array, and only leave the string concatenation for the very last
operation. It did the trick. Barely, I must say. Passing code is below. Thanks,
Marcelo.
public
class Solution
{
public
string GetPermutation(int n, int k)
{
string
set = "";
for
(int i = 1; i <= n; i++)
set
+= i.ToString();
int
index = 0;
string
result = "";
bool[]
used = new bool[n];
char[]
current = new char[n];
int
currentIndex = 0;
_GetPermutation(current,
ref currentIndex, set, ref used, ref index, k, ref result);
return
result;
}
private
bool _GetPermutation(char[] current,
ref int currentIndex,
string set,
ref bool[] used,
ref int index,
int k,
ref string result)
{
if
(currentIndex == set.Length)
{
index++;
if
(index == k)
{
result
= "";
foreach
(char c in current)
result
+= c.ToString();
return
true;
}
return
false;
}
for
(int i = 0; i < set.Length; i++)
{
if
(!used[i])
{
used[i]
= true;
current[currentIndex++] = set[i];
if
(_GetPermutation(current, ref currentIndex, set, ref used, ref index, k, ref
result)) return true;
currentIndex--;
used[i]
= false;
}
}
return
false;
}
}
So true, Marcelo! :) Concatenation is one of the first enemies that functional programmers discover, since beginners usually implement recursive list traversal using concatenation, which results in a very unfortunate O(N^2) time complexity. On top of expensive copying involved in concatenation, allocations are even a bigger problem, especially for managed languages, since it causes garbage collector pressure.
ReplyDeleteSince I'm somewhat sleepy right now, I decided to cheat and use a built-in C++ function to solve this problem (code is reuse is good, isn't it? :)
class Solution {
public:
string getPermutation(int n, int k) {
string label(n, '\0');
for (int i = 1; i <= n; ++i) label[i-1] = '0' + i;
for (int i = 1; i < k; ++i) next_permutation(label.begin(), label.end());
return label;
}
};
Thank you!
Taras
Sooo cooool!!! Next_permutation: very nice! https://stackoverflow.com/questions/11483060/stdnext-permutation-implementation-explanation
ReplyDeleteHaha, C++ is perfect for cheaters like me :D
DeleteI really appreciate your professional approach.These are pieces of very useful information that will be of great use for me in future.
ReplyDeleteซอมบี้