Correct solution doesn't produce a lexicographical ordering


  • 0
    P

    I came up with this code which got accepted. Problem is that this doesn't produce a lexicographical permutation.

    
    void perm(vector<int> &nums, vector<int> &row,vector<vector<int> > &result, int k) {
        if (k == nums.size()-1) {
            row = nums;
            result.push_back(row);
            return ;
        }
        
        for(int i = k; i<nums.size();++i) {
            swap(nums[i],nums[k]);
            perm(nums,row,result,k+1);
            swap(nums[i],nums[k]);
        }
    }
    
    class Solution {
    public:
        vector<vector<int>> permute(vector<int>& nums) {
            
            vector<int> row;
            vector<vector<int> > result;
            perm(nums,row,result,0);
            return result;
        }
    };
    
    

    I checked the top solution and it is very similar to what I had done and executed that. Even that solution doesn't produce a correct lexicographical order.

    Question is how can this code be modified if lexicographical ordering is a must?

    Edit:

    By lexicographical ordering, I mean my output is currently producing this:

    [[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,2,1],[3,1,2]]
    

    However, the correct ordering should be

    [[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]
    

    Notice the 312 vs 321 at the end. It becomes more apparent which the input size is increased.


  • 1
    Z

    It must be related to the use of std::swap() which modify the order of nums

    To avoid swap:

    #include <vector>
    class Solution {
    public:
        void _permute(std::vector<vector<int>> &ret, std::vector<int> &per, std::vector<int> &remain, int len) {
            if (per.size() == len) {
                ret.push_back(per);
                return ;
            }
            for (int i = 0; i < remain.size(); ++i) {
                per.push_back(remain[i]);
                remain.erase(remain.begin() + i);
                _permute(ret, per, remain, len);
                remain.insert(remain.begin() + i, per.back());
                per.pop_back();
            }
        }
    
        vector<vector<int>> permute(vector<int>& nums) {
            std::vector<vector<int>> ret;
            std::vector<int> per;
            std::vector<int> remain = nums;
            int len = nums.size();
            _permute(ret, per, remain, len);
            return ret;
        }
    };
    

Log in to reply
 

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