SHARE
TWEET

Permutations Larger Than or Equal to K

a guest May 23rd, 2019 80 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. import java.util.ArrayList;
  2. import java.util.Arrays;
  3.  
  4. public class ValidPermutations {
  5.     private int _k;
  6.     private int[] _list;
  7.  
  8.     public ValidPermutations(int k, int[] list)
  9.     {
  10.         this._k = k;
  11.         this._list = list;
  12.     }
  13.  
  14.     private ArrayList<int[]> _allPermutationsRecurs(int[] prevList)
  15.     {
  16.         ArrayList<int[]> permutations = new ArrayList<int[]>();
  17.         permutations.add(prevList);
  18.         for (int i = 0; i < prevList.length; i++)
  19.         {
  20.             int[] currPermutation = new int[prevList.length - 1];
  21.             for (int j = 0; j < prevList.length - 1; j++)
  22.             {
  23.                 if (j >= i)
  24.                     currPermutation[j] = prevList[j + 1];
  25.                 else if (j < i)
  26.                     currPermutation[j] = prevList[j];
  27.             }
  28.            
  29.             if (currPermutation.length != 0)
  30.             {
  31.                 ArrayList<int[]> nextPermutations = this._allPermutations(currPermutation);
  32.                 for (int j = 0; j < nextPermutations.size(); j++)
  33.                     permutations.add(nextPermutations.get(j));
  34.             }
  35.         }
  36.         return permutations;
  37.     }
  38.  
  39.     private ArrayList<int[]> _allPermutations(int[] list)
  40.     {
  41.         ArrayList<int[]> permutations = this._allPermutationsRecurs(list);
  42.         for (int i = permutations.size() - 1; i >= 0; i--)
  43.         {
  44.             for (int j = i - 1; j >= 0; j--)
  45.             {
  46.                 if (Arrays.equals(permutations.get(i), permutations.get(j)))
  47.                 {
  48.                     permutations.remove(i);
  49.                     break;
  50.                 }
  51.             }
  52.         }
  53.         return permutations;
  54.     }
  55.  
  56.     public ArrayList<int[]> PermutationsWithSumsLargerThanOrEqualToK()
  57.     {
  58.         ArrayList<int[]> allPermutations = this._allPermutations(this._list);
  59.         for (int i = allPermutations.size() - 1; i >= 0; i--)
  60.         {
  61.             int sum = 0;
  62.             for (int j = 0; j < allPermutations.get(i).length; j++)
  63.                 sum += allPermutations.get(i)[j];
  64.             if (sum < this._k) allPermutations.remove(i);
  65.         }
  66.  
  67.         return allPermutations;
  68.     }
  69.  
  70.     public static void main(String[] args)
  71.     {
  72.         ValidPermutations perms = new ValidPermutations(12, new int[] {5, 7, 9});
  73.         ArrayList<int[]> validPerms = perms.PermutationsWithSumsLargerThanOrEqualToK();
  74.  
  75.         for (int i = 0; i < validPerms.size(); i++)
  76.         {
  77.             System.out.print("[");
  78.             for (int j = 0; j < validPerms.get(i).length; j++)
  79.                 System.out.print(" " + validPerms.get(i)[j]);
  80.             System.out.print(" ]\n");
  81.         }
  82.     }
  83. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
Not a member of Pastebin yet?
Sign Up, it unlocks many cool features!
 
Top