001: /*
002: * Copyright 2004-2008 H2 Group. Licensed under the H2 License, Version 1.0
003: * (http://h2database.com/html/license.html).
004: * Initial Developer: H2 Group
005: */
006: package org.h2.util;
007:
008: import org.h2.message.Message;
009:
010: /**
011: * A class to iterate over all permutations of an array.
012: * The algorithm is from Applied Combinatorics, by Alan Tucker as implemented in
013: * http://www.koders.com/java/fidD3445CD11B1DC687F6B8911075E7F01E23171553.aspx
014: */
015: public class Permutations {
016:
017: private Object[] in;
018: private Object[] out;
019: private int n, m;
020: private int[] index;
021: private boolean hasNext = true;
022:
023: /**
024: * Create a new permutations object.
025: *
026: * @param in the source array
027: * @param out the target array
028: */
029: public Permutations(Object[] in, Object[] out) {
030: this (in, out, in.length);
031: }
032:
033: /**
034: * Create a new permutations object.
035: *
036: * @param in the source array
037: * @param out the target array
038: * @param m the number of output elements to generate
039: */
040: public Permutations(Object[] in, Object[] out, int m) {
041: this .n = in.length;
042: this .m = m;
043: if (n < m || m < 0) {
044: throw Message.getInternalError("n < m or m < 0");
045: }
046: this .in = in;
047: this .out = out;
048: index = new int[n];
049: for (int i = 0; i < n; i++) {
050: index[i] = i;
051: }
052:
053: // The elements from m to n are always kept ascending right to left.
054: // This keeps the dip in the interesting region.
055: reverseAfter(m - 1);
056: }
057:
058: /**
059: * Move the index forward a notch. The algorithm first finds the rightmost
060: * index that is less than its neighbor to the right. This is the dip point.
061: * The algorithm next finds the least element to the right of the dip that
062: * is greater than the dip. That element is switched with the dip. Finally,
063: * the list of elements to the right of the dip is reversed.
064: * For example, in a permutation of 5 items, the index may be {1, 2, 4, 3,
065: * 0}. The dip is 2 the rightmost element less than its neighbor on its
066: * right. The least element to the right of 2 that is greater than 2 is 3.
067: * These elements are swapped, yielding {1, 3, 4, 2, 0}, and the list right
068: * of the dip point is reversed, yielding {1, 3, 0, 2, 4}.
069: */
070: private void moveIndex() {
071: // find the index of the first element that dips
072: int i = rightmostDip();
073: if (i < 0) {
074: hasNext = false;
075: return;
076: }
077:
078: // find the least greater element to the right of the dip
079: int leastToRightIndex = i + 1;
080: for (int j = i + 2; j < n; j++) {
081: if (index[j] < index[leastToRightIndex]
082: && index[j] > index[i]) {
083: leastToRightIndex = j;
084: }
085: }
086:
087: // switch dip element with least greater element to its right
088: int t = index[i];
089: index[i] = index[leastToRightIndex];
090: index[leastToRightIndex] = t;
091:
092: if (m - 1 > i) {
093: // reverse the elements to the right of the dip
094: reverseAfter(i);
095:
096: // reverse the elements to the right of m - 1
097: reverseAfter(m - 1);
098: }
099: }
100:
101: /**
102: * Get the index of the first element from the right that is less
103: * than its neighbor on the right.
104: *
105: * @return the index or -1 if non is found
106: */
107: private int rightmostDip() {
108: for (int i = n - 2; i >= 0; i--) {
109: if (index[i] < index[i + 1]) {
110: return i;
111: }
112: }
113: return -1;
114: }
115:
116: /**
117: * Reverse the elements to the right of the specified index.
118: *
119: * @param i the index
120: */
121: private void reverseAfter(int i) {
122: int start = i + 1;
123: int end = n - 1;
124: while (start < end) {
125: int t = index[start];
126: index[start] = index[end];
127: index[end] = t;
128: start++;
129: end--;
130: }
131: }
132:
133: /**
134: * Go to the next lineup, and if available, fill the target array.
135: *
136: * @return if a new lineup is available
137: */
138: public boolean next() {
139: if (!hasNext) {
140: return false;
141: }
142: for (int i = 0; i < m; i++) {
143: out[i] = in[index[i]];
144: }
145: moveIndex();
146: return true;
147: }
148:
149: }
|