Permutationen mit Iterator lazy generieren

[Thomas Darimont]

Hallo,

inspiriert durch den Beitrag:
http://www.tutorials.de/algorithmen...ute-force-algorithmus-fuer-permutationen.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)

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() {
			/*
			 * http://en.wikipedia.org/wiki/Permutation 
			 * 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:

#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