<Must Read>Solution WITHOUT random generators, using pure permutation techniques


  • -1
    L

    Algo :
    *--> For an array of n integers, the 'max' number of permutations will be n! (there can be duplicates, which can decrease the 'exact' number of permutations, but they are irrelevant here). Make sure we take care of overflowing of the factorial

    --> Keep global shuffle_counter, incresed everytime with the shuffle function

    --> Keep a local_counter that is used to find the Yth permutation (Y = global shuffle counter)

    --> To break from the recursion, we need extra result array, and a stop_flag, to break out from the next for loop iteration.

    public class Solution {
    long shuffle_count, local_count, maxPerms;
    int[] original;
    int[] copy;
    int[] result;
    boolean stop_flag,shuffle_allowed;

    public Solution(int[] nums) {
        original = nums;
        copy = new int[nums.length];
        copyArray(copy, original);
        result = new int[nums.length];
        maxPerms = nums.length;
        for(int i = nums.length-1 ; i>1 && maxPerms > 1 ; i--)
          maxPerms = maxPerms*i;
        if(maxPerms < 1)
          maxPerms = Long.MAX_VALUE;
        shuffle_count = 0;
        local_count = -1;
        stop_flag = false;
        shuffle_allowed = !(nums.length < 2 );
    }
    
    /** Resets the array to its original configuration and return it. */
    public int[] reset() {
       return original;    
    }
    
    /** Returns a random shuffling of the array. */
    public int[] shuffle() {
        if(shuffle_allowed){
         shuffle_count = (shuffle_count+1)%maxPerms;
         local_count = -1;
         stop_flag = false;
         result = new int[copy.length];
         permute(copy, 0, copy.length-1);
        }
         return result;
    }
    
    public void permute(int [] num, int s, int e){
        if(s==e){
            local_count++;
            if(local_count == shuffle_count){
              stop_flag = true;
              copyArray(result, num);
            }
            return;
        }
        
        for(int i=s ; i<=e && stop_flag==false; i++){
            swap(num, s, i);
            permute(num, s+1, e);
            swap(num, s, i);
        }
    }
    
    public void swap(int[] num, int x, int y){
        int temp = num[x];
        num[x] = num[y];
        num[y] = temp;
    }
    
    public void copyArray(int[]a, int[]b){
        for(int i=0; i<b.length;i++)
         a[i] = b[i];
    }
    

    }

    /**

    • Your Solution object will be instantiated and called as such:
    • Solution obj = new Solution(nums);
    • int[] param_1 = obj.reset();
    • int[] param_2 = obj.shuffle();
      */

Log in to reply
 

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