KickJava   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 Group
4  */
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.aspx
14  */
15 public class Permutations {
16     
17     private Object JavaDoc[] in;
18     private Object JavaDoc[] out;
19     private int n, m;
20     private int[] index;
21     private boolean hasNext = true;
22
23     public Permutations(Object JavaDoc[] in, Object JavaDoc[] out) {
24         this(in, out, in.length);
25     }
26
27     public Permutations(Object JavaDoc[] in, Object JavaDoc[] 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 rightmost
47      * 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 that
49      * 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 its
53      * 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 right
55      * 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 dips
59 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 dip
66 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 right
74 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 dip
80 reverseAfter(i);
81             
82             // reverse the elements to the right of m - 1
83 reverseAfter(m - 1);
84         }
85     }
86
87     /**
88      * Get the index of the first element from the right that is less
89      * 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 available
119      */
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