1 | static <A> IterableIterator<O[]> allPermutations_iterator(final L<A> theList) {
|
2 | ret new IterableIterator<O[]>() {
|
3 | int[] next;
|
4 |
|
5 | int n = l(theList);
|
6 | int[] perm, dirs;
|
7 |
|
8 | {
|
9 | if (n > 0) {
|
10 | perm = new int[n];
|
11 | dirs = new int[n];
|
12 | for(int i = 0; i < n; i++) {
|
13 | perm[i] = i;
|
14 | dirs[i] = -1;
|
15 | }
|
16 | dirs[0] = 0;
|
17 | }
|
18 |
|
19 | next = perm;
|
20 | }
|
21 |
|
22 | @Override
|
23 | public O[] next() {
|
24 | int[] r = makeNext();
|
25 | next = null;
|
26 | O[] out = new O[n];
|
27 | for i to n:
|
28 | out[i] = theList.get(r[i]);
|
29 | ret out;
|
30 | }
|
31 |
|
32 | @Override
|
33 | public boolean hasNext() {
|
34 | return (makeNext() != null);
|
35 | }
|
36 |
|
37 | @Override
|
38 | public void remove() {
|
39 | throw new UnsupportedOperationException();
|
40 | }
|
41 |
|
42 | int[] makeNext() {
|
43 | ping();
|
44 | if (next != null)
|
45 | return next;
|
46 | if (perm == null)
|
47 | return null;
|
48 |
|
49 | // find the largest element with != 0 direction
|
50 | int i = -1, e = -1;
|
51 | for(int j = 0; j < n; j++)
|
52 | if ((dirs[j] != 0) && (perm[j] > e)) {
|
53 | e = perm[j];
|
54 | i = j;
|
55 | }
|
56 |
|
57 | if (i == -1) // no such element -> no more premutations
|
58 | return (next = (perm = (dirs = null))); // no more permutations
|
59 |
|
60 | // swap with the element in its direction
|
61 | int k = i + dirs[i];
|
62 | swapIntArray(dirs, i, k);
|
63 | swapIntArray(perm, i, k);
|
64 | // if it's at the start/end or the next element in the direction
|
65 | // is greater, reset its direction.
|
66 | if ((k == 0) || (k == n-1) || (perm[k + dirs[k]] > e))
|
67 | dirs[k] = 0;
|
68 |
|
69 | // set directions to all greater elements
|
70 | for(int j = 0; j < n; j++)
|
71 | if (perm[j] > e)
|
72 | dirs[j] = (j < k) ? +1 : -1;
|
73 |
|
74 | return (next = perm);
|
75 | }
|
76 | };
|
77 | } |