"Eingeklammerte" Abfolge in neue Liste schreiben

[robocode]

Hallo,
ich grübel schon seit paar Tagen über ein Problem, für das mir irgendwie der gedankliche Startpunkt fehlt.

Ich habe eine Liste k mit beliebigen Abfolgen der Punkte A und B, also z.B folgendermaßen:

k=[A1 , B1, B2, B3, A2, B4, A3, A4, B5, B6, B7, A5]

Die Liste startet und endet immer mit einem A-Punkt.
Nun möchte ich die Liste derart unterteilen, dass ich B-Punkte, die von A's eingeklammert werden, in eine neue Liste L_i schreibe. Im obigen Beispiel sähe das wie folgt aus:

L_1=[A1, B1, B2,B3, A2]
L_2=[A2, B4, A3]
L_3=[A4, B5, B6, B7, A5]

A's und B's sind Strings bei denen ich mit einer if Bedinung überprüfe, ob der erst Buchstabe 'A' oder 'B' ist. Ich komm jedoch nicht darauf, wie ich diese eingeklammerten Abfolgen erzeuge (und diese dann in neu-generierte Listen schreibe), da man ja bei Python irgendwie nich die [i+1]te Position überprüfen kann. Mir fehlen da irgendwie paar logische Abfolgen.

[EyDu]

A's und B's sind Strings bei denen ich mit einer if Bedinung überprüfe, ob der erst Buchstabe 'A' oder 'B' ist. Ich komm jedoch nicht darauf, wie ich diese eingeklammerten Abfolgen erzeuge (und diese dann in neu-generierte Listen schreibe), da man ja bei Python irgendwie nich die [i+1]te Position überprüfen kann. Mir fehlen da irgendwie paar logische Abfolgen.

Natürlich kann man das folgende Element testen. Das ist hier aber unnötig und kompliziert. Du weißt doch, dass du dich in einem von As umgebenem Abschnitt befindest. Für den aktuellen Abschnitt erstellst du dann einfach eine Liste und packst so lange neue Elemente rein, bis der Abschnitt mit einem anderen Element aus A beendet ist. Dann packst du diese liste in eine Liste L und startest mit einer neuen Liste von As.

Aber mal anders gefragt: Wo kommen die Daten her und warum haben die eine solche Form? Vielleicht lässt sich das Problem auch schöner lösen.

[robocode]

Es handelt sich um eine Abfolge von Koordinatenpunkten, die jeweils einen Kommentar besitzen die die Art des Punktes festlegt.
Ich glaube ich tue mir schwer, den von dir genannten Abschnitt zu definieren. Wie könnte so eine Definition für das obige Beispiel lauten?

[Sirius3]

@robocode: Du brauchst zu jedem Zeitpunkt zwei Listen, eine Liste, die die Elemente sammelt und eine die die Listen sammelt. Jetzt mußt Du nur noch entscheiden, wann welches Element zu welcher Liste hinzugefügt wird, und wann Du eine neue Liste anfängst.

[robocode]

So hab jetzt mal bisschen rumgebastelt und bin auf folgendes gekommen:

Code: Alles auswählen

A="A"
B="B"
k=[A,B,B,B,A,B,A,B,A,B,A,B,A]                    #Beispiel-Liste
L=[]                                    #Liste in der die Punkte gesammelt werden
K=[]                                    #Liste, in der die Listen gesammelt werden
z=0
for i in k:
    if i==A and z==0:
        L.append(i)
        z=1
    
    elif i!=A:
        L.append(i)

    elif i==A and z==1:
        L.append(i)                     #Schluss-'A" wird an Liste L angehängt
        K.append(L)                     #Liste L wird in Liste K gespeichert
        L=[]                            #anschließend wird Liste L "resettet"
        L.append(i)                     #Schluss-A der vorigen Liste wird Anfangs-A der neuen Liste
        
     

print K -> [['A', 'B', 'B', 'B', 'A'], ['A', 'B', 'A'], ['A', 'B', 'A'], ['A', 'B', 'A'], ['A', 'B', 'A']]

Im Nachhinein weiß ich jedoch nicht genau ob ich das "z" das ich für den Start reinprogrammiert habe wirklich brauche.

[Hyperion]

Im Nachhinein weiß ich jedoch nicht genau ob ich das "z" das ich für den Start reinprogrammiert habe wirklich brauche.

Lol... YMMD

Mal im Ernst: Was sagt Dir das über die Namen Deines Codes? Die sind eben einfach schlecht! Klein und Groß-K‽ Ein kleines ``i`` nimmt man wenn überhaupt für Integerwerte - nicht für Strings. Und schon gar nicht als Abkürzung für ``item``

Für Deinen Ansatz brauchst Du das ``z``, da Du es als Flag zum Prüfen verwendest, ob Du innerhalb einer "B"-Sequenz bist oder ein abschließendes "A" kommt. Allerdings gibt es für Wahrheitswerte den Datentyp ``bool`` in Python mit den zugehörigen Literalen ``True`` und ``False``. Also nutze diese statt "1" und "0" - auch wenn sie tatsächlich denselben Wahrheitsgehalt haben!

Du kannst musst den Zustand aber auch nicht explizit in einer Variable "mitschleppen". Denk doch mal drüber nach, was Du an Information aus dem letzten gelesenem bzw. gespeicherten Zeichen gewinnen kannst. Vielleicht reicht das als Tipp, um das ganze eleganter zu machen

[Sirius3]

@robocode: und bedenke, wie Du mit der letzten Liste umgehen willst.

[thorius]

eine Möglichkeit wäre über die Liste zu iterieren und beim Auftreten von Element A* nach dem folgenden A* zu suchen. Alles dazwischen entpräche einem L_*.

Code: Alles auswählen

k=['A1', 'B1', 'B2', 'B3', 'A2', 'B4', 'A3', 'A4', 'B5', 'B6', 'B7', 'A5']
l=[]
for i,_ in enumerate(k):
    if k[i].startswith("A"):    # das erste auftreten von A finden
        for j,_ in enumerate(k[i+1:]):   # einen zähler danach
            if k[j+i+1].startswith("A"):   # das nächste A finden
                l.append(k[i:j+i+2])     # und die liste an l anhängen
                break
print(l)

eine andere Möglichkeit wäre die Position aller A* Elemente zu suchen und dann Päärchen mit Start und Endpunkt zu bilden:

Code: Alles auswählen

k=['A1', 'B1', 'B2', 'B3', 'A2', 'B4', 'A3', 'A4', 'B5', 'B6', 'B7', 'A5']
pos_of_a=[]
for i,_ in enumerate(k):
    if k[i].startswith("A"):
        pos_of_a.append(i)  # erzeugt liste mit allen positionen von A

pair_of_a=[]
for i,_ in enumerate(pos_of_a[:-1]):   # letztes element auslassen
    pair_of_a.append([pos[i],pos[i+1]+1])  #generiert liste mit päärchen

l=[]
for i,j in pair_of_a:
    l.append(k[i,j])

print(l)

Die Schwachstelle bei beiden Beispielen ist, dass auch zwei A* Elemente ohne B* Elemente gefunden werden:
k=[A1 , B1, B2, B3, A2, B4, A3, A4, B5, B6, B7, A5]
Diese Aussnahme müsste man entsprechend ausschliessen.

zum Abschluss: zerreisst mich nicht in der Luft, das geht sicher auch eleganter .

[BlackJack]

Ich hätte folgendes im Angebot:

Code: Alles auswählen

from itertools import groupby
from operator import itemgetter


def group_points(points):
    def stamp():
        i = 0
        for point in points:
            if point.startswith('A'):
                i += 1
            yield (i, point)

    result = list()
    for i, group in groupby(stamp(), itemgetter(0)):
        assert i != 0
        grouped_points = [p for _, p in group]
        if len(result) > 1:
            result.append(grouped_points[0])
            yield result
        result = grouped_points


def main():
    points = [
        'A1', 'B1', 'B2', 'B3', 'A2', 'B4', 'A3', 'A4', 'B5', 'B6', 'B7', 'A5'
    ]
    for group in group_points(points):
        print group


if __name__ == '__main__':
    main()

[Hyperion]

Ich biete hier konventionell dieses an:

Code: Alles auswählen

def make_routes(points):
    result = []
    group = []
    for point in points:
        group.append(point)
        if len(group) > 1 and "A" in point:
            result.append(group)
            group = [point]
    return result

points = ['A1', 'B1', 'B2', 'B3', 'A2', 'B4', 'A3', 'A4', 'B5', 'B6', 'B7', 'A5']
make_routes(points)
>
[['A1', 'B1', 'B2', 'B3', 'A2'],
 ['A2', 'B4', 'A3'],
 ['A3', 'A4'],
 ['A4', 'B5', 'B6', 'B7', 'A5']]

Wobei man sagen muss, dass das dritte Pärchen nur aus "A"s besteht... allerdings ist das iirc nie spezifiziert worden, ob die rausgefiltert werden müssen oder nicht

@BlackJack: Narf... elegant! Ich habe auch sofort an ``groupby`` gedacht, bin aber nicht auf den Trick mit der Closure-Funktion gekommen

@thorius: Deine erste Variante hat eine quadratische Laufzeit - das ist suboptimal Außerdem nutzt Du ``enumerate`` nicht "richtig". Du willst ja oft das Item haben - wieso wirfst Du es über ``_`` dann weg?

[robocode]

@Hyperion: Gruppen die nur aus A's bestehen sollen nicht betrachtet werden. Wie könnte man die bei deinem Vorschlag herausfiltern?

Wo siehst du - abgesehen von den zugegebenermaßen schlechten Namensgebungen - Probleme in meinem Code?

[EyDu]

Schreibe dafür einfach eine weitere Funktion. Die geht dann das Ergebnis durch und filtert Listen aus nur As aus.

[Hyperion]

Wo siehst du - abgesehen von den zugegebenermaßen schlechten Namensgebungen - Probleme in meinem Code?

Schrieb ich doch: Namen + Typ des Flags (Mache aus dem Integerwert einen Booleschen!) Ansonsten ist das algorithmisch vollkommen ok

Zum Rausfiltern mit nur "A"-Gruppen brauchst Du eine weitere Bedingung *vor* der bisherigen, die u.a. auf die "Länge == 2" prüft. Die bisherige kann man daran per ``elif`` anschließen.

[pillmuncher]

Oder funktional-reaktiv...
Ergebnis zB:

Code: Alles auswählen

[['A1', 'B3', 'A2'],
 ['A3', 'B4', 'A4'],
 ['A4', 'B5', 'B6', 'B7', 'A5'],
 ['A6', 'B8', 'A7'],
 ['A7', 'B9', 'B10', 'A8'],
 ['A8', 'B11', 'A9'],
 ['A9', 'B12', 'A10'],
 ['A12', 'B13', 'B14', 'A13'],
 ['A13', 'B15', 'A14'],
 ['A14', 'B16', 'B17', 'A15'],
 ['A16', 'B18', 'B19', 'B20', 'B21', 'A17'],
 ['A17', 'B22', 'B23', 'A18'],
 ['A19', 'B24', 'B25', 'A20'],
 ['A21', 'B26', 'B27', 'B28', 'B29', 'B30', 'B31', 'A22'],
 ['A22', 'B32', 'B33', 'A23'],
 ['A23', 'B34', 'A24'],
 ['A24', 'B35', 'A25'],
 ['A26', 'B36', 'A27'],
 ['A31', 'B37', 'A32'],
 ['A32', 'B38', 'A33'],
 ['A34', 'B39', 'B40', 'A35'],
 ['A35', 'B41', 'B42', 'A36'],
 ['A36', 'B43', 'B44', 'A37'],
 ['A38', 'B45', 'B46', 'B47', 'B48', 'A39'],
 ['A41', 'B49', 'B50', 'B51', 'B52', 'B53', 'B54', 'A42']]

[pillmuncher]

Oder so:

Code: Alles auswählen

#!/usr/bin/env python3
# -*- coding: utf-8

from itertools import count, tee
from random import choice
from pprint import pprint

def pairwise(iterable):
    a, b = tee(iterable)
    next(b, None)
    return zip(a, b)

def get_points():
    cis = [['A', count(1)], ['B', count(1)]]
    yield 'A0'
    for _ in range(99):
        c, i = choice(cis)
        yield '{}{}'.format(c, next(i))
    yield 'A100'

def main():
    def get_result(points):
        def get_row(pairs=pairwise(points)):
            for x, y in pairs:
                if y.startswith('B'):
                    yield x
                elif x.startswith('B'):
                    yield x
                    yield y
                    return
        while True:
            row = list(get_row())
            if not row:
                return
            yield row
    pprint(list(get_result(get_points())))

if __name__ == '__main__':
    main()

[pillmuncher]

Oder monadisch:

Code: Alles auswählen

#!/usr/bin/env python3
# -*- coding: utf-8


from itertools import count, filterfalse, tee
from random import choice
from pprint import pprint


class Stream:

    def __init__(self, iterable):
        self.iterable = iter(iterable)

    def __iter__(self):
        return self

    def __next__(self):
        return next(self.iterable)

    def bind(self, mfunc):
        return mfunc(self.iterable)

    def map(self, project):
        return Stream(project(each) for each in self.iterable)

    def filter(self, pred):
        return Stream(filter(pred, self.iterable))

    def filterfalse(self, pred):
        return Stream(filterfalse(pred, self.iterable))

    def pairwise(self):
        a, b = tee(self.iterable)
        next(b, None)
        return Stream(zip(a, b))

    def split(self, pred):
        def splitter():
            acc = []
            for item in self.iterable:
                acc.append(item)
                if pred(item):
                    yield acc
                    acc = []
            if acc:
                yield acc
        return Stream(splitter())


def points():
    cis = [['A', count(1)], ['B', count(1)]]
    yield 'A0'
    for _ in range(99):
        c, i = choice(cis)
        yield '{}{}'.format(c, next(i))
    yield 'A100'


def main():
    result = list(
        Stream(points())
        .pairwise()
        .filterfalse(lambda x: x[0].startswith('A') and x[1].startswith('A'))
        .split(lambda x: x[1].startswith('A'))
        .map(lambda xs: [x[0] for x in xs] + list(xs[-1][1:]))
    )
    pprint(result)


if __name__ == '__main__':
    main()

[pillmuncher]

Nachdem ich es etwas ausgearbeitet habe (hier), habe ich noch eine Lösung gefunden:

Code: Alles auswählen

#!/usr/bin/env python3
# -*- coding: utf-8

from random import choice
from pprint import pprint

from streams import Stream, first, second, unstar

def points(n):
    return Stream.chain(
        Stream.once((0, 'A')),
        Stream.join(
            Stream.repeat('A').enumerate(start=1),
            Stream.repeat('B').enumerate(start=1),
            scheduler=choice,
        ).take(n - 1),
        Stream.once((n, 'A')),
    ).map(unstar('{1}{0}'.format))

def is_even(n):
    return n % 2 == 0

@unstar
def combine_window(left_as, bs, right_as):
    return left_as[-1:] + bs + right_as[:1]

def main():
    pprint(list(
        points(100)
        .groupby(first)
        .map(second, list)
        .window(size=3)
        .filter_by_index(is_even)
        .map(combine_window)
    ))

if __name__ == '__main__':
    main()

Ergebnis zB:

Code: Alles auswählen

[['A1', 'B1', 'A2'],
 ['A2', 'B2', 'B3', 'A3'],
 ['A6', 'B4', 'B5', 'A7'],
 ['A8', 'B6', 'B7', 'A9'],
 ['A10', 'B8', 'A11'],
 ['A12', 'B9', 'B10', 'A13'],
 ['A14', 'B11', 'B12', 'B13', 'A15'],
 ['A15', 'B14', 'B15', 'A16'],
 ['A18', 'B16', 'B17', 'A19'],
 ['A19', 'B18', 'A20'],
 ['A20', 'B19', 'B20', 'A21'],
 ['A21', 'B21', 'B22', 'B23', 'B24', 'B25', 'A22'],
 ['A23', 'B26', 'B27', 'A24'],
 ['A26', 'B28', 'B29', 'B30', 'B31', 'A27'],
 ['A29', 'B32', 'A30'],
 ['A30', 'B33', 'B34', 'A31'],
 ['A31', 'B35', 'B36', 'B37', 'A32'],
 ['A32', 'B38', 'A33'],
 ['A35', 'B39', 'A36'],
 ['A37', 'B40', 'A38'],
 ['A38', 'B41', 'B42', 'A39'],
 ['A40', 'B43', 'A41'],
 ['A41', 'B44', 'B45', 'A42'],
 ['A42', 'B46', 'B47', 'B48', 'A43'],
 ['A43', 'B49', 'A44'],
 ['A44', 'B50', 'A45'],
 ['A45', 'B51', 'B52', 'A46'],
 ['A46', 'B53', 'A100']]

Auch sowas geht damit:

Code: Alles auswählen

#!/usr/bin/env python3
# -*- coding: utf-8

from streams import Stream

def computation(a, b, c):
    return a + b * c

def main():
    s1 = Stream.count()
    s2 = Stream.count().map(lambda n: 10 ** n)
    s3 = Stream.repeat(5)
    print(computation(1, 2, 3))
    print(list(computation(s1, s2, s3).take(10)))

if __name__ == '__main__':
    main()

Ergebnis:

Code: Alles auswählen

7
[5, 51, 502, 5003, 50004, 500005, 5000006, 50000007, 500000008, 5000000009]

Das wäre die Pull-Seite (Iteratoren). Als nächstes müsste man die Push-Seite (Observers/Observables und Behaviours) in Angriff nehmen und es asynchron machen. RxPY löst zwar dieses Problem bereits, kommt aber leider in diesem schrecklichen Microsoft-Jargon daher, der es für mich völlig unbenutzbar macht. Beispiel:

| window(self, window_openings=None, window_closing_selector=None)
| Projects each element of an observable sequence into zero or more
| windows.
|
| Keyword arguments:
| :param Observable window_openings: Observable sequence whose elements
| denote the creation of windows.
| :param types.FunctionType window_closing_selector: [Optional] A function
| invoked to define the closing of each produced window. It defines the
| boundaries of the produced windows (a window is started when the
| previous one is closed, resulting in non-overlapping windows).
|
| :returns: An observable sequence of windows.
| :rtype: Observable[Observable]

Was soll denn "Observable sequence whose elements denote the creation of windows." überhaupt bedeuten? Mich erinnert das an Heidegger: "Aus dem Spiegel-Spiel des Gerings des Ringes ereignet sich das Dingen des Dinges". Aber Heidegger kann man verstehen, wenn man bei jemand vernünftigen, zB. Ernst Tugendhat nachliest, was das heißen soll. Für Microsoftisch hab ich so jemanden noch nicht gefunden.

[pillmuncher]

Das Problem lässt sich auch so formulieren:

Gegeben eine Sequenz von Punkten der Form A\d+([AB]\d+)+B\d+. Selektiere daraus alle Sublisten der Form A\d+(B\d+)+A\d+.

(ab jetzt schreibe ich vereinfachend A für A\d+ bzw. B für B\d+)

Die beiden äußeren Elemente stammen offensichtlich aus Sublisten der Form A+, wobei das linke das letzte ELement und das rechte das erste Element einer solchen Liste darstellt. Nennen wir eine B-Folge bs und die links (vorher) bzw. rechts (nachher) davon stehenden A-Folgen left_as und right_as. Wenn die Folgen Listen sind, kann man die Subliste AB+A in Python formulieren als

Code: Alles auswählen

left_as[-1:] + bs + right_as[:1]

Aufeinanderfolgende Sublisten kann man über ein gleitendes Fenster erzeugen:

Code: Alles auswählen

a b c d e f g ...
a b c
  b c d
    c d e
      d e f
        e f g
          ...

Aus einer Folge (A+B+)+A+ erhalten wir, wenn wir gleitende Fenster der Länge drei erzeugen, abwechselnd Listen der Form A+B+A+ und B+A+B+. An letzteren sind wir nicht interessiert und können sie ausfiltern. Dazu verwenden wir Slicing:

Code: Alles auswählen

for left_as, bs, right_as in islice(windows, 0, None, 2):
    ...

windows bekommen wir, indem wir ein Python-Rezept anwenden, das auch unter dem Namen nwise() bekannt ist:

Code: Alles auswählen

windows = zip(
    *(islice(each, i, None) for i, each in enumerate(tee(groups, 3)))
)

groups ist dabei die Folge sich strikt abwechselnder Sublisten, die jeweils nur A- und B-Punkte besitzen. Eine solche Folge können wir mit groupby() erzeugen:

Code: Alles auswählen

groups = (
    list(group) for key, group in groupby(points, itemgetter(0))
)

Die Folge points von Punkten setze ich mal als bereits existierend voraus. Wenn man dann alles zusammensetzt, kommt diese Generator-Funktion heraus:

Code: Alles auswählen

from itertools import groupby, islice, tee
from operator import itemgetter

def make_rows(points):
    groups = (
        list(group) for key, group in groupby(points, itemgetter(0))
    )
    windows = zip(
        *(islice(each, i, None) for i, each in enumerate(tee(groups, 3)))
    )
    for left_as, bs, right_as in islice(windows, 0, None, 2):
        yield left_as[-1:] + bs + right_as[:1]

Verwenden kann man sie dann zB. so:

Code: Alles auswählen

def main():
    from pprint import pprint
    pprint(list(make_rows(make_points(100))))

if __name__ == '__main__':
    main()

Dadurch, dass an den kritischen Stellen ausschließlich Generatoren verwendet werden, ist das ganze äußerst speichersparend. Auch sehr große Punktfolgen lassen sich damit leicht verarbeiten, sofern auch diese über einen Generator erzeugt werden.

Die Funktion make_rows() kann man schöner und übersichtlicher machen, wenn man meine experimentelle Streams-Bibliothek[*] verwendet. Dann würde sie so aussehen:

Code: Alles auswählen

from streams import Stream
from combinators import first, unstar

@unstar
def combine_window(left_as, bs, right_as):
    return left_as[-1:] + bs + right_as[:1]

def make_rows(points):
    return (
        points
        .groupby(first)
        .window(size=3)
        .slice(step=2)
        .map(combine_window)
    )

Auch ohne Dokumentation kann man ziemlich leicht feststellen, was hier passiert, finde ich.

Mit streams lassen sich auch die Punkte erzeugen:

Code: Alles auswählen

import random

def points(n):
    return Stream.chain(
        Stream.once((0, 'A')),
        Stream.join(
            Stream.repeat('A').enumerate(start=1),
            Stream.repeat('B').enumerate(start=1),
            scheduler=random.choice,
        ).take(n - 1),
        Stream.once((n, 'A')),
    ).map(unstar('{1}{0}'.format))

Hier das Programm im Ganzen.


[*] Mit der Bibliothek habe ich angefangen, nachdem über das Problem in diesem Thread nachgedacht habe und mich gefragt habe, wie man das soweitmöglich mit bloßen Transformationen hinbekommt.