Hallo,

inspiriert durch den Beitrag:
http://www.tutorials.de/algorithmen-...utationen.html
habe ich mir mal Gedanken darüber gemacht wie man die Generierung einer Permutation mit einem Iterator formulieren kann. Zusätzlich wollte ich herausfinden, wie man die Permutationen Schrittweise oder gar verzögert bzw. lazy on-the-fly berechnen kann.

Deshalb hier mal ein kleines Beispiel für die lazy Generierung von Permutationen in einem Iterator. Lazy bedeutet hier, dass die Permutation erst dann "berechnet" wird wenn diese in der Iteration benötigt wird.

Als kleine Hilfs-Bibliothek (zur einfachen Formulierung des Iterators) verwende ich guava-libraries: http://code.google.com/p/guava-libraries/

Nebenbei zeige ich noch eine Möglichkeit zur Bestimmung von Potenzmengen.

Den gezeigten Algorithmus zur Generierung von Permutationen habe ich von wikipedia
entnommen: http://en.wikipedia.org/wiki/Permutation (Systematic generation of all permutations)

Code java:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159

package de.tutorials.algo;
 
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collection;
import java.util.Comparator;
import java.util.HashSet;
import java.util.Iterator;
import java.util.List;
import java.util.Set;
import java.util.TreeSet;
 
import com.google.common.collect.AbstractIterator;
 
import static com.google.common.collect.Lists.newArrayList;
import static com.google.common.collect.Sets.newHashSet;
 
public class LazyPermutations {
    
    public static void main(String[] args) {
           System.out.println("#Permutation");
            for (Object[] perm : new Permutations(newArrayList(1,2,3,1))) {
                System.out.println(Arrays.toString(perm));
            }
            
            System.out.println();
            
            System.out.println("#Alle Permutationen über die Potenzmenge");
            for (Set<String> set : powerSet(newHashSet("A", "B", "C"))) {
                if (set.isEmpty()) continue;
                for (Object[] perm : new Permutations(set)) {
                    System.out.println(Arrays.toString(perm));
                }
            }
    }
 
    /*
     * ich hätte auch com.google.common.collect.Sets.powerSet(set) verwenden können... 
     * aber ich wollte hiermit eine einfache alternative Implementierung demonstrieren. 
     */
    private static <T> Set<Set<T>> powerSet(Set<T> set) { 
        Set<Set<T>> powerSet = new TreeSet<Set<T>>(compareSetsBySizeAndHashCode());
        List<T> items = new ArrayList<T>(set);
 
        int numberOfItems = items.size();
        int numberOfSets = (int) Math.pow(2, set.size());
 
        for (int i = 0; i < numberOfSets; i++) {
            Set<T> subSet = new HashSet<T>();
            for (int j = 0; j < numberOfItems; j++) {
                boolean bitIsSet = ((i >> j) & 1) == 1; //TODO: handle overflow
                if (bitIsSet) {
                    T item = items.get(j);
                    subSet.add(item);
                }
            }
            powerSet.add(subSet);
        }
 
        return powerSet;
    }
 
    private static Comparator<Set<? extends Object>> compareSetsBySizeAndHashCode() {
        return new Comparator<Set<? extends Object>>() {
            public int compare(Set<? extends Object> first, Set<? extends Object> second) {
                int result = first.size() - second.size();
                if (result == 0) {
                    result = first.hashCode() - second.hashCode(); //as a last resort we order by hashcode.
                }
                return result;
            }
        };
    }
 
    static class Permutations extends AbstractIterator<Object[]> implements Iterable<Object[]> {
        private final static int NO_SUCH_INDEX_EXISTS = -1;
 
        private Object[] items;
        private Object[] currentPermutation;
        private boolean firstIteration;
 
        public Permutations(Collection<? extends Comparable<?>> items) {
            Object[] array = items.toArray();
            Arrays.sort(array);
            this.items = array;
            this.firstIteration = true;
        }
 
        @Override
        protected Object[] computeNext() {
            /*
             * [url]http://en.wikipedia.org/wiki/Permutation[/url] 
             * Systematic generation of all permutations
             */
            if (firstIteration) { // we simply return the items we just sorted as current permutation 
                currentPermutation = items.clone();
                firstIteration = false;
            } else {
                int k = findLargestIndexK(); /* such that items[k] < items[k + 1] */
 
                switch (k) {
 
                case NO_SUCH_INDEX_EXISTS:
                    currentPermutation = endOfData();
                    break;
 
                default:
                    int l = findLargestIndexL(k); /* such that items[k] < items[l] */
                    swap(k, l);
                    reverseTailFrom(k);
 
                }
            }
            return currentPermutation;
        }
 
        private int findLargestIndexK() {
            int k = -1;
            for (int i = 0; i < currentPermutation.length - 1; i++) {
                if (firstIsSmaller(currentPermutation[i], currentPermutation[i + 1])) {
                    k = i;
                }
            }
            return k;
        }
 
        private int findLargestIndexL(int k) {
            int l = -1;
            for (int i = k + 1; i < currentPermutation.length; i++) {
                if (firstIsSmaller(currentPermutation[k], currentPermutation[i])) {
                    l = i;
                }
            }
            return l;
        }
 
        private void swap(int i, int j) {
            Object tmp = currentPermutation[i];
            currentPermutation[i] = currentPermutation[j];
            currentPermutation[j] = tmp;
        }
 
        private void reverseTailFrom(int k) {
            for (int i = k + 1, j = currentPermutation.length - 1; i < j; i++, j--) {
                swap(i, j);
            }
        }
 
        @SuppressWarnings("unchecked")
        private boolean firstIsSmaller(Object first, Object second) {
            return ((Comparable<Object>) first).compareTo(second) < 0;
        }
 
        @Override
        public Iterator<Object[]> iterator() {
            return this;
        }
    }
}

Ausgabe:
Code :
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30

#Permutation
[1, 1, 2, 3]
[1, 1, 3, 2]
[1, 2, 1, 3]
[1, 2, 3, 1]
[1, 3, 1, 2]
[1, 3, 2, 1]
[2, 1, 1, 3]
[2, 1, 3, 1]
[2, 3, 1, 1]
[3, 1, 1, 2]
[3, 1, 2, 1]
[3, 2, 1, 1]
 
#Alle Permutationen über die Potenzmenge
[A]
[B]
[C]
[A, B]
[B, A]
[A, C]
[C, A]
[B, C]
[C, B]
[A, B, C]
[A, C, B]
[B, A, C]
[B, C, A]
[C, A, B]
[C, B, A]

Gruß Tom