From 0229c16365e5d849857b30ef6bd6634f89913a4b Mon Sep 17 00:00:00 2001 From: Stefan Suhren Date: Thu, 20 Nov 2014 18:39:54 +0100 Subject: Assignment No.8 implemented non recursive FaB --- .../in/inf/java1/aufgabe8/FloydAndBentley.java | 218 ++++++++++++--------- .../fhswf/in/inf/java1/aufgabe8/LottoZiehung.java | 56 ------ .../in/inf/java1/aufgabe8/LottoZiehungMain.java | 51 +++++ 3 files changed, 181 insertions(+), 144 deletions(-) delete mode 100644 src/de/fhswf/in/inf/java1/aufgabe8/LottoZiehung.java create mode 100644 src/de/fhswf/in/inf/java1/aufgabe8/LottoZiehungMain.java (limited to 'src/de/fhswf/in') diff --git a/src/de/fhswf/in/inf/java1/aufgabe8/FloydAndBentley.java b/src/de/fhswf/in/inf/java1/aufgabe8/FloydAndBentley.java index 8ec8464..54dd863 100644 --- a/src/de/fhswf/in/inf/java1/aufgabe8/FloydAndBentley.java +++ b/src/de/fhswf/in/inf/java1/aufgabe8/FloydAndBentley.java @@ -1,88 +1,130 @@ -/** - * - */ -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 - * 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 List sample(List 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 ret = new ArrayList<>(k); - sampleRec(s, k, ret); - - return ret; - - } - - /** - * TODO Add method comment here - * - * @param - * @param s - * @param k - * @param ret - */ - private static void sampleRec(List s, int k, List 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); - - } -} +/** + * + */ +package de.fhswf.in.inf.java1.aufgabe8; + +import java.util.ArrayList; +import java.util.List; +import java.util.Random; + +/** + * Utility class for the Floyd and Bentley algorithm. + * + * @author $Author: $ + * @version $Revision: $, $Date: $ UTC + */ +public final class FloydAndBentley +{ + + private static Random rnd = new Random(); + + /** + * Private constructor for utility class. + * + */ + private FloydAndBentley() + { + } + + /** + * A function which chooses a sample from a List with the Floyd and Bentley + * algorithm. (Recursive algorithm) + * + * @param + * 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 sample. + */ + public static List sample(List 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 ret = new ArrayList<>(k); + sampleRec(s, k, ret); + + return ret; + + } + + /** + * The recursive implementation of the Floyd and Bentley algorithm. + * + * @param + * Type of the Lists. + * @param s + * The set from which the sample is chosen. + * @param k + * The number of items to be chosen. + * @param ret + * Return the sample. + */ + private static void sampleRec(List s, int k, List ret) + { + if (ret.size() >= k) + { + return; + } + + T val = s.get(rnd.nextInt(s.size() - (k - ret.size()))); + + if (ret.contains(val)) + { + val = s.get(s.size() - (k - ret.size())); + } + + ret.add(val); + + sampleRec(s, k, ret); + + } + + /** + * A function which chooses a sample from a List with the Floyd and Bentley + * algorithm. (Non recursive algorithm) + * + * @param + * 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 sample. + */ + public static List sample2(List 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 ret = new ArrayList<>(k); + + for (int i = 0; i < k; i++) + { + T val = s.get(rnd.nextInt(s.size() - (k - ret.size()))); + + if (ret.contains(val)) + { + val = s.get(s.size() - (k - ret.size())); + } + + ret.add(val); + } + + return ret; + } +} diff --git a/src/de/fhswf/in/inf/java1/aufgabe8/LottoZiehung.java b/src/de/fhswf/in/inf/java1/aufgabe8/LottoZiehung.java deleted file mode 100644 index 279345d..0000000 --- a/src/de/fhswf/in/inf/java1/aufgabe8/LottoZiehung.java +++ /dev/null @@ -1,56 +0,0 @@ -/** - * - */ -package de.fhswf.in.inf.java1.aufgabe8; - -import java.util.ArrayList; -import java.util.List; - -/** - * TODO Add comment here - * - * @author $Author: $ - * @version $Revision: $, $Date: $ UTC - */ -public final class LottoZiehung -{ - - /** - * TODO Add constructor comment here - * - */ - private LottoZiehung() - { - // TODO Auto-generated constructor stub - } - - /** - * TODO Add method comment here - * - * @param args - * Command line arguments. - */ - public static void main(String[] args) - { - // TODO Auto-generated method stub - - List lottoZahlen = new ArrayList<>(49); - - for (int i = 1; i <= 49; i++) - { - lottoZahlen.add(i); - } - - List ziehung = FloydAndBentley.sample(lottoZahlen, 7); - - Integer Sonderzahl = ziehung.get(6); - - ziehung.remove(6); - - ziehung.sort(null); - - System.out.println(ziehung + " SonderZahl: " + Sonderzahl); - - } - -} diff --git a/src/de/fhswf/in/inf/java1/aufgabe8/LottoZiehungMain.java b/src/de/fhswf/in/inf/java1/aufgabe8/LottoZiehungMain.java new file mode 100644 index 0000000..6524a29 --- /dev/null +++ b/src/de/fhswf/in/inf/java1/aufgabe8/LottoZiehungMain.java @@ -0,0 +1,51 @@ +/** + * + */ +package de.fhswf.in.inf.java1.aufgabe8; + +import java.util.ArrayList; +import java.util.List; + +/** + * Main class for the LottoZiehung. + * + * @author $Author: $ + * @version $Revision: $, $Date: $ UTC + */ +public final class LottoZiehungMain +{ + + /** + * Private constructor for utility class. + * + */ + private LottoZiehungMain() + { + } + + /** + * Main function of the package. + * + * @param args + * Command line arguments. + */ + public static void main(String[] args) + { + List lottoZahlen = new ArrayList<>(49); + + for (int i = 1; i <= 49; i++) + { + lottoZahlen.add(i); + } + + List ziehung = FloydAndBentley.sample(lottoZahlen, 7); + + Integer Sonderzahl = ziehung.get(6); + + ziehung.remove(6); + + ziehung.sort(null); + + System.out.println(ziehung + " SonderZahl: " + Sonderzahl); + } +} -- cgit v1.2.3-70-g09d2