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 */ 017 018package org.apache.commons.rng.sampling; 019 020import java.util.List; 021import java.util.ArrayList; 022 023import org.apache.commons.rng.UniformRandomProvider; 024 025/** 026 * Sampling from a {@link List}. 027 * 028 * This class also contains utilities for shuffling a {@link List} in-place. 029 * 030 * @since 1.0 031 */ 032public class ListSampler { 033 /** 034 * Class contains only static methods. 035 */ 036 private ListSampler() {} 037 038 /** 039 * Generates a list of size {@code k} whose entries are selected 040 * randomly, without repetition, from the items in the given 041 * {@code collection}. 042 * 043 * <p> 044 * Sampling is without replacement; but if the source collection 045 * contains identical objects, the sample may include repeats. 046 * </p> 047 * 048 * @param <T> Type of the list items. 049 * @param rng Generator of uniformly distributed random numbers. 050 * @param collection List to be sampled from. 051 * @param k Size of the returned sample. 052 * @throws IllegalArgumentException if {@code k <= 0} or 053 * {@code k > collection.size()}. 054 * @return a shuffled sample from the source collection. 055 */ 056 public static <T> List<T> sample(UniformRandomProvider rng, 057 List<T> collection, 058 int k) { 059 final int n = collection.size(); 060 final PermutationSampler p = new PermutationSampler(rng, n, k); 061 final List<T> result = new ArrayList<T>(k); 062 final int[] index = p.sample(); 063 064 for (int i = 0; i < k; i++) { 065 result.add(collection.get(index[i])); 066 } 067 068 return result; 069 } 070 071 /** 072 * Shuffles the entries of the given array. 073 * 074 * @see #shuffle(UniformRandomProvider,List,int,boolean) 075 * 076 * @param <T> Type of the list items. 077 * @param rng Random number generator. 078 * @param list List whose entries will be shuffled (in-place). 079 */ 080 public static <T> void shuffle(UniformRandomProvider rng, 081 List<T> list) { 082 shuffle(rng, list, 0, false); 083 } 084 085 /** 086 * Shuffles the entries of the given array, using the 087 * <a href="http://en.wikipedia.org/wiki/Fisher-Yates_shuffle#The_modern_algorithm"> 088 * Fisher-Yates</a> algorithm. 089 * The {@code start} and {@code pos} parameters select which part 090 * of the array is randomized and which is left untouched. 091 * 092 * @param <T> Type of the list items. 093 * @param rng Random number generator. 094 * @param list List whose entries will be shuffled (in-place). 095 * @param start Index at which shuffling begins. 096 * @param towardHead Shuffling is performed for index positions between 097 * {@code start} and either the end (if {@code false}) or the beginning 098 * (if {@code true}) of the array. 099 */ 100 public static <T> void shuffle(UniformRandomProvider rng, 101 List<T> list, 102 int start, 103 boolean towardHead) { 104 final int len = list.size(); 105 final int[] indices = PermutationSampler.natural(len); 106 PermutationSampler.shuffle(rng, indices, start, towardHead); 107 108 final ArrayList<T> items = new ArrayList<T>(list); 109 for (int i = 0; i < len; i++) { 110 list.set(i, items.get(indices[i])); 111 } 112 } 113}