1 /* 2 * Licensed to the Apache Software Foundation (ASF) under one or more 3 * contributor license agreements. See the NOTICE file distributed with 4 * this work for additional information regarding copyright ownership. 5 * The ASF licenses this file to You under the Apache License, Version 2.0 6 * (the "License"); you may not use this file except in compliance with 7 * the License. You may obtain a copy of the License at 8 * 9 * http://www.apache.org/licenses/LICENSE-2.0 10 * 11 * Unless required by applicable law or agreed to in writing, software 12 * distributed under the License is distributed on an "AS IS" BASIS, 13 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 14 * See the License for the specific language governing permissions and 15 * limitations under the License. 16 */ 17 18 package org.apache.commons.rng.sampling; 19 20 import java.util.List; 21 import java.util.ListIterator; 22 import java.util.RandomAccess; 23 import java.util.ArrayList; 24 25 import org.apache.commons.rng.UniformRandomProvider; 26 27 /** 28 * Sampling from a {@link List}. 29 * 30 * <p>This class also contains utilities for shuffling a {@link List} in-place.</p> 31 * 32 * @since 1.0 33 */ 34 public final class ListSampler { 35 /** 36 * The size threshold for using the random access algorithm 37 * when the list does not implement java.util.RandomAccess. 38 */ 39 private static final int RANDOM_ACCESS_SIZE_THRESHOLD = 4; 40 41 /** 42 * Class contains only static methods. 43 */ 44 private ListSampler() {} 45 46 /** 47 * Generates a list of size {@code k} whose entries are selected 48 * randomly, without repetition, from the items in the given 49 * {@code collection}. 50 * 51 * <p> 52 * Sampling is without replacement; but if the source collection 53 * contains identical objects, the sample may include repeats. 54 * </p> 55 * 56 * <p> 57 * Sampling uses {@link UniformRandomProvider#nextInt(int)}. 58 * </p> 59 * 60 * @param <T> Type of the list items. 61 * @param rng Generator of uniformly distributed random numbers. 62 * @param collection List to be sampled from. 63 * @param k Size of the returned sample. 64 * @throws IllegalArgumentException if {@code k <= 0} or 65 * {@code k > collection.size()}. 66 * @return a shuffled sample from the source collection. 67 */ 68 public static <T> List<T> sample(UniformRandomProvider rng, 69 List<T> collection, 70 int k) { 71 final int n = collection.size(); 72 final PermutationSampler p = new PermutationSampler(rng, n, k); 73 final List<T> result = new ArrayList<>(k); 74 final int[] index = p.sample(); 75 76 for (int i = 0; i < k; i++) { 77 result.add(collection.get(index[i])); 78 } 79 80 return result; 81 } 82 83 /** 84 * Shuffles the entries of the given array, using the 85 * <a href="http://en.wikipedia.org/wiki/Fisher-Yates_shuffle#The_modern_algorithm"> 86 * Fisher-Yates</a> algorithm. 87 * 88 * <p> 89 * Sampling uses {@link UniformRandomProvider#nextInt(int)}. 90 * </p> 91 * 92 * @param <T> Type of the list items. 93 * @param rng Random number generator. 94 * @param list List whose entries will be shuffled (in-place). 95 */ 96 @SuppressWarnings({"rawtypes", "unchecked"}) 97 public static <T> void shuffle(UniformRandomProvider rng, 98 List<T> list) { 99 if (list instanceof RandomAccess || list.size() < RANDOM_ACCESS_SIZE_THRESHOLD) { 100 // Shuffle list in-place 101 for (int i = list.size(); i > 1; i--) { 102 swap(list, i - 1, rng.nextInt(i)); 103 } 104 } else { 105 // Shuffle as an array 106 final Object[] array = list.toArray(); 107 for (int i = array.length; i > 1; i--) { 108 swap(array, i - 1, rng.nextInt(i)); 109 } 110 111 // Copy back. Use raw types. 112 final ListIterator it = list.listIterator(); 113 for (final Object item : array) { 114 it.next(); 115 it.set(item); 116 } 117 } 118 } 119 120 /** 121 * Shuffles the entries of the given array, using the 122 * <a href="http://en.wikipedia.org/wiki/Fisher-Yates_shuffle#The_modern_algorithm"> 123 * Fisher-Yates</a> algorithm. 124 * 125 * <p> 126 * The {@code start} and {@code pos} parameters select which part 127 * of the array is randomized and which is left untouched. 128 * </p> 129 * 130 * <p> 131 * Sampling uses {@link UniformRandomProvider#nextInt(int)}. 132 * </p> 133 * 134 * @param <T> Type of the list items. 135 * @param rng Random number generator. 136 * @param list List whose entries will be shuffled (in-place). 137 * @param start Index at which shuffling begins. 138 * @param towardHead Shuffling is performed for index positions between 139 * {@code start} and either the end (if {@code false}) or the beginning 140 * (if {@code true}) of the array. 141 */ 142 public static <T> void shuffle(UniformRandomProvider rng, 143 List<T> list, 144 int start, 145 boolean towardHead) { 146 // Shuffle in-place as a sub-list. 147 if (towardHead) { 148 shuffle(rng, list.subList(0, start + 1)); 149 } else { 150 shuffle(rng, list.subList(start, list.size())); 151 } 152 } 153 154 /** 155 * Swaps the two specified elements in the list. 156 * 157 * @param <T> Type of the list items. 158 * @param list List. 159 * @param i First index. 160 * @param j Second index. 161 */ 162 private static <T> void swap(List<T> list, int i, int j) { 163 final T tmp = list.get(i); 164 list.set(i, list.get(j)); 165 list.set(j, tmp); 166 } 167 168 /** 169 * Swaps the two specified elements in the array. 170 * 171 * @param array Array. 172 * @param i First index. 173 * @param j Second index. 174 */ 175 private static void swap(Object[] array, int i, int j) { 176 final Object tmp = array[i]; 177 array[i] = array[j]; 178 array[j] = tmp; 179 } 180 }