Code666 (代码贴、代码片段)

[Java] 一个用于产生全排列的java类代码 →→→→→进入此内容的聊天室

来自 , 2019-07-07, 写在 Java, 查看 107 次.
URL http://www.code666.cn/view/ac2d43ef
  1. // Permute.java -- A class generating all permutations
  2.  
  3. import java.util.Iterator;
  4. import java.util.NoSuchElementException;
  5. import java.lang.reflect.Array;
  6.  
  7. public class Permute implements Iterator {
  8.  
  9.    private final int size;
  10.    private final Object [] elements;  // copy of original 0 .. size-1
  11.    private final Object ar;           // array for output,  0 .. size-1
  12.    private final int [] permutation;  // perm of nums 1..size, perm[0]=0
  13.  
  14.    private boolean next = true;
  15.  
  16.    // int[], double[] array won't work :-(
  17.    public Permute (Object [] e) {
  18.       size = e.length;
  19.       elements = new Object [size];    // not suitable for primitives
  20.       System.arraycopy (e, 0, elements, 0, size);
  21.       ar = Array.newInstance (e.getClass().getComponentType(), size);
  22.       System.arraycopy (e, 0, ar, 0, size);
  23.       permutation = new int [size+1];
  24.       for (int i=0; i<size+1; i++) {
  25.          permutation [i]=i;
  26.       }
  27.    }
  28.  
  29.    private void formNextPermutation () {
  30.       for (int i=0; i<size; i++) {
  31.          // i+1 because perm[0] always = 0
  32.          // perm[]-1 because the numbers 1..size are being permuted
  33.          Array.set (ar, i, elements[permutation[i+1]-1]);
  34.       }
  35.    }
  36.  
  37.    public boolean hasNext() {
  38.       return next;
  39.    }
  40.  
  41.    public void remove() throws UnsupportedOperationException {
  42.       throw new UnsupportedOperationException();
  43.    }
  44.  
  45.    private void swap (final int i, final int j) {
  46.       final int x = permutation[i];
  47.       permutation[i] = permutation [j];
  48.       permutation[j] = x;
  49.    }
  50.  
  51.    // does not throw NoSuchElement; it wraps around!
  52.    public Object next() throws NoSuchElementException {
  53.  
  54.       formNextPermutation ();  // copy original elements
  55.  
  56.       int i = size-1;
  57.       while (permutation[i]>permutation[i+1]) i--;
  58.  
  59.       if (i==0) {
  60.          next = false;
  61.          for (int j=0; j<size+1; j++) {
  62.             permutation [j]=j;
  63.          }
  64.          return ar;
  65.       }
  66.  
  67.       int j = size;
  68.  
  69.       while (permutation[i]>permutation[j]) j--;
  70.       swap (i,j);
  71.       int r = size;
  72.       int s = i+1;
  73.       while (r>s) { swap(r,s); r--; s++; }
  74.  
  75.       return ar;
  76.    }
  77.  
  78.    public String toString () {
  79.       final int n = Array.getLength(ar);
  80.       final StringBuffer sb = new StringBuffer ("[");
  81.       for (int j=0; j<n; j++) {
  82.          sb.append (Array.get(ar,j).toString());
  83.          if (j<n-1) sb.append (",");
  84.       }
  85.       sb.append("]");
  86.       return new String (sb);
  87.    }
  88.  
  89.   //code from http://www.sharejs.com/codes/
  90.    public static void main (String [] args) {
  91.       for (Iterator i = new Permute(args); i.hasNext(); ) {
  92.          final String [] a = (String []) i.next();
  93.          System.out.println (i);
  94.       }
  95.    }
  96. }
  97. //java/8709

回复 "一个用于产生全排列的java类代码"

这儿你可以回复上面这条便签

captcha

贴代码片段 - Code666