# My solution using adjacent elements swap

• An efficient solution generating unordered permutations, with no recursion, no much additional memory cost, O(1) time complexity for each new permutation (excluding the time cost for copying). Each step swap a pair of adjacent elements and generate a new permutation, with non-repetitive guarantee.

Though the code maybe a little confusing :P

``````// generate permutations by swap a pair of adjacent elements at one time
class Solution {
public:
vector<vector<int> > permute(vector<int> &num) {
vector<vector<int> > permutations;
vector<int> elem_permutation (num.begin(), num.end());
vector<int> index_permutation;
vector<int> position;
// direction_flag[i] = 0, 1, 2, 3 means the ith element is moving right, moving left, left most, right most
vector<int> direction_flag;
int permutation_num;
int cur_moving;
int len = num.size();
if (len > 0)
{
permutations.push_back (elem_permutation);
for (int i = 0; i < len; i++)
{
index_permutation.push_back (i);
position.push_back (i);
direction_flag.push_back (0);
}
permutation_num = 1;
for (int i = 2; i <= len; i++)
permutation_num *= i;
cur_moving = 0;
for (int i = 1; i < permutation_num; i++)
{
if (direction_flag[cur_moving] == 0)
{
swap (elem_permutation[position[cur_moving]], elem_permutation[position[cur_moving] + 1]);
swap (index_permutation[position[cur_moving]], index_permutation[position[cur_moving] + 1]);
position[index_permutation[position[cur_moving]++]]--;
if (position[cur_moving] == len - 1 || cur_moving > index_permutation[position[cur_moving] + 1])
direction_flag[cur_moving] = 3;
}
else
{
swap (elem_permutation[position[cur_moving]], elem_permutation[position[cur_moving] - 1]);
swap (index_permutation[position[cur_moving]], index_permutation[position[cur_moving] - 1]);
position[index_permutation[position[cur_moving]--]]++;
if (position[cur_moving] == 0 || cur_moving > index_permutation[position[cur_moving] - 1])
direction_flag[cur_moving] = 2;
}
if (cur_moving > 0)
{
for (int j = 0; j < cur_moving; j++)
direction_flag[j] -= 2;
cur_moving = 0;
}
else
{
for (int j = 0; ; j++)
if (direction_flag[j] < 2 || j == len - 1)
{
cur_moving = j;
break;
}
}
permutations.push_back (elem_permutation);
}
}
return permutations;
}
};``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.