daily pastebin goal
87%
SHARE
TWEET

Untitled

a guest Jan 22nd, 2019 60 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. public class Permutations<T> implements IEnumerable<List<T>> {
  2.  
  3.     PermutationGenerator pGenerator;
  4.     T[] elements;
  5.     int[] indices;
  6.  
  7.     public Permutations(List<T> list) {
  8.         pGenerator = new PermutationGenerator(list.size());
  9.         elements = (T[]) list.toArray();
  10.     }
  11.  
  12.     public Iterator<List<T>> iterator() {
  13.         return new Iterator<List<T>>() {
  14.  
  15.             int pos = 0;
  16.  
  17.             public boolean hasNext() {
  18.                 return pGenerator.hasMore();
  19.             }
  20.  
  21.             public List<T> next() {
  22.                 if (!hasNext()) {
  23.                     throw new NoSuchElementException();
  24.                 }
  25.                 indices = pGenerator.getNext();
  26.                 List<T> permutation = new ArrayList<T>();
  27.                 for (int i = 0; i < indices.length; i++) {
  28.                     permutation.add(elements[indices[i]]);
  29.                 }
  30.                 return permutation;
  31.             }
  32.  
  33.             public void remove() {
  34.                 throw new UnsupportedOperationException();
  35.             }
  36.         };
  37.     }
  38.  
  39.     private final class PermutationGenerator {
  40.  
  41.         private int[] a;
  42.         private BigInteger numLeft;
  43.         private BigInteger total;
  44.  
  45.         //-----------------------------------------------------------
  46.         // Constructor. WARNING: Don't make n too large.
  47.         // Recall that the number of permutations is n!
  48.         // which can be very large, even when n is as small as 20 --
  49.         // 20! = 2,432,902,008,176,640,000 and
  50.         // 21! is too big to fit into a Java long, which is
  51.         // why we use BigInteger instead.
  52.         //----------------------------------------------------------
  53.         public PermutationGenerator(int n) {
  54.             if (n < 1) {
  55.                 throw new IllegalArgumentException("Set must have at least one element");
  56.             }
  57.             a = new int[n];
  58.             total = getFactorial(n);
  59.             reset();
  60.         }
  61.  
  62.         //------
  63.         // Reset
  64.         //------
  65.         public void reset() {
  66.             for (int i = 0; i < a.length; i++) {
  67.                 a[i] = i;
  68.             }
  69.             numLeft = new BigInteger(total.toString());
  70.         }
  71.  
  72.         //------------------------------------------------
  73.         // Return number of permutations not yet generated
  74.         //------------------------------------------------
  75.         public BigInteger getNumLeft() {
  76.             return numLeft;
  77.         }
  78.  
  79.         //------------------------------------
  80.         // Return total number of permutations
  81.         //------------------------------------
  82.         public BigInteger getTotal() {
  83.             return total;
  84.         }
  85.  
  86.         //-----------------------------
  87.         // Are there more permutations?
  88.         //-----------------------------
  89.         public boolean hasMore() {
  90.             return numLeft.compareTo(BigInteger.ZERO) == 1;
  91.         }
  92.  
  93.         //------------------
  94.         // Compute factorial
  95.         //------------------
  96.         private BigInteger getFactorial(int n) {
  97.             BigInteger fact = BigInteger.ONE;
  98.             for (int i = n; i > 1; i--) {
  99.                 fact = fact.multiply(new BigInteger(Integer.toString(i)));
  100.             }
  101.             return fact;
  102.         }
  103.  
  104.         //--------------------------------------------------------
  105.         // Generate next permutation (algorithm from Rosen p. 284)
  106.         //--------------------------------------------------------
  107.         public int[] getNext() {
  108.  
  109.             if (numLeft.equals(total)) {
  110.                 numLeft = numLeft.subtract(BigInteger.ONE);
  111.                 return a;
  112.             }
  113.  
  114.             int temp;
  115.  
  116.             // Find largest index j with a[j] < a[j+1]
  117.  
  118.             int j = a.length - 2;
  119.             while (a[j] > a[j + 1]) {
  120.                 j--;
  121.             }
  122.  
  123.             // Find index k such that a[k] is smallest integer
  124.             // greater than a[j] to the right of a[j]
  125.  
  126.             int k = a.length - 1;
  127.             while (a[j] > a[k]) {
  128.                 k--;
  129.             }
  130.  
  131.             // Interchange a[j] and a[k]
  132.  
  133.             temp = a[k];
  134.             a[k] = a[j];
  135.             a[j] = temp;
  136.  
  137.             // Put tail end of permutation after jth position in increasing order
  138.  
  139.             int r = a.length - 1;
  140.             int s = j + 1;
  141.  
  142.             while (r > s) {
  143.                 temp = a[s];
  144.                 a[s] = a[r];
  145.                 a[r] = temp;
  146.                 r--;
  147.                 s++;
  148.             }
  149.  
  150.             numLeft = numLeft.subtract(BigInteger.ONE);
  151.             return a;
  152.  
  153.         }
  154.     }
  155. }
  156.  
  157. public class Program
  158. {
  159.   public List<List<char>> Results(List<char> allValues)
  160.         {
  161.             var collection = new List<List<char>>();
  162.             for (int counter = 0; counter < (1 << allValues.Count); ++counter)
  163.             {
  164.                 List<char> combination = new List<char>();
  165.                 for (int i = 0; i < allValues.Count; ++i)
  166.                 {
  167.                     if ((counter & (1 << i)) == 0)
  168.                         combination.Add(allValues[i]);
  169.                 }
  170.  
  171.                 // do something with combination
  172.                 collection.Add(combination);
  173.             }
  174.             return collection;
  175.         }
  176.  
  177.         void PowerSetofChars()
  178.         {
  179.             var chars = new List<char> { 'A', 'B', 'C' };
  180.  
  181.             var result = Results(chars);
  182.  
  183.         }
  184. public static void Main(string[] args)
  185. {
  186. Program p = new Program();
  187. p.PowerSetOfChars();
  188. }
  189. }
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
 
Top