001/* 002 * Licensed to the Apache Software Foundation (ASF) under one or more 003 * contributor license agreements. See the NOTICE file distributed with 004 * this work for additional information regarding copyright ownership. 005 * The ASF licenses this file to You under the Apache License, Version 2.0 006 * (the "License"); you may not use this file except in compliance with 007 * the License. You may obtain a copy of the License at 008 * 009 * http://www.apache.org/licenses/LICENSE-2.0 010 * 011 * Unless required by applicable law or agreed to in writing, software 012 * distributed under the License is distributed on an "AS IS" BASIS, 013 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 014 * See the License for the specific language governing permissions and 015 * limitations under the License. 016 */ 017package org.apache.commons.collections4.iterators; 018 019import java.util.ArrayList; 020import java.util.Arrays; 021import java.util.Collection; 022import java.util.HashMap; 023import java.util.Iterator; 024import java.util.List; 025import java.util.Map; 026import java.util.NoSuchElementException; 027import java.util.Objects; 028 029/** 030 * This iterator creates permutations of an input collection, using the 031 * Steinhaus-Johnson-Trotter algorithm (also called plain changes). 032 * <p> 033 * The iterator will return exactly n! permutations of the input collection. 034 * The {@code remove()} operation is not supported, and will throw an 035 * {@code UnsupportedOperationException}. 036 * <p> 037 * NOTE: in case an empty collection is provided, the iterator will 038 * return exactly one empty list as result, as 0! = 1. 039 * 040 * @param <E> the type of the objects being permuted 041 * 042 * @since 4.0 043 */ 044public class PermutationIterator<E> implements Iterator<List<E>> { 045 046 /** 047 * Permutation is done on these keys to handle equal objects. 048 */ 049 private final int[] keys; 050 051 /** 052 * Mapping between keys and objects. 053 */ 054 private final Map<Integer, E> objectMap; 055 056 /** 057 * Direction table used in the algorithm: 058 * <ul> 059 * <li>false is left</li> 060 * <li>true is right</li> 061 * </ul> 062 */ 063 private final boolean[] direction; 064 065 /** 066 * Next permutation to return. When a permutation is requested 067 * this instance is provided and the next one is computed. 068 */ 069 private List<E> nextPermutation; 070 071 /** 072 * Standard constructor for this class. 073 * @param collection the collection to generate permutations for 074 * @throws NullPointerException if coll is null 075 */ 076 public PermutationIterator(final Collection<? extends E> collection) { 077 Objects.requireNonNull(collection, "collection"); 078 keys = new int[collection.size()]; 079 direction = new boolean[collection.size()]; 080 Arrays.fill(direction, false); 081 int value = 1; 082 objectMap = new HashMap<>(); 083 for (final E e : collection) { 084 objectMap.put(Integer.valueOf(value), e); 085 keys[value - 1] = value; 086 value++; 087 } 088 nextPermutation = new ArrayList<>(collection); 089 } 090 091 /** 092 * Indicates if there are more permutation available. 093 * @return true if there are more permutations, otherwise false 094 */ 095 @Override 096 public boolean hasNext() { 097 return nextPermutation != null; 098 } 099 100 /** 101 * Returns the next permutation of the input collection. 102 * @return a list of the permutator's elements representing a permutation 103 * @throws NoSuchElementException if there are no more permutations 104 */ 105 @Override 106 public List<E> next() { 107 if (!hasNext()) { 108 throw new NoSuchElementException(); 109 } 110 111 // find the largest mobile integer k 112 int indexOfLargestMobileInteger = -1; 113 int largestKey = -1; 114 for (int i = 0; i < keys.length; i++) { 115 if (direction[i] && i < keys.length - 1 && keys[i] > keys[i + 1] || 116 !direction[i] && i > 0 && keys[i] > keys[i - 1]) { 117 if (keys[i] > largestKey) { // NOPMD 118 largestKey = keys[i]; 119 indexOfLargestMobileInteger = i; 120 } 121 } 122 } 123 if (largestKey == -1) { 124 final List<E> toReturn = nextPermutation; 125 nextPermutation = null; 126 return toReturn; 127 } 128 129 // swap k and the adjacent integer it is looking at 130 final int offset = direction[indexOfLargestMobileInteger] ? 1 : -1; 131 final int tmpKey = keys[indexOfLargestMobileInteger]; 132 keys[indexOfLargestMobileInteger] = keys[indexOfLargestMobileInteger + offset]; 133 keys[indexOfLargestMobileInteger + offset] = tmpKey; 134 final boolean tmpDirection = direction[indexOfLargestMobileInteger]; 135 direction[indexOfLargestMobileInteger] = direction[indexOfLargestMobileInteger + offset]; 136 direction[indexOfLargestMobileInteger + offset] = tmpDirection; 137 138 // reverse the direction of all integers larger than k and build the result 139 final List<E> nextP = new ArrayList<>(); 140 for (int i = 0; i < keys.length; i++) { 141 if (keys[i] > largestKey) { 142 direction[i] = !direction[i]; 143 } 144 nextP.add(objectMap.get(Integer.valueOf(keys[i]))); 145 } 146 final List<E> result = nextPermutation; 147 nextPermutation = nextP; 148 return result; 149 } 150 151 @Override 152 public void remove() { 153 throw new UnsupportedOperationException("remove() is not supported"); 154 } 155 156}