LIKE CODING: Permutation

Showing posts with label Permutation. Show all posts

Friday, August 7, 2015

MJ [2]

Questions: Similar to LeetCode Permutation Sequence [1] except the numbers in nums are not unique. In Test, there are 4 numbers whose permutations are in increasing order, find the sequence number (1-based) of one of its permutation in the sequence. Eg., if nums=[2 1 2 3] it should return 4; if nums=[3 1 2 2] it should return 10.

Test:
1 2 2 3---1
1 2 3 2---2
1 3 2 2---3
2 1 2 3---4
2 1 3 2---5
2 2 1 3---6
2 2 3 1---7
2 3 1 2---8
2 3 2 1---9
3 1 2 2---10
3 2 1 2---11
3 2 2 1---12

============ =====================

Ref
[1] https://leetcode.com/problems/permutation-sequence/
[2] http://www.mitbbs.com/article_t/JobHunting/33021689.html
[3] http://www.mitbbs.com/article_t1/JobHunting/32952623_0_1.html
Zenefits MJ, replace numbers with chars.

Tuesday, March 31, 2015

LeetCode [31] Next Permutation

Implement next permutation, which rearranges numbers into the lexicographically next greater permutation of numbers.

If such arrangement is not possible, it must rearrange it as the lowest possible order (ie, sorted in ascending order).

The replacement must be in-place and use only constant extra memory.

Here are some examples. Inputs are in the left-hand column and its corresponding outputs are in the right-hand column.

1,2,3 → 1,3,2
3,2,1 → 1,2,3
1,1,5 → 1,5,1

class Solution {
public:
    void nextPermutation(vector<int>& nums) {
        int n = nums.size();
        if(n<=1) return;

        //find the first decreasing position from the end;
        int i=n-2;
        while(i>=0 && nums[i]>=nums[i+1]) i--;
        
        //this is the greatest number. return the smallest number;
        if(i<0)
        {
            sort(nums.begin(), nums.end());
            return;
        }

        //find the smallest number (from the end) greater than nums[i]
        int j=n-1;
        while(j>i && nums[j]<=nums[i]) j--;
        swap(nums[i], nums[j]);
        sort(nums.begin()+i+1, nums.end());
    }
};

class Solution {
    public void nextPermutation(int[] nums) {
        int n = nums.length;

        int i = n-2;
        for(; i>=0; --i){
            if(nums[i]<nums[i+1]) break;
        }
        
        if(i<0){
            Arrays.sort(nums);
            return;
        }
        
        int j = n-1;
        for(; j>i; --j){
            if(nums[j]>nums[i]) break;
        }
        
        //swap i and j
        int t = nums[i];
        nums[i] = nums[j];
        nums[j] = t;
        Arrays.sort(nums,i+1,n);
    }
}

Wednesday, February 25, 2015

LeetCode [47] Permutations II

47. Permutations II

Medium

Given a collection of numbers, nums, that might contain duplicates, return all possible unique permutations in any order.

Example 1:

Input: nums = [1,1,2]
Output:
[[1,1,2],
 [1,2,1],
 [2,1,1]]

Example 2:

Input: nums = [1,2,3]
Output: [[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]

Constraints:

1 <= nums.length <= 8
-10 <= nums[i] <= 10

class Solution {
public:
    vector<vector<int>> permuteUnique(vector<int>& nums) {
        vector<vector<int>> ret;
        sort(nums.begin(), nums.end());
        bt(nums, ret, 0, nums.size());
        return ret;
    }

    //nums cannot be reference so that nums[pos+1..n-1] is in increasing order
    void bt(vector<int> nums, vector<vector<int>> &ret, int pos, int n){
        if(pos==n){
            ret.push_back(nums);
        }else{
            for(int i=pos; i<n; ++i){
                if(i>pos && nums[i]==nums[pos]) continue;
                swap(nums[pos], nums[i]);
                bt(nums, ret, pos+1, n);
                //cannot swap back; otherwise nums[pos+1..n-1] will not be in increasing order
            }
        }
    }
};

===========

Note
It is important to keep the increasing order of the non-determined portion of the vector, ie., nums[pos+1, n-1], such that we can conveniently skip the duplicate cases by line 17.

An example for the recursion of nums. pos=0. Note that nums[1, 4] are in increasing order.
0 1 2 3 4 -- index
1 2 3 4 5
2 1 3 4 5
3 1 2 4 5
4 1 2 3 5
5 1 2 3 4

If nums is swapped back at line20. nums[1, 4] are no longer in increasing order.
0 1 2 3 4 -- index
1 2 3 4 5
2 1 3 4 5
3 2 1 4 5
4 2 3 1 5
5 2 3 4 1

LeetCode [46] Permutations

46. Permutations

Medium

Given a collection of distinct integers, return all possible permutations.

Example:

Input: [1,2,3]
Output:
[
  [1,2,3],
  [1,3,2],
  [2,1,3],
  [2,3,1],
  [3,1,2],
  [3,2,1]
]

class Solution {
public:
    vector<vector<int>> permute(vector<int>& nums) {
        vector<vector<int>> res;
        int n = nums.size();
        if(!n) return res;
        bool used[n];
        memset(used, false, n*sizeof(bool));
        vector<int> cur;
        bt(nums, used, cur, 0, n, res);
        return res;
    }

    void bt(vector<int>& nums, bool used[], vector<int> cur, int len, int n, vector<vector<int>> &res){
        if(n==len){
            res.push_back(cur);
        }else{
            for(int i=0; i<n; ++i){
                if(!used[i]){
                    used[i] = true;
                    cur.push_back(nums[i]);
                    bt(nums, used, cur, len+1, n, res);
                    cur.pop_back();
                    used[i] = false;
                }
            }
        }
    }
};

class Solution {
public:
    vector<vector<int>> permute(vector<int>& nums) {
        vector<vector<int>> ret;
        dfs(ret, nums, 0, nums.size());
        return ret;
    }
    void dfs(vector<vector<int>> &ret, vector<int> &nums, int p, int n){
        if(p==n){
            ret.push_back(nums);
        }else{
            for(int i=p; i<n; ++i){
                swap(nums[p], nums[i]);
                dfs(ret, nums, p+1, n);
                swap(nums[p], nums[i]);
            }
        }
    }
};

class Solution {
    List<List<Integer>> lists;
    public List<List<Integer>> permute(int[] nums) {
        lists = new ArrayList<>();
        dfs(nums.length, nums, new ArrayList<>(), new HashSet<>());
        return lists;
    }
    
    void dfs(int n, int[] nums, List<Integer> list, Set<Integer> used){
        if(list.size()==n){
            lists.add(list);
        }else{
            for(int i=0; i<n; ++i){
                if(!used.contains(nums[i])){
                    List<Integer> newList = new ArrayList<>(list);
                    newList.add(nums[i]);
                    used.add(nums[i]);
                    dfs(n, nums, newList, used);
                    used.remove(nums[i]);
                }
            }
        }
    }
}

Thursday, February 19, 2015

LeetCode [60] Permutation Sequence

60. Permutation Sequence

Hard

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 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.
Given k will be between 1 and n! inclusive.

Example 1:

Input: n = 3, k = 3
Output: "213"

Example 2:

Input: n = 4, k = 9
Output: "2314"

class Solution {
public:
    int factorial(int n){
        if(n==0) return 1;
        return n*factorial(n-1);
    }

    string getPermutation(int n, int k) {
        string s;
        vector<char> nums;
        for(int i=1; i<=n; ++i) nums.push_back('0'+i);
        k--;//0-based
        while(s.size()<n){
            int cnt_group = factorial(n-s.size()-1);
            int id_group = k/cnt_group;
            s += nums[id_group];
            nums.erase(nums.begin()+id_group);
            k -= cnt_group*id_group;
        }
        return s;
    }
};

public class Solution {
public String getPermutation(int n, int k) {
    int pos = 0;
    List<Integer> numbers = new ArrayList<>();
    int[] factorial = new int[n+1];
    StringBuilder sb = new StringBuilder();
    
    // create an array of factorial lookup
    int sum = 1;
    factorial[0] = 1;
    for(int i=1; i<=n; i++){
        sum *= i;
        factorial[i] = sum;
    }
    // factorial[] = {1, 1, 2, 6, 24, ... n!}
    
    // create a list of numbers to get indices
    for(int i=1; i<=n; i++){
        numbers.add(i);
    }
    // numbers = {1, 2, 3, 4}
    
    k--;
    
    for(int i = 1; i <= n; i++){
        int index = k/factorial[n-i];
        sb.append(String.valueOf(numbers.get(index)));
        numbers.remove(index);
        k-=index*factorial[n-i];
    }
    
    return String.valueOf(sb);
}
}