My solution using adjacent elements swap


  • 2
    T

    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;
        }
    };

Log in to reply
 

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