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