001package ball.util.stream; 002/*- 003 * ########################################################################## 004 * Utilities 005 * %% 006 * Copyright (C) 2008 - 2022 Allen D. Ball 007 * %% 008 * Licensed under the Apache License, Version 2.0 (the "License"); 009 * you may not use this file except in compliance with the License. 010 * You may obtain a copy of the License at 011 * 012 * http://www.apache.org/licenses/LICENSE-2.0 013 * 014 * Unless required by applicable law or agreed to in writing, software 015 * distributed under the License is distributed on an "AS IS" BASIS, 016 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 017 * See the License for the specific language governing permissions and 018 * limitations under the License. 019 * ########################################################################## 020 */ 021import ball.util.DispatchSpliterator; 022import java.util.Arrays; 023import java.util.Collection; 024import java.util.Collections; 025import java.util.LinkedList; 026import java.util.List; 027import java.util.Spliterator; 028import java.util.function.Consumer; 029import java.util.function.Predicate; 030import java.util.function.Supplier; 031import java.util.stream.IntStream; 032import java.util.stream.Stream; 033import java.util.stream.StreamSupport; 034import lombok.Getter; 035import lombok.NoArgsConstructor; 036import lombok.Setter; 037import lombok.ToString; 038import lombok.experimental.Accessors; 039 040import static java.util.Objects.requireNonNull; 041import static lombok.AccessLevel.PRIVATE; 042 043/** 044 * {@link Stream} implementaion that provides all combinations of a 045 * {@link List}. 046 * 047 * @param <T> The {@link List} element type. 048 * 049 * @author {@link.uri mailto:ball@hcf.dev Allen D. Ball} 050 */ 051public interface Combinations<T> extends Stream<List<T>> { 052 053 /** 054 * Method to get the {@link Stream} of combinations. Combinations will 055 * be streamed largest to smallest or smallest to largest depending on 056 * the relative magnitude of {@code size0} and {@code sizeN}. E.g., to 057 * stream largest to smallest specify {@code sizeN} that is greater than 058 * {@code size0}. 059 * 060 * @param size0 The combination size range start 061 * (inclusive). 062 * @param sizeN The combination size range end (inclusive). 063 * @param predicate The optional {@link Predicate} (may be 064 * {@code null}) specifying prerequisite 065 * requirement(s) for the combinations. Any 066 * path that does not match will be pruned. 067 * @param collection The {@link Collection} of elements to 068 * permute. 069 * @param <T> The {@link Collection} element type. 070 * 071 * @return The {@link Stream} of combinations. 072 */ 073 public static <T> Stream<List<T>> of(int size0, int sizeN, Predicate<List<T>> predicate, Collection<T> collection) { 074 SpliteratorSupplier<T> supplier = 075 new SpliteratorSupplier<T>() 076 .collection(collection) 077 .size0(size0).sizeN(sizeN) 078 .predicate(predicate); 079 080 return supplier.stream(); 081 } 082 083 /** 084 * Method to get the {@link Stream} of combinations. 085 * 086 * @param size The combination size. 087 * @param collection The {@link Collection} of elements to 088 * permute. 089 * @param <T> The {@link Collection} element type. 090 * 091 * @return The {@link Stream} of combinations. 092 */ 093 public static <T> Stream<List<T>> of(int size, Collection<T> collection) { 094 return of(size, size, null, collection); 095 } 096 097 /** 098 * {@link Combinations} {@link Spliterator} {@link Supplier}. 099 */ 100 @NoArgsConstructor(access = PRIVATE) @ToString 101 public static class SpliteratorSupplier<T> implements Supplier<Spliterator<List<T>>> { 102 @Getter @Setter @Accessors(chain = true, fluent = true) 103 private int characteristics = 104 Spliterator.IMMUTABLE | Spliterator.NONNULL | Spliterator.SIZED | Spliterator.SUBSIZED; 105 @Getter @Setter @Accessors(chain = true, fluent = true) 106 private Collection<? extends T> collection = null; 107 @Getter @Setter @Accessors(chain = true, fluent = true) 108 private int size0 = -1; 109 @Getter @Setter @Accessors(chain = true, fluent = true) 110 private int sizeN = -1; 111 @Getter @Setter @Accessors(chain = true, fluent = true) 112 private Predicate<List<T>> predicate = null; 113 114 public SpliteratorSupplier<T> size(int size) { 115 return size0(size).sizeN(size); 116 } 117 118 public Stream<List<T>> stream() { 119 return StreamSupport.<List<T>>stream(get(), false); 120 } 121 122 @Override 123 public Spliterator<List<T>> get() { 124 if (size0() == -1 && sizeN() == -1) { 125 size(collection.size()); 126 } else if (size0() == -1) { 127 size0(sizeN()); 128 } else if (sizeN() == -1) { 129 sizeN(size0()); 130 } 131 132 return new Start(); 133 } 134 135 private class Start extends DispatchSpliterator<List<T>> { 136 public Start() { 137 super(binomial(collection().size(), size0(), sizeN()), SpliteratorSupplier.this.characteristics()); 138 } 139 140 @Override 141 protected Spliterator<Supplier<Spliterator<List<T>>>> spliterators() { 142 List<Supplier<Spliterator<List<T>>>> list = new LinkedList<>(); 143 144 IntStream.rangeClosed(Math.min(size0(), sizeN()), Math.max(size0(), sizeN())) 145 .filter(t -> ! (collection.size() < t)) 146 .forEach(t -> list.add(() -> new ForSize(t))); 147 148 if (size0() > sizeN()) { 149 Collections.reverse(list); 150 } 151 152 return list.spliterator(); 153 } 154 155 @Override 156 public long estimateSize() { 157 return binomial(collection().size(), size0(), sizeN()); 158 } 159 160 @Override 161 public String toString() { 162 return collection() + "/" + Arrays.asList(size0(), sizeN()); 163 } 164 } 165 166 private class ForSize extends DispatchSpliterator<List<T>> { 167 private final int size; 168 169 public ForSize(int size) { 170 super(binomial(collection().size(), size), SpliteratorSupplier.this.characteristics()); 171 172 this.size = size; 173 } 174 175 @Override 176 protected Spliterator<Supplier<Spliterator<List<T>>>> spliterators() { 177 Supplier<Spliterator<List<T>>> supplier = 178 () -> new ForPrefix(size, new LinkedList<>(), new LinkedList<>(collection())); 179 180 return Stream.of(supplier).spliterator(); 181 } 182 183 @Override 184 public long estimateSize() { 185 return binomial(collection().size(), size); 186 } 187 188 @Override 189 public String toString() { 190 return collection() + "/" + Arrays.asList(size); 191 } 192 } 193 194 private class ForPrefix extends DispatchSpliterator<List<T>> { 195 private final int size; 196 private final List<T> prefix; 197 private final List<T> remaining; 198 199 public ForPrefix(int size, List<T> prefix, List<T> remaining) { 200 super(binomial(remaining.size(), size), SpliteratorSupplier.this.characteristics()); 201 202 this.size = size; 203 this.prefix = requireNonNull(prefix); 204 this.remaining = requireNonNull(remaining); 205 } 206 207 @Override 208 protected Spliterator<Supplier<Spliterator<List<T>>>> spliterators() { 209 List<Supplier<Spliterator<List<T>>>> list = new LinkedList<>(); 210 211 if (prefix.size() < size) { 212 for (int i = 0, n = remaining.size(); i < n; i += 1) { 213 List<T> prefix = new LinkedList<>(this.prefix); 214 List<T> remaining = new LinkedList<>(this.remaining); 215 216 prefix.add(remaining.remove(i)); 217 218 list.add(() -> new ForPrefix(size, prefix, remaining)); 219 } 220 } else if (prefix.size() == size) { 221 list.add(() -> new ForCombination(prefix)); 222 } else { 223 throw new IllegalStateException(); 224 } 225 226 return list.spliterator(); 227 } 228 229 @Override 230 public boolean tryAdvance(Consumer<? super List<T>> consumer) { 231 Predicate<List<T>> predicate = SpliteratorSupplier.this.predicate(); 232 233 return ((prefix.isEmpty() || (predicate == null || predicate.test(prefix))) 234 && super.tryAdvance(consumer)); 235 } 236 237 @Override 238 public long estimateSize() { 239 return binomial(remaining.size(), size); 240 } 241 242 @Override 243 public String toString() { 244 return prefix + ":" + remaining + "/" + Arrays.asList(size); 245 } 246 } 247 248 private class ForCombination extends DispatchSpliterator<List<T>> { 249 private final List<T> combination; 250 251 public ForCombination(List<T> combination) { 252 super(1, SpliteratorSupplier.this.characteristics()); 253 254 this.combination = requireNonNull(combination); 255 } 256 257 @Override 258 protected Spliterator<Supplier<Spliterator<List<T>>>> spliterators() { 259 Supplier<Spliterator<List<T>>> supplier = () -> Stream.of(combination).spliterator(); 260 261 return Stream.of(supplier).spliterator(); 262 } 263 264 @Override 265 public boolean tryAdvance(Consumer<? super List<T>> consumer) { 266 Predicate<List<T>> predicate = SpliteratorSupplier.this.predicate(); 267 268 return ((combination.isEmpty() || (predicate == null || predicate.test(combination))) 269 && super.tryAdvance(consumer)); 270 } 271 272 @Override 273 public String toString() { return String.valueOf(combination); } 274 } 275 } 276}