Advertisement
cd62131

Generate Combinations

Aug 22nd, 2017
312
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
Java 5 1.37 KB | None | 0 0
  1. import java.util.ArrayList;
  2. import java.util.List;
  3.  
  4. public class Combinations {
  5.     private final int n;
  6.     private int x;
  7.     private String[] disp;
  8.  
  9.     public static void main(String[] args) {
  10.         System.out.println(new Combinations(8).generateAll());
  11.         System.out.println(new Combinations(new String[] { "a", "b", "c" }).generateAll());
  12.     }
  13.  
  14.     public Combinations(int n) {
  15.         this.n = n;
  16.         disp = new String[n];
  17.         for (int i = 0; i < n; ++i) {
  18.             disp[i] = Integer.toString(i + 1);
  19.         }
  20.     }
  21.  
  22.     public Combinations(String[] ss) {
  23.         n = ss.length;
  24.         disp = ss;
  25.     }
  26.  
  27.     private int lowBit(int n) {
  28.         return (1 << n) - 1;
  29.     }
  30.  
  31.     private boolean next() {
  32.         int smallest = x & -x;
  33.         int ripple = x + smallest;
  34.         int new_smallest = ripple & -ripple;
  35.         int ones = ((new_smallest / smallest) >>> 1) - 1;
  36.         x = ripple | ones;
  37.         return (x & ~lowBit(n)) == 0;
  38.     }
  39.  
  40.     public List<List<String>> generate(int k) {
  41.         List<List<String>> ret = new ArrayList<>();
  42.         x = lowBit(k);
  43.         do {
  44.             List<String> lis = new ArrayList<>();
  45.             for (int s = x, i = 1; i <= n; s >>>= 1, ++i) {
  46.                 if ((s & 1) == 1) {
  47.                     lis.add(disp[i - 1]);
  48.                 }
  49.             }
  50.             ret.add(lis);
  51.         } while (next());
  52.         return ret;
  53.     }
  54.  
  55.     public List<List<List<String>>> generateAll() {
  56.         List<List<List<String>>> ret = new ArrayList<>();
  57.         for (int i = 1; i <= n; ++i) {
  58.             ret.add(generate(i));
  59.         }
  60.         return ret;
  61.     }
  62. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement