Buchstaben aufgabe

[mto99]

Mittwoch 30. Oktober 2019, 17:46
Hallo Leute,

Ich habe eine Aufgabe, die ich nicht gelöst bekomme.

Die Aufgabe lautet:
Schreiben Sie eine Python-Funktion, die eine Liste aller Worte aus Kleinbuchstaben (keine Umlaute) erzeugt, die aus genau 4 Buchstaben bestehen und die keine drei direkt aufeinanderfolgenden Konsonanten enthält.

Ich sitze schon seit 2 Tagen davor, aber ich kann es nicht lösen.

Vielen Dank schon im Voraus.

[sparrow]

Du hast doch auf deinen anderen Beitrag bereits eine Antwort bekommen. Statt die Frage noch einmal zu kopieren, solltest du die einfach beantworten.

[Sirius3]

Warum glaubst Du, dass nochmal die selbe Frage zu stellen, Dir eine andere Antwort als das letzte mal einbringt?

Was hast Du schon versucht? Welche Gedanken hast Du Dir schon für die Lösung gemacht?

[__blackjack__]

@mto99: Wo konkret hakt es denn? Was sind denn Kleinbuchstaben ohne Umlaute genau? Das ß ist ja ein Kleinbuchstabe. Und das hier sind auch alles Kleinbuchstaben: "αβγδεζηθικλμνξοπρςτυφχψω". Und was sind Konsonanten? Zählt da beispielsweise das "y" dazu oder nicht?

Ich habe das mal für Kleinbuchstaben aus dem deutschsprachigen Raum ohne Umlaute aber mit ß und den Vokalbuchstaben "aeiouy" in der Programmiersprache Vala umgesetzt. Das Ergebnis sind 225.828 Worte.

Code: Alles auswählen

public class Strings : Object {
    
    private string[] alphabet;
    private size_t element_length;
    private size_t _size;
    
    public size_t size { get { return this._size; } }
    
    public Strings (string alphabet, size_t element_length) {
        this.alphabet = new string[alphabet.char_count ()];
        int offset = 0;
        unichar c;
        for (var i = 0; alphabet.get_next_char (ref offset, out c); ++i) {
            this.alphabet[i] = c.to_string ();
        }
        
        this.element_length = element_length;
        this._size = (size_t) Math.pow (this.alphabet.length, this.element_length);
    }
    
    public new string get (size_t index)
        requires (0 <= index < this.size)
        ensures (result.char_count () == this.element_length)
    {
        var sb = new StringBuilder.sized(this.element_length * 2);
        for (int i = 0; i < this.element_length; ++i) {
            sb.append (this.alphabet[index % this.alphabet.length]);
            index /= this.alphabet.length;
        }
        return sb.str;
    }
}


static bool is_alpha(string s) {
    int offset = 0;
    unichar c;
    while (s.get_next_char (ref offset, out c)) {
        if (! c.isalpha ()) return false;
    }
    return true;
}


static Regex create_consonant_regex (string alphabet, string vowels, int count)
    requires (is_alpha (alphabet) && is_alpha (vowels) && count > 0)
{
    var sb = new StringBuilder ("[");
    int offset = 0;
    unichar c;
    while (alphabet.get_next_char (ref offset, out c)) {
        assert (c.isalpha ());
        if (vowels.index_of_char (c) == -1) sb.append_unichar (c);
    }
    sb.append_printf("]{%d}", count);
    
    return new Regex(sb.str);
}


static void main ()
{
    var alphabet = "abcdefghijklmnopqrsßtuvwxyz";
    var consonant_regex = create_consonant_regex (alphabet, "aeiouy", 3);
    foreach (var s in new Strings (alphabet, 4)) {
        if (! consonant_regex.match (s)) stdout.printf ("%s\n", s);
    }
}

In Python ist das deutlich weniger Code wenn man die Module der Standardbibliothek benutzt. Anstelle der `Strings`-Klasse in dem Vala-Programm kann man das Kreuzprodukt aus 4× dem Alphabet nämlich mit einer Funktion aus dem `itertools`-Modul aufzählen lassen.

[nezzcarth]

Vala sieht man nicht so oft, schick

@mto99: Wo konkret hakt es denn? Was sind denn Kleinbuchstaben ohne Umlaute genau? Das ß ist ja ein Kleinbuchstabe. Und das hier sind auch alles Kleinbuchstaben: "αβγδεζηθικλμνξοπρςτυφχψω". Und was sind Konsonanten? Zählt da beispielsweise das "y" dazu oder nicht?

Diese Aufgaben beruhen halt meistens auf der Annahme, dass es entweder keinen Unterschied zwischen Lauten und Buchstaben gibt, oder dass eine eins zu eins Beziehung zwischen diesen besteht (grade im Deutschen sind die Beziehungen sehr komplex). Beides ist aber streng genommen für das für das Deutsche nicht korrekt. Laute können Konsonanten sein, Buchstaben (bzw. 'Graphe') nicht; sie sind nur ihre grafische Repräsentation. Ich vermute, dass im Sinne der Aufgabe zum Beispiel "schi" nicht zulässig wäre, weil 's', 'c', und 'h' vermutlich als drei "Konsonanten" angesehen würden, dabei besteht das Wort lautlich eigentlich nur aus einem Konsonanten (repräsentiert durch den Trigraph "sch") und einem Vokal. Wenn man die Aufgabe unter den vereinfachenden Annahmen implementiert (und ggf. die schwierigen Fälle wie 'y' usw. weglässt), ist sie ja recht trivial. Wenn man es korrekt machen will, ist das aber gar nicht so einfach.

[mto99]

Hallo
bisjetzt habe ich diesen Code:

------------------------------------------------------------------------

Code: Alles auswählen

import random
def words():
    alphabet = random.choice("abcdefghijklmnopqrstuvwxyz")
    return alphabet
words()

number = 0
word = ""
while number < 4:
    number = number+1
    word = word + words()
print(word)

-------------------------------------------------------------

jedoch fehlen diese punkte:
1. es dürfen keine 3 konsonanten aufeinander folgen
2. Alle möglichen Wörter sollen zusammen in einer Liste ausgegeben werden

[mto99]

PS:
Die Wörter müssen auch keinen Sinn ergeben. Hauptsache keine 3 konsonanten hintereinander.

[nezzcarth]

Dann fang doch vielleicht im ersten Schritt mal an, deine Buchstaben in zwei Gruppen -- "Konsonanten" und "Vokale" -- zu teilen. Anschließend kannst du dir überlegen, wie du weiter vorgehst. Eine Möglichkeit ist zum Beispiel, zunächst alle möglichen vierbuchstabigen Kombinationen zu erzeug und dann in einem zweiten Schritt die herauszufiltern, die das Kriterium nicht erfüllen.

[__blackjack__]

@mto99: Beim Programmieren sind gute und treffende Namen wichtig. `words()` hat absolut nichts mit Worten zu tun, das liefert zufällig *einen* Buchstaben.

Funktionen sollte man Namen von Tätigkeiten geben, damit man sie von eher passiven Werten unterscheiden kann. Hinter `words` würde man keine Funktion sondern beispielsweise eine Liste mit Worten erwarten.

`alphabet` ist auch falsch, denn an den Namen wird kein Alphabet gebunden, sondern ebenfalls ein einzelner zufälliger Buchstabe.

Der Aufruf von `words()` gleich nach der Definition macht keinen Sinn, weil mit dem Rückgabwert dort nichts gemacht wird. Die Zeile hat keinen Effekt.

`number` ist überflüssig, denn das hat vor und nach jedem Schleifendurchlauf den Wert der Länge von `word` und diese Länge kann man mit der `len()`-Funktion ermitteln, die braucht man nicht noch einmal selber parallel dazu mitzählen.

Bei den ”arithmetischen” Operatoren gibt es auch eine Zuweisungsform, so dass man bei Audrücken der Form ``a = a <op> b`` auch ``a <op>= b`` schreiben kann. Also beispielsweise bei ``number = number + 1`` kürzer ``number += 1``.

Die Kleinbuchstaben aus dem ASCII-Bereich gibt es im `string`-Modul bereits als Konstante — die braucht man nicht selbst eintippen.

Code: Alles auswählen

import random
from string import ascii_lowercase


def get_random_charachter():
    return random.choice(ascii_lowercase)


def main():
    word = ""
    while len(word) < 4:
        word += get_random_charachter()

    print(word)


if __name__ == "__main__":
    main()

Zeichenketten durch wiederholtes ”addieren” von Teilen zu erstellen ist ineffizient in Programmiersprachen mit unversänderlichen Zeichenketten. Idiomatisch in Python ist das sammeln der Teilzeichenketten in einer Liste und am Ende dann mit der `str.join()`-Methode zusammensetzen. Statt einer Liste kann es auch ein beliebiges iterierbares Objekt sein, zum Beispiel auch ein Generatorausdruck:

Code: Alles auswählen

def main():
    word = "".join(get_random_charachter() for _ in range(4))
    print(word)

Der Ansatz mit dem zufällig generieren wird aber nichts bringen, denn Du brauchst ja *alle* Möglichkeiten und die zufällig zu generieren ginge zwar, ist aber extrem ineffizient, weil es um so länger dauert, je mehr Varianten man schon gefunden hat, die restlichen zufällig zu erzeugen.

Du wirst diese Worte also systematisch erzeugen müssen. Da gibt es ganz grob drei Varianten:

1) Eine rekursive Funktion die alle Worte erzeugt. Sozusagen der Klassiker.
2) Eine Funktion die aus einer ganzen Zahl *eine* der Varianten erzeugt, die man dann nacheinander mit Zahlen von 0 bis Anzahl der möglichen 4-stelligen Worte minus 1 aufruft. Das habe ich dem Vala-Programm gemacht.
3) Eine Funktion aus dem `itertools`-Modul verwenden. Ist am einfachsten.

[mto99]

hallo

Random Wörter erstellen habe ich hingekriegt, aber die Bedingung, dass keine 3 Konsonanten aufeinander folgen soll fehlt.

[nezzcarth]

Random Wörter erstellen habe ich hingekriegt, aber die Bedingung, dass keine 3 Konsonanten aufeinander folgen soll fehlt.

Es gibt 29!/(25!*4!) = 23.751 mögliche vierbuchstabige Wörter, die aus einem Alphabet mit 26 Buchstaben gebildet werden können. Diese alle zufällig zu erzeugen, ist konzeptuell unschön (auch wenn es nicht lange dauert) und skaliert nicht gut. Die Wörter systematisch zu erzeugen ist auch nicht so schwierig, insb. nicht, wenn man das itertools -Modul zur Hilfe nimmt. Was hast du dir denn bzgl. des Filterns überlegt? Eine Lösung wäre zum Beispiel ein passender regulärer Ausdruck.

[ThomasL]

Es gibt 29!/(25!*4!) = 23.751 mögliche vierbuchstabige Wörter, die aus einem Alphabet mit 26 Buchstaben gebildet werden können.

Ähm, für mich sind das 26**4 = 456976 Wörter, angefangen bei "aaaa" bis "zzzz" oder bin ich da auf dem Holzweg? Also ohne die Restriktion mit den 3 Konsonanten.

[mto99]

Random Wörter erstellen habe ich hingekriegt, aber die Bedingung, dass keine 3 Konsonanten aufeinander folgen soll fehlt.

Es gibt 29!/(25!*4!) = 23.751 mögliche vierbuchstabige Wörter, die aus einem Alphabet mit 26 Buchstaben gebildet werden können. Diese alle zufällig zu erzeugen, ist konzeptuell unschön (auch wenn es nicht lange dauert) und skaliert nicht gut. Die Wörter systematisch zu erzeugen ist auch nicht so schwierig, insb. nicht, wenn man das itertools -Modul zur Hilfe nimmt. Was hast du dir denn bzgl. des Filterns überlegt? Eine Lösung wäre zum Beispiel ein passender regulärer Ausdruck.

Hallo,
das ist ja der Punkt. Ich habe keinen Plan darüber.
ich weiß, klingt bischen sche**e.

[nezzcarth]

Es gibt 29!/(25!*4!) = 23.751 mögliche vierbuchstabige Wörter, die aus einem Alphabet mit 26 Buchstaben gebildet werden können.

Ähm, für mich sind das 26**4 = 456976 Wörter, angefangen bei "aaaa" bis "zzzz" oder bin ich da auf dem Holzweg? Also ohne die Restriktion mit den 3 Konsonanten.

Nein, bist du nicht, das ist richtig . Ich habe die Kombinationen falsch erzeugt (combinations_with_replacement, statt dem, was man eigentlich nehmen sollte).

[__blackjack__]

@mto99: Was heisst keinen Plan? Es wurden doch nun schon einige Lösungsansätze genannt. Und wenn ich das richtig verstanden habe, hast Du die erste Teilaufgabe, alle vierbuchstabigen Worte aus einem gegebenen Alphabet zu erzeugen, ja bereits gelöst‽ Per Zufall ist das natürlich so gar nicht effizient, aber wenn der Teil funktioniert, kannst Du ja erst einmal den Teil mit dem Filtern lösen, und danach die erste Teilaufgabe vielleicht noch mal sinnvoller angehen.

Stichwort für das filtern ist ja auch schon gefallen, und das habe ich im Vala-Programm auch so gemacht: Reguläre Ausdrücke. Da gibt es in der Python-Standard-Bibliothek ein Modul für, Dokumention zum Modul, und auch noch ein extra Howto-Dokument.

Teillösung 1 könnte eine Funktion sein, die ein Alphabet und eine Länge bekommt und alle Worte dieser Länge aus dem Alphabet erzeugt. Das hast Du ja schon. (Zeig doch mal.)

Teillösung 2 könnte eine Funktion sein, die ein Wort bekommt und entscheidet ob das drei aufeinanderfolgende Konsonantenbuchstaben enthält oder nicht.

Wobei man da vielleicht noch eine Funktion zwischenschieben könnte die ein Alphabet und Vokalbuchstaben bekommt und daraus dann die Konsonantenbuchstaben erstellt, denn das ist einfacher anzugeben und leichter verständlich wenn man nicht Alphabet und Konsonantenbuchstaben ins Programm schreibt, sondern Alphabet und Vokalbuchstaben, weil Vokalbuchstaben deutlich weniger sind.

[bords0]

Zeichenketten durch wiederholtes ”addieren” von Teilen zu erstellen ist ineffizient in Programmiersprachen mit unversänderlichen Zeichenketten. Idiomatisch in Python ist das sammeln der Teilzeichenketten in einer Liste und am Ende dann mit der `str.join()`-Methode zusammensetzen. Statt einer Liste kann es auch ein beliebiges iterierbares Objekt sein, zum Beispiel auch ein Generatorausdruck:

Code: Alles auswählen

def main():
    word = "".join(get_random_charachter() for _ in range(4))
    print(word)

Bei einer kleinen fixen Anzahl von Additionen dürfte es irrelevant sein, wie effizient das ist. Insbesondere gilt die Effizienzbetrachtung nur "asymptotisch", und für 4 bekomme ich tatsächlich das umgekehrte Ergebnis:

Code: Alles auswählen

In [3]: %timeit "".join(get_random_charachter() for _ in range(4))
11.6 µs ± 405 ns per loop (mean ± std. dev. of 7 runs, 100000 loops each)

In [4]: %timeit get_random_charachter() + get_random_charachter() + get_random_charachter() + get_random_charachter()
8.98 µs ± 292 ns per loop (mean ± std. dev. of 7 runs, 100000 loops each)

Der Klassiker auf dem Lernstand des OP wäre m.E. ein geschachtelte Schleife:

Code: Alles auswählen

for c1 in ascii_lowercase:
    for c2 in ascii_lowercase:
        word2 = c1 + c2
        for c3 in ascii_lowecase:
            word3 = word2 + c3
            < letzte Schleife nur angedeutet, OP soll ja auch noch was tun >
                < Prüfung, ob word[:3] oder word [1:] nur aus Konsonanten bestehen, ggf. ausgeben >

[Sirius3]

@bords0: beim Programmieren sollte man ja auch lernen, Dinge möglichst allgemeingültig auszudrücken. Deine Beispiele sind halt fix auf 4 Buchstaben ausgelegt, wenn man jetzt nach 5 oder 3 Buchstaben fragt, muß man quasi neu programmieren. Das sollte ein Anfänger halt von Anfang an richtig lernen. Deshalb sollten solche Aufgaben auch immer mit Fragen wie "mach das selbe mit 348239 Buchstaben" enden.

[__blackjack__]

@bords0: Ich schrieb deshalb auch nicht nur von Effizienz sondern auch von *idiomatischem* Python. Es kann sogar sein das man bei konkreten Python-Implementierungen gar keine Einbusse hat, weil die so clever sein können unveränderliche Zeichenketten *doch* einfach zu verändern wenn sie die Möglichkeit haben festzustellen das es a) nur *eine* Referenz auf die Zeichenkette gibt, und b) diese Referenz gleich nach der Veränderung durch die Veränderte Zeichenkette überschrieben würde. Weil man dann die Zeichenkette verändern kann ohne das es jemand merkt. Zeitmessungen können hier also irreführend sein. Gerade weil es bei nur 4 Zeichen nicht drauf ankommt was schneller ist, sollte man IMHO den ”pythonischeren” Weg wählen.

[henni31162]

ich habe mir kurz mal eine iterative Lösung geschnitzt und die zeigt mir 455905 von 456976 (26 ** 4) Möglichkeiten an. Geht bestimmt eleganter und effizienter, funktioniert aber

Code: Alles auswählen

vokale_ascii = [97, 101, 105, 111, 117]

count = 0
for i1 in range(97, 123):
    for i2 in range(97, 123):
        for i3 in range(97, 123):
            for i4 in range(97,123):
                if (i1 == i2 == i3) & (i1 not in vokale_ascii):
                    pass
                elif (i2 == i3 == i4) & (i2 not in vokale_ascii):
                    pass
                else:
                    count += 1
                    print("{}: {}{}{}{}".format(count, chr(i1), chr(i2), chr(i3), chr(i4)))

[__deets__]

In Python verknuepft man mit "and", nicht mit dem bitweisen "&". Und ich sehe jetzt nicht, dass die Aufgabenstellung erfuellt ist. Denn du pruefst nur, dass die drei Zeichen *gleich* und Konsonanten sind. Die muesstest du anpassen, damit sie prueft, ob alle drei fraglichen Indizes Vokale sind. Die Beobachtung, dass es nur zwei Positionen fuer das Auftreten geben kann ist aber ein wichtiger Schritt