blob: 8ec84649a8877d058b62b5143f52a01f45f6cffd (
plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
|
/**
*
*/
package de.fhswf.in.inf.java1.aufgabe8;
import java.util.ArrayList;
import java.util.List;
import java.util.Random;
/**
* TODO Add comment here
*
* @author $Author: $
* @version $Revision: $, $Date: $ UTC
*/
public final class FloydAndBentley
{
private static Random rnd = new Random();
/**
* TODO Add constructor comment here
*
*/
private FloydAndBentley()
{
// TODO Auto-generated constructor stub
}
/**
* A function which chooses a sample from a List with the Floyd and Bentley
* algorithm.
*
*
* @param <T>
* Type of the Lists.
* @param s
* The set from which the sample is chosen.
* @param k
* The number of items to be chosen.
* @return Return the ordered sample.
*/
public static <T> List<T> sample(List<T> s, int k)
{
if (s.isEmpty())
{
throw new IllegalArgumentException("Set is empty");
}
if (k > s.size())
{
throw new IllegalArgumentException("k is bigger than the Set");
}
List<T> ret = new ArrayList<>(k);
sampleRec(s, k, ret);
return ret;
}
/**
* TODO Add method comment here
*
* @param <T>
* @param s
* @param k
* @param ret
*/
private static <T> void sampleRec(List<T> s, int k, List<T> ret)
{
if (ret.size() >= k)
{
return;
}
T val = s.get(rnd.nextInt(s.size() - ((k - ret.size()) - 1)));
if (ret.contains(val))
{
val = s.get(s.size() - ((k - ret.size()) - 1));
}
ret.add(val);
sampleRec(s, k, ret);
}
}
|
