Java API By Example, From Geeks To Geeks.

# Java > Open Source Codes > org > h2 > util > Permutations

 `1 /*2  * Copyright 2004-2006 H2 Group. Licensed under the H2 License, Version 1.0 (http://h2database.com/html/license.html).3  * Initial Developer: H2 Group4  */5 package org.h2.util;6 7 import org.h2.message.Message;8 9 10 /**11  * A class to iterate over all permutations of an array.12  * The algorithm is from Applied Combinatorics, by Alan Tucker as implemented in 13  * http://www.koders.com/java/fidD3445CD11B1DC687F6B8911075E7F01E23171553.aspx14  */15 public class Permutations {16     17     private Object [] in;18     private Object [] out;19     private int n, m;20     private int[] index;21     private boolean hasNext = true;22 23     public Permutations(Object [] in, Object [] out) {24         this(in, out, in.length);25     }26 27     public Permutations(Object [] in, Object [] out, int m) {28         this.n = in.length;29         this.m = m;30         if (n < m || m < 0) {31             throw Message.getInternalError("n < m or m < 0");32         }33         this.in = in;34         this.out = out;35         index = new int[n];36         for (int i = 0; i < n; i++) {37             index[i] = i;38         }39 40         // The elements from m to n are always kept ascending right to left.41 // This keeps the dip in the interesting region.42 reverseAfter(m - 1);43     }44 45     /**46      * Move the index forward a notch. The algorithm first finds the rightmost47      * index that is less than its neighbor to the right. This is the dip point.48      * The algorithm next finds the least element to the right of the dip that49      * is greater than the dip. That element is switched with the dip. Finally,50      * the list of elements to the right of the dip is reversed.51      * For example, in a permutation of 5 items, the index may be {1, 2, 4, 3,52      * 0}. The dip is 2 the rightmost element less than its neighbor on its53      * right. The least element to the right of 2 that is greater than 2 is 3.54      * These elements are swapped, yielding {1, 3, 4, 2, 0}, and the list right55      * of the dip point is reversed, yielding {1, 3, 0, 2, 4}.56      */57     private void moveIndex() {58         // find the index of the first element that dips59 int i = rightmostDip();60         if (i < 0) {61             hasNext = false;62             return;63         }64 65         // find the least greater element to the right of the dip66 int leastToRightIndex = i + 1;67         for (int j = i + 2; j < n; j++) {68             if (index[j] < index[leastToRightIndex] && index[j] > index[i]) {69                 leastToRightIndex = j;70             }71         }72 73         // switch dip element with least greater element to its right74 int t = index[i];75         index[i] = index[leastToRightIndex];76         index[leastToRightIndex] = t;77 78         if (m - 1 > i) {79             // reverse the elements to the right of the dip80 reverseAfter(i);81             82             // reverse the elements to the right of m - 183 reverseAfter(m - 1);84         }85     }86 87     /**88      * Get the index of the first element from the right that is less89      * than its neighbor on the right.90      */91     private int rightmostDip() {92         for (int i = n - 2; i >= 0; i--) {93             if (index[i] < index[i + 1]) {94                 return i;95             }96         }97         return -1;98     }99 100     /**101      * Reverse the elements to the right of the specified index.102      */103     private void reverseAfter(int i) {104         int start = i + 1;105         int end = n - 1;106         while (start < end) {107             int t = index[start];108             index[start] = index[end];109             index[end] = t;110             start++;111             end--;112         }113     }114     115     /**116      * Go to the next lineup, and if available, fill the target array.117      * 118      * @return if a new lineup is available119      */120     public boolean next() {121         if (!hasNext) {122             return false;123         }124         for (int i = 0; i < m; i++) {125             out[i] = in[index[i]];126         }127         moveIndex();128         return true;129     }130     131 }132 ` Popular Tags