Thomas Kramer

IT-COW | All posts tagged 'Algorithmus-von-Floyd-und-Bentley'

Der Algorithmus von Floyd und Bentley

By Administrator at Dezember 07, 2011 19:23
Filed Under: Algorithmen, Programmierung allgemein, Studium, Java

Eine Java-Aufgabe war den Algorithmus von Floyd und Bentley (1986) zu implementieren. Die besten (deutschsprachigen) Quellen die ich dazu gefunden habe sind folgende:

 

 

Es geht dabei darum eine zufällige Auswahl aus einer Menge zu bilden - der Algorithmus selbst ist eigentlich ganz einfach: Es werden zunächst eine Menge aus der gewählt wird, n für die Grösse dieser Menge und m für die Anzahl der Einträge, die aus der Gesamtmenge ausgewählt werden sollen, festgelegt.

 

Das Beispiel war mit den Lottozahlen 6 aus 49: n ist dann 49 und m ist gleich 6, dann wird zuerst in einer Rekursion m soweit verringert bis es auf eins ist - und n parallel ebenfalls:

 

49 - 6

48 - 5

47 - 4

46 - 3

45 - 2

44 - 1

 

Nach der ersten Rückkehr aus den Rekursionen wird eine Zufallszahl von 1-44 gebildet - wenn diese in der zurückzugebenden Menge noch nicht enthalten ist (beim ersten Durchlauf natürlich nicht) wird sie hinzugefügt. Wenn sie doch schon vorhanden wäre würde stattdessen n=44 der Auswahlmenge hinzugefügt.

 

Zweiter Durchlauf nach Rekursion: Es wird eine Zufallszahl von 1-45 gebildet - wenn diese in der zurückzugebenden Menge noch nicht enthalten ist wird sie hinzugefügt - ansonsten wird n=45 der Auswahlmenge beigemengt. Da im vorherigen Durchlauf nur zwischen Zahlen von 1-44 ausgewählt wurde kann 45 noch nicht enthalten sein! So geht das dann immer weiter.

 

Ein Unterschied zum Original-Algorithmus ist hier dass die Gesamtmenge mit übergeben wird - die Zufallszahl wird daher als Index auf diese Menge angewendet. Daher benötigt der eigentliche Algorithmus drei statt zwei Parametern.

 

Ein wichtiger Punkt war noch dass die Auswahlmenge nicht immer in den Rekursionen neu instanziiert werden soll, weil das unnötig ist. Daher lässt man die Rekursion sogar bis auf m=0 herunterlaufen statt bis auf m=1 - und bei m=0 erst wird die Rückgabemenge einmalig instanziiert. Davor muss nur der Variablenname bekannt sein!

 

Weiter unten ist sowohl eine rekursive als auch eine iterative Variante dieses Algorithmus aufgeführt. Wichtig war dem Dozenten dann noch dass in der Rekursion die Eingangsparameter nicht erneut überprüft werden sollten.

 

import java.util.ArrayList;
import java.util.List;
import java.util.Set;
import java.util.HashSet;

/**
 * Main-Klasse.
 *
 * @author $Author: Thomas Kramer
 * @version $Revision: 1.0 $, $Date: 06.12.2011 $ UTC
 */

public final class Main
{
   private static List<Integer> zahlen = new ArrayList<Integer>();

   private static Set<Integer> ergebnisMenge = new HashSet<Integer>();

   /**
    * leerer Konstruktor.
    *
    */

   private Main()
   {

   }

   /**
    *
    * Zufallszahl erzeugen mit Unter- und Obergrenze.
    *
    * @param low Untergrenze
    * @param high Obergrenze
    * @return Zufallszahl
    */

   public static int myRandomWithHigh(int low, int high)
   {
      if (low < 0)
      {
         throw new IllegalArgumentException("Parameter 'low' ungültig!");
      }
      if (high < 0)
      {
         throw new IllegalArgumentException("Parameter 'high' ungültig!");
      }
      high++;
      return (int) (Math.random() * (high - low) + low);
   }

   /**
    *
    * Algorithmus von Floyd und Benltey zur Auswahl von Zufallszahlen.
    *
    * rekursive Variante.
    *
    * @param s Liste
    * @param k Anzahl für Auswahlmenge
    * @return Auswahlmenge
    */

   public static <Integer> Set<Integer> sample(List<Integer> s, int k)
   {
      if (s.size() == 0)
      {
         throw new IllegalArgumentException("Liste 's' ungültig!");
      }
      if (k < 0)
      {
         throw new IllegalArgumentException("Parameter 'k' ungültig!");
      }

      return sample_rekursive(s, s.size(), k);
   }

   /**
    *
    * ausgelagerte Rekursion des Algorithmus von Floyd und Bentley.
    *
    * @param s Liste
    * @param n Anzahl für Liste
    * @param k Anzahl für Auswahlmenge
    * @return Auswahlmenge
    */

   public static <T> Set<T> sample_rekursive(List<T> s, int n, int k)
   {
      Set<T> result = null;

      /*
       * wenn mehr als eine Zufallszahl gewünscht ist, Set durch rekursiven
       * Aufruf füllen
       */

      if (k == 0)
      {
         result = new HashSet<T>();
      }
      else
      {
         result = sample_rekursive(s, n - 1, k - 1);
         T z = s.get(myRandomWithHigh(0, n - 1));
         if (!result.contains(z))
         {
            result.add(z);
         }
         else
         {
            result.add(s.get(n - 1));
         }
      }
      return result;
   }

   /**
    *
    * Algorithmus von Floyd und Bentley zur Auswahl von Zufallszahlen.
    *
    * iterative Variante.
    *
    * @param s Liste
    * @param k Anzahl für Auswahlmenge
    * @return Auswahlmenge
    */

   public static <T> Set<T> sample2(List<T> s, int k)
   {
      if (s.size() == 0)
      {
         throw new IllegalArgumentException("Liste 's' ungültig!");
      }
      if (k < 0)
      {
         throw new IllegalArgumentException("Parameter 'k' ungültig!");
      }

      Set<T> result = new HashSet<T>();
     
      T z;
      int n = (s.size() - k + 1);
      Integer count = 1;
     
      while (count != (k + 1))
      {
          z = s.get(myRandomWithHigh(0, n - 1));
          if (!result.contains(z))
          {
             result.add(z);
          }
          else
          {
             result.add(s.get(n - 1));
          }
                 
        count++;
        n++;
      }

      return result;
   }

   /**
    * Main-Methode.
    *
    * @param args
    *           Aufrufparameter
    */

   public static void main(String[] args)
   {
      /* Set füllen */
      Integer zahlenArray[] = { 23, 34, 55, 32, 11, 22, 33, 78 };
      for (int i = 0; i <= (zahlenArray.length - 1); i++)
      {
         zahlen.add(zahlenArray[i]);
      }

      Integer auswahlMenge = 3;
      ergebnisMenge.clear();
      ergebnisMenge = sample2(zahlen, auswahlMenge);
      for (Integer zahl : ergebnisMenge)
      {
         System.out.println(zahl);
      }
      System.out.println("Anzahl: " + ergebnisMenge.size());

      /* Ziehung der Lottozahlen */
      Lottozahlen lz = new Lottozahlen();
      lz.ziehen();
      System.out.println("\nLottozahlen: ");
      for (Integer zahl : lz.lottozahlen())
      {
         System.out.println(zahl);
      }
      System.out.println("Zusatzzahl: " + lz.zusatzZahl());
   }
}

 

import java.util.ArrayList;

/**
 *
 * Lottozahlenziehung.
 *
 * @author Thomas Kramer
 * @version $Revision:  $, $Date:  $ UTC
 */

public class Lottozahlen
{
    static final int MIN_NUMBER = 1;
    static final int MAX_NUMBER = 49;
    static final int ANZAHL = 6;
 
    private ArrayList<Integer> zahlenPool;   
    private Integer[] gezogeneZahlen;
    private Integer   gezogeneZusatzZahl;
       
    /**
     * Standard-Konstruktor.
     */

    public Lottozahlen()
    {      
        /* Zahlenpool füllen mit Zahlen von 1 - 49 */
        zahlenPool = new ArrayList<Integer>();
        for (int i = MIN_NUMBER; i <= MAX_NUMBER; i++)
        {
            zahlenPool.add(i);
        }
       
        /* instanziieren */
        gezogeneZahlen = new Integer[ ANZAHL ];
        gezogeneZusatzZahl = MIN_NUMBER - 1;       
    }   
   
    /**
     * gezogene Lottozahlen.
     *
     * @return Array
     */

    public Integer[] lottozahlen()
    {
        if (gezogeneZahlen.length == 0 || gezogeneZusatzZahl == 0)
        {
            ziehen();
        }
        return gezogeneZahlen;
    }

    /**
     * Zusatzzahl zurückgeben.
     *
     * @return Die Zusatzzahl.
     */

    public int zusatzZahl()
    {
        if (gezogeneZusatzZahl == 0)
        {
            ziehen();
        }
        return gezogeneZusatzZahl;
    }

   /**
    *
    * neue Lottozahlenziehung.
    *
    */

    public void ziehen()
    {
        /* 6 aus 49 ziehen aus Zahlenpool, und in ein Array umwandeln */
        Main.sample(zahlenPool, ANZAHL).toArray(gezogeneZahlen);   
        /* eine Zahl ziehen, in Array umwandeln und erste Zahl auswählen */
        gezogeneZusatzZahl = (Integer) (Main.sample(zahlenPool, 1).toArray()[0]);     
       
        /* Array sortieren */
        java.util.Arrays.sort(gezogeneZahlen);       
    }
   
}

 

Monats-Liste