Algorithmus Floyd und Bentley

Aru · 21. November 2013 um 11:59

Hallo zusammen!

Meine Aufgabe ist die Implementierung eines Algorithmus, der von Floyd und Bentley entwickelt wurde. Auf StackOverflow wurde er (iterativ) folgendermaßen skizziert:

initialize set S to empty
for J := N-M + 1 to N do
    T := RandInt(1, J)
    if T is not in S then
        insert T in S
    else
        insert J in S

Ich soll das Ganze nun rekursiv implementieren, was ich so angegangen bin:

   {
      return sampleRec(s, new ArrayList<T>(), s.size() - k);
   }

   private static <T> List<T> sampleRec(List<T> s, List<T> newList, int m)
   {
      if (m < s.size())
      {
         int random = rnd.nextInt(m);
         if (newList.contains(s.get(random)))
         {
            newList.add(s.get(m));
         }
         else
         {
            newList.add(s.get(random));
         }
         return sampleRec(s, newList, m + 1);
      }
      return newList;
   }```

Jetzt stellt sich mir dabei die Frage, ob das wirklich "rekursiv" ist, und weiterhin, ob das nicht besser geht. Eine andere Lösung sieht so aus:

```private static <T> List<T> sampleRec(List<T> s, int m)
   {
      List<T> newList;

      if (m == s.size())
      {
         newList = new ArrayList<T>();
      }
      else
      {
         newList = sampleRec(s, m + 1);
         int random = rnd.nextInt(m);
         if (newList.contains(s.get(random)))
         {
            newList.add(s.get(m));
         }
         else
         {
            newList.add(s.get(random));
         }
      }
      return newList;
   }

Diese Lösung finde ich aber aus mehreren Gründen irgendwie nicht so prickelnd: Unter anderem, weil das Anlegen der Liste unnötig verkompliziert wird.

Ich wäre also um jeden Tipp dankbar, was sich verbessern lässt, und auch um Argumente, was für die eine Lösung, aber auch für die andere spricht.

SlaterB · 21. November 2013 um 13:18

im Pseudocode ist S das leere neue Set,
ungünstig dass du in deinem Code zwar auch Variable s hast als Set bzw. Liste, aber in einer anderen Funktion

im Pseudocode geht es doch auch um Zahlen an sich, wozu überhaupt das Set vom Typ T?
du könntest das in jedem Fall unterteilen:

den Algorithmus nur mit Zahlen ausführen, Indexe sammeln,
zu den gesammelten Indexen in einem nachgelagerten Schritt die zugehörtigen T-Elemente holen


         int random = rnd.nextInt(m);
         if (newList.contains(s.get(random)))
         {
            newList.add(s.get(m));
         }
         else
         {
            newList.add(s.get(random));
         }

ein if ohne else reicht, um gegebenfalls die int-Variable mit dem Wert m zu belegen,
die add-Zeile danach reicht einmal, nach dem if ist der richtige Index vorhanden,
nicht unnötig 2x schreiben, doppelten Code vermeiden

deine beiden Code-Varianten sind grundsätzlich austauschbar, kann man je nach Stil so oder so machen,
in der ersten Variante brauchst du keinen Rückgabewert für die Rekursion,
die vorgeschaltete Methode erzeugt die Liste für den zweiten Parameter, kann sie sich merken und am Ende zurückgeben

zur Hauptfrage nach der Rekursion fällt mir am wenigsten ein,
es ist eine simple for-Schleife, die kann man eben nur durch so eine Pseudo-Rekursion ähnlich abbilden,
ist richtig wenn auch nicht toll und geht nicht besser, denke ich

recht spät fällt mir auf:
in der zweiten Variante füllst du falsch herum, erst die großen Zahlen, später kleine,
das kann statistische Auswirkungen haben, das Ergebnis ändern,
denn neue Zahlen hängen von denen ab, die schon da sind,
gründlich testen, besser ganz auf Umkehr verzichten,

lieber mit hoher Zahl beginnen, auf 0 oder 1 runter gehen, Liste erzeugen, und im Rückbau mit immer größeren Zahlen befüllen,
braucht vielleicht (auch) eine vorgeschaltete Methode, falls die nicht eh schon da ist,
das m als Parameter sieht komisch aus, muss nicht wie bei Variante 1 auch irgendwo size()-k gerechnet werden?

Aru · 21. November 2013 um 14:02

Schon mal vielen Dank für deine Antwort!

im Pseudocode geht es doch auch um Zahlen an sich, wozu überhaupt das Set vom Typ T? du könntest das in jedem Fall unterteilen:

Das stimmt. Der Methodenrumpf ist allerdings vorgegeben, also kann ich da wenig dran ändern.

ein if ohne else reicht, um gegebenfalls die int-Variable mit dem Wert m zu belegen,
die add-Zeile danach reicht einmal, nach dem if ist der richtige Index vorhanden,
nicht unnötig 2x schreiben, doppelten Code vermeiden

Das werde ich auf jeden Fall ausbessern!

braucht vielleicht (auch) eine vorgeschaltete Methode, falls die nicht eh schon da ist,
das m als Parameter sieht komisch aus, muss nicht wie bei Variante 1 auch irgendwo size()-k gerechnet werden?

Für die zweite Version gilt genau die gleiche „vorgeschaltete Methode“ wie bei der ersten. Das geht aus meinem Post vielleicht nicht so hervor.

SlaterB · 21. November 2013 um 14:41

ist der Rumpf nicht der Code in der Methode?

falls nur die Signatur vorgegeben ist, etwa allein von der sowieso nur vorgeschalteten Methode,
dann könntest du es noch anders implementieren, aber muss ja nicht sein

 public static <T> List<T> sample(List<T> s, int k)
   {
      List<Integer> indexes = sampleRec(s.size(), s.size() - k);
      // build & return List<T>
   }

Marco13 · 21. November 2013 um 15:22

Vielleicht noch der Link: http://stackoverflow.com/questions/2394246/algorithm-to-select-a-single-random-combination-of-values
Aber durch Draufschauen verstehe ich nicht, warum er macht, was er soll… ggf. morgen mal ein Beispiel durchspielen…

Aru · 21. November 2013 um 16:11

[QUOTE=SlaterB]ist der Rumpf nicht der Code in der Methode?

falls nur die Signatur vorgegeben ist, etwa allein von der sowieso nur vorgeschalteten Methode,
dann könntest du es noch anders implementieren, aber muss ja nicht sein
[/QUOTE]

Meinte ich ja auch, sorry.

Aber durch Draufschauen verstehe ich nicht, warum er macht, was er soll… ggf. morgen mal ein Beispiel durchspielen…

Die Idee ist eigentlich relativ simpel: Wir behalten uns so viele Zahlen zum „Ausweichen“ vor, wie wir auch aus der Menge auswählen wollen.
Jedes Mal wählen wir dann eine Zahl zufällig aus der restlichen Menge und weiterhin eine „Ausweichzahl“: Ist die zufällig ausgewählte Zahl schon in der neuen Menge vorhanden, nehmen wir einfach unsere „Ausweichzahl“. Die „Ausweichzahlen“ verringern wir dann quasi jeden Schritt um eine, da wir ja etwa im letzten Schritt nur noch eine Zahl zum Ausweichen brauchen.

In der SO-Frage ist auch ein Link zu einem mathematischen Beweis, wen es interessiert: combinatorics - What's the proof of correctness for Robert Floyd's algorithm for selecting a single, random combination of values? - Mathematics Stack Exchange

Aru · 29. November 2013 um 04:09

Falls es noch mal irgendwen auf dieser Welt interessieren sollte, hier übrigens meine “finale” Lösung:


   private static <T> void checkArguments(final List<T> s, final int k)
   {
      if (s == null)
      {
         throw new IllegalArgumentException("s cannot be null.");
      }
      if (k >= s.size())
      {
         throw new IllegalArgumentException(
               "k must be smaller than the size of s");
      }
      if (k < 0)
      {
         throw new IllegalArgumentException("k may not be negative");
      }
   }

   public static <T> List<T> sample(final List<T> s, final int k)
   {
      checkArguments(s, k);
      return sampleRec(s, new ArrayList<T>(), s.size() - k);
   }

   public static <T> List<T> sampleIterative(final List<T> s, final int k)
   {
      checkArguments(s, k);

      List<T> newList = new ArrayList<>();
      for (int i = s.size() - k; i < s.size(); i++)
      {
         T random = s.get(RANDOM.nextInt(i));
         if (newList.contains(random))
         {
            random = s.get(i);
         }
         newList.add(random);
      }
      return newList;
   }

   private static <T> List<T> sampleRec(final List<T> s, final List<T> newList, final int m)
   {
      if (m < s.size())
      {
         T random = s.get(RANDOM.nextInt(m));
         if (newList.contains(random))
         {
            random = s.get(m);
         }
         newList.add(random);
         return sampleRec(s, newList, m + 1);
      }
      return newList;
   }```

Danke noch mal für die Hilfe!

SlaterB · 29. November 2013 um 04:52

die vorgeschaltete Methode von sampleRec heißt einfach nur sample, das ist ein unnötiger Fehler

und wie gesagt würde ich auf die Rückgabe verzichten wenn die Ergebnisliste bereits als Parameter mitgegeben wird, verwirrend

auch:

         return sampleRec(s, newList, m + 1);
      }
      return newList;

stände im if drin kein return beim rekursiven Aufruf, dann ginge es auch, dann wird nach dem if newList übergeben, ist ja eh dasselbe…

außerdem noch meinen weiteren Vorschlag zum Index eingebaut ergibt als Anschauung

public class Test
{
    public static void main(String[] args)
    {
        test(true);
        test(false);
    }

    static void test(boolean rec)
    {
        List<Integer> s = new ArrayList<Integer>();
        for (int i = 0; i <= 20; i++)
        {
            s.add(i);
        }
        int[] count = new int[s.size() + 1];
        int k = 5;
        for (int i = 0; i < 1000000; i++)
        {
            List<Integer> l = rec ? sample(s, k) : sampleIterative(s, k);
            for (Integer x : l)
            {
                count[x]++;
            }
        }
        System.out.println(Arrays.toString(count));

    }

    private static final Random RANDOM = new Random();

    private static <T>void checkArguments(final List<T> s, final int k)
    {
        if (s == null)
        {
            throw new IllegalArgumentException("s cannot be null.");
        }
        if (k >= s.size())
        {
            throw new IllegalArgumentException("k must be smaller than the size of s");
        }
        if (k < 0)
        {
            throw new IllegalArgumentException("k may not be negative");
        }
    }

    public static <T>List<T> sample(final List<T> s, final int k)
    {
        checkArguments(s, k);
        ArrayList<T> newList = new ArrayList<T>();
        sampleRec(s, newList, s.size() - k);
        return newList;
    }

    public static <T>List<T> sampleIterative(final List<T> s, final int k)
    {
        checkArguments(s, k);

        List<T> newList = new ArrayList<T>();
        for (int i = s.size() - k; i < s.size(); i++)
        {
            int index = RANDOM.nextInt(i);
            if (newList.contains(s.get(index)))
            {
                index = i;
            }
            newList.add(s.get(index));
        }
        return newList;
    }

    private static <T>void sampleRec(final List<T> s, final List<T> newList, final int m)
    {
        if (m >= s.size()) return;

        int index = RANDOM.nextInt(m);
        if (newList.contains(s.get(index)))
        {
            index = m;
        }
        newList.add(s.get(index));
        sampleRec(s, newList, m + 1);
    }

}

zudem kleine Statistik dabei, Ergebnisse zählen,
würde der rekursive Aufruf wie im ersten Posting weiter vorne in der Methode stehen dann ein deutlicher Unterschied wie vermutet,
aktuell beide Varianten gleich, richtige Reihenfolge

nun alles von mir gewünschte noch selber eingebaut
jetzt ganz am Ende, nachdem schon 3x überlegt ob ich soviel blah blah eigentlich posten sollte fällt mir doch noch ein Fehler auf, je nach Interpretation der Aufgabe

wie man an meiner Statistik sieht, sind die hinteren Zahlen etwas benachteiligt, die hinteren 5 für das Beispiel mit k = 5,
das liegt daran dass RANDOM.nextInt(15) nur Zahlen von 0 bis 14 liefert, nach der Aufgabenstellung soll es aber glaube ich auch der aktuell maximale Index selber sein

wenn man die Random-Parameter in beiden Varianten mit +1 ergänzt, dann hat das zwei Konsequenzen:

alle Zahlen nun gleichverteilt, immer günstig, gewiss gewollt
abweichende Verteilung bei umgekehrter Rekursionsreihenfolge noch extremer

edit:
+1 muss es sein

Aru · 29. November 2013 um 05:29

Wow, danke für all die Mühe, die du dir gibst.

wie man an meiner Statistik sieht, sind die hinteren Zahlen etwas benachteiligt, die hinteren 5 für das Beispiel mit k = 5,
das liegt daran dass RANDOM.nextInt(15) nur Zahlen von 0 bis 14 liefert, nach der Aufgabenstellung soll es aber glaube ich auch der aktuell maximale Index selber sein

Stimmt, das klingt logisch. Es ist ja völlig egal, ob die Zahl, die letztlich zum Ausweichen genutzt wird, direkt getroffen werden kann. Denn in der Liste ist sie ja auf keinen Fall. Und so gleicht sich auch hinterher wieder aus, dass sie in den ersten Zügen nicht dabei sein konnte.

Ich will mich nicht aus dem Fenster lehnen, aber ich bin mir eigentlich ziemlich sicher, dass das Ganze dann vom Dozenten falsch erklärt wurde. Aber vielleicht täuscht mich hier auch nur meine Erinnerung, von daher.