(Semi-mathematischer) Pseudo-Code: Auswahl von Elementen einer Menge



  • Hallo,
    gibt es eine einigermaßen anerkannte (bzw. einleuchtende) Notation für die Auswahl (und Benennung) beliebiger Elemente aus einer Menge? Konkret: Ich muss häufiger Algorithmen in so pseudo-mathematischem Code schreiben und weiß jedesmal nicht, wie sich die Zeilen 3 und 7 am sinnvollsten darstellen lassen.

    X <- getSomeSet();
    while ( X != empty ) {
      select some x in X // 1
      X <- X \ {x}
      Y <- doSomething(x);
      if (|Y| = 2) {
        select the two elements (x, y) in Y // 2
        return doSomething(x, y);
      }
    }
    


  • sei x, y element Y???



  • oder besser {x,y} Teilmenge Y.
    Besser ist es, weil in meinem ersten vorschlag, x und y nicht notwendig verschieden sein müssen. Das kannst noch dazu schreiben mit x != y. Bei mengen sind aber afaik die Elemente durch die definition verschieden.



  • element schrieb:

    Bei mengen sind aber afaik die Elemente durch die definition verschieden.

    Nö. Aber {x, x} = {x}.



  • Mir gefällt choose besser als select, also: Choose distinct x,y from X. Oder sowas in der Art.



  • Choose gefällt mir persönlich nicht so gut, weil es hier ja nix zu wählen gibt. Zumindest im zweiten Fall. Im ersten Fall isses gut. Im zweiten Fall würde versuchen das ganze über {x,y} = Y zu formalisieren. Eventuell schon im if:
    Y={x,y} (x \ne y) dann sind die Elemente automatisch benannt.



  • Jester schrieb:

    Eventuell schon im if:
    Y={x,y} (x \ne y) dann sind die Elemente automatisch benannt.

    So hatte ich mir das bisher auch gedacht, wusste aber nicht, ob das "funktioniert". Brauche ich denn das x \ne y hier? Das = garantiert mir doch, dass nur zwei Elemente in der Menge sind und die Tatsache, dass es sich um eine Menge handelt garantiert mir, dass x und y ungleich sind. Oder mache ich hier gerade einen Denkfehler?

    Bashar schrieb:

    Mir gefällt choose besser als select, also: Choose distinct x,y from X. Oder sowas in der Art.

    Gut, choose gefällt mir auch besser. Allerdings ist mein Ziel ja eine Notation, die möglichst ohne umschreibende Worte auskommt.

    Für

    select some x in X // 1
    X <- X \ {x}
    

    habe ich mittlerweile folgendes gefunden:

    X <- X \ {x} for some x in X
    

    Nicht so schön finde ich daran, dass man nicht gut erkennt, dass ein neues x eingeführt wird. Mit der Tatsache, dass das x auch gleich aus der Menge entfernt wird könnte ich noch leben.



  • HumeSikkins schrieb:

    Das = garantiert mir doch, dass nur zwei Elemente in der Menge sind und die Tatsache, dass es sich um eine Menge handelt garantiert mir, dass x und y ungleich sind. Oder mache ich hier gerade einen Denkfehler?

    Üblicherweise sagt man, dass {x,x} und {x} die selbe Menge bezeichnen. Dann erzwingst Du damit nur, dass Du höchstens 2 Elemente hast. Wenn ich v_1,...,v_n habe und sagen will, dass die paarweise verschieden sind schreibe ich auch manchmal |{v_1,..,v_n}| = n. Insbesondere wäre eine Definition, die doppeltes Aufzählen sehr schwierig zu handhaben, wenn es Variable gäbe, etwa a und b. Dann darf man {a,b} nur schreiben, wenn a ungleich b ist und müßte ne Fallunterscheidung für a=b in der Notation einführen.


Log in to reply