File D:\maven-qcr-plugin-testsunitaires\qcr4java\h2-1.3.170-sources\target\site\qc\lecode\util\Permutations.java.html

1 /*
2 * Copyright 2004-2011 H2 Group. Multiple-Licensed under the H2 License,
3 * Version 1.0, and under the Eclipse Public License, Version 1.0
4 * (http://h2database.com/html/license.html).
5 * Initial Developer: H2 Group
6 *
7 * According to a mail from Alan Tucker to Chris H Miller from IBM,
8 * the algorithm is in the public domain:
9 *
10 * Date: 2010-07-15 15:57
11 * Subject: Re: Applied Combinatorics Code
12 *
13 * Chris,
14 * The combinatorics algorithms in my textbook are all not under patent
15 * or copyright. They are as much in the public domain as the solution to any
16 * common question in an undergraduate mathematics course, e.g., in my
17 * combinatorics course, the solution to the problem of how many arrangements
18 * there are of the letters in the word MATHEMATICS. I appreciate your due
19 * diligence.
20 * -Alan
21 */
22 package org.h2.util;
23
24 import org.h2.message.DbException;
25
26 /**
27 * A class to iterate over all permutations of an array.
28 * The algorithm is from Applied Combinatorics, by Alan Tucker as implemented in
29 * http://www.koders.com/java/fidD3445CD11B1DC687F6B8911075E7F01E23171553.aspx
30 *
31 * @param <T> the element type
32 */
33 public class Permutations<T> {
34
35 private final T[] in;
36 private final T[] out;
37 private final int n, m;
38 private final int[] index;
39 private boolean hasNext = true;
40
41 private Permutations(T[] in, T[] out, int m) {
42 this.n = in.length;
43 this.m = m;
44 if (n < m || m < 0) {
45 DbException.throwInternalError("n < m or m < 0");
46 }
47 this.in = in;
48 this.out = out;
49 index = new int[n];
50 for (int i = 0; i < n; i++) {
51 index[i] = i;
52 }
53
54 // The elements from m to n are always kept ascending right to left.
55 // This keeps the dip in the interesting region.
56 reverseAfter(m - 1);
57 }
58
59 /**
60 * Create a new permutations object.
61 *
62 * @param <T> the type
63 * @param in the source array
64 * @param out the target array
65 * @return the generated permutations object
66 */
67 public static <T> Permutations<T> create(T[] in, T[] out) {
68 return new Permutations<T>(in, out, in.length);
69 }
70
71 /**
72 * Create a new permutations object.
73 *
74 * @param <T> the type
75 * @param in the source array
76 * @param out the target array
77 * @param m the number of output elements to generate
78 * @return the generated permutations object
79 */
80 public static <T> Permutations<T> create(T[] in, T[] out, int m) {
81 return new Permutations<T>(in, out, m);
82 }
83
84 /**
85 * Move the index forward a notch. The algorithm first finds the rightmost
86 * index that is less than its neighbor to the right. This is the dip point.
87 * The algorithm next finds the least element to the right of the dip that
88 * is greater than the dip. That element is switched with the dip. Finally,
89 * the list of elements to the right of the dip is reversed.
90 * For example, in a permutation of 5 items, the index may be {1, 2, 4, 3,
91 * 0}. The dip is 2 the rightmost element less than its neighbor on its
92 * right. The least element to the right of 2 that is greater than 2 is 3.
93 * These elements are swapped, yielding {1, 3, 4, 2, 0}, and the list right
94 * of the dip point is reversed, yielding {1, 3, 0, 2, 4}.
95 */
96 private void moveIndex() {
97 // find the index of the first element that dips
98 int i = rightmostDip();
99 if (i < 0) {
100 hasNext = false;
101 return;
102 }
103
104 // find the least greater element to the right of the dip
105 int leastToRightIndex = i + 1;
106 for (int j = i + 2; j < n; j++) {
107 if (index[j] < index[leastToRightIndex] && index[j] > index[i]) {
108 leastToRightIndex = j;
109 }
110 }
111
112 // switch dip element with least greater element to its right
113 int t = index[i];
114 index[i] = index[leastToRightIndex];
115 index[leastToRightIndex] = t;
116
117 if (m - 1 > i) {
118 // reverse the elements to the right of the dip
119 reverseAfter(i);
120
121 // reverse the elements to the right of m - 1
122 reverseAfter(m - 1);
123 }
124 }
125
126 /**
127 * Get the index of the first element from the right that is less
128 * than its neighbor on the right.
129 *
130 * @return the index or -1 if non is found
131 */
132 private int rightmostDip() {
133 for (int i = n - 2; i >= 0; i--) {
134 if (index[i] < index[i + 1]) {
135 return i;
136 }
137 }
138 return -1;
139 }
140
141 /**
142 * Reverse the elements to the right of the specified index.
143 *
144 * @param i the index
145 */
146 private void reverseAfter(int i) {
147 int start = i + 1;
148 int end = n - 1;
149 while (start < end) {
150 int t = index[start];
151 index[start] = index[end];
152 index[end] = t;
153 start++;
154 end--;
155 }
156 }
157
158 /**
159 * Go to the next lineup, and if available, fill the target array.
160 *
161 * @return if a new lineup is available
162 */
163 public boolean next() {
164 if (!hasNext) {
165 return false;
166 }
167 for (int i = 0; i < m; i++) {
168 out[i] = in[index[i]];
169 }
170 moveIndex();
171 return true;
172 }
173
174 }
175