Liste/Array ausgewählte Elemente kopieren

[Anaconda2016]

Hallo zusammen, ich programmiere gerade das erste Mal mit Python und probiere dabei den bekannten Deferred Acceptance Algorithm zu verändern.

Mein derzeitiges Problem ist es, dass ich zur Zeit verschiedene Elemente in einer Liste/Array/matrix duplizieren möchte, d.h. folgendes Array:

A= {'i1':['s1','s2','s3'],
'i2':['s1','s2','s3'],
'i3':['s3','s2','s3'],
's1':['i1','i2','i3'],
's2':['i1','i3','i2'],
's3':['i1','i2','i3']}

sollte danach so aussehen:
B= {'i1':['s1','s2','s3'],
'i2':['s1','s2','s3'],
'i3':['s3','s2','s3'],
's1':['i1','i1','i2','i2','i3','i3'],
's2':['i1','i3','i2'],
's3':['i1','i2','i3']}

in dem Fall ist 's1' also doppelt so groß geworden.

Ich hoffe es kann mir jemand helfen!

[BlackJack]

@Anaconda2016: Und nach welchen Kriterien soll das passieren? Und wo genau liegt dabei das Problem?

Das wird ja wohl nicht die Antwort sein, nach der Du suchst:

Code: Alles auswählen

In [2]: A
Out[2]: 
{'i1': ['s1', 's2', 's3'],
 'i2': ['s1', 's2', 's3'],
 'i3': ['s3', 's2', 's3'],
 's1': ['i1', 'i2', 'i3'],
 's2': ['i1', 'i3', 'i2'],
 's3': ['i1', 'i2', 'i3']}

In [3]: A['s1'].extend(['i2', 'i3', 'i3'])

In [4]: A
Out[4]: 
{'i1': ['s1', 's2', 's3'],
 'i2': ['s1', 's2', 's3'],
 'i3': ['s3', 's2', 's3'],
 's1': ['i1', 'i2', 'i3', 'i2', 'i3', 'i3'],
 's2': ['i1', 'i3', 'i2'],
 's3': ['i1', 'i2', 'i3']}

[Anaconda2016]

Die Bedinung vor ab ist, dass ich ein anderes array prüfe also z.b. c=[2,1,1] und diese dann zu den 's1','s2','s3' gehören, also quasi 'freie Plätze angibt', in diesem Fall ha 's1' zwei Plätze. Danach sollte dann unbedingt weiter die Reihenfolge beachtet werden, d.h. für B sollte zwingend 's1':['i1','i1','i2','i2','i3','i3'] dort stehen.

Das ganze sollte dann natürlich in einer Schleife automatisch passieren

[Sirius3]

@Anaconda2016: Durch Deinen zweiten Post wird mir auch nicht klarer, was Du eigentlich erreichen willst. Vielleicht sollten wir mal weg von der Datenstruktur gehen, denn die scheint mir für das Problem nicht optimal zu sein. Wie lautet das Problem, das Du versuchst zu lösen? Versuch also mal nicht Deinen Lösungsweg zu beschreiben, sondern in allgemein verständlicher Sprache jemandem zu erklären, der keine Ahnung hat, was Du hast und was Du willst. Du hast eine Anzahl von Plätzen, davon sind einige frei?

[Anaconda2016]

Im allgemeinen habe ich z.B. Aufgaben die einer Maschine zugewiesen werden müssen. Der einfachste Fall ist, dass eine Aufgabe einer Maschine zugewiesen werden soll. Dafür gibt es einen Algorithmus, der auch funktioniert:

Code: Alles auswählen

def GaleShapley(teacher,school,pref):
        rank={} 
        for s in school:
                rank[s]={}
                i=1
                for t in pref[s]:
                        rank[s][t]=i
                        i+=1
        #create a pointer to the next school to propose         
        prefptr={}
        for t in teacher:
                prefptr[t]=0
        freeteacher=list(teacher) #all teachers and schools are free
        numpartners=len(teacher) #length teacher
        D={} #Build dicitionary to assign
        #run the algorithm
        while freeteacher:
                t=freeteacher.pop() #last item of the list will be remove and return
                if prefptr[t]>numpartners: continue
                #ueberspringt den befehl wenn if erfüllt zur while schleife
                #get the highest ranked woman that has no been proposed to
                s=pref[t][prefptr[t]]
                prefptr[t]+=1
                if s not in D: D[s]=t
                else:
                        tprime=D[s]
                        if rank[s][t]<rank[s][tprime]:
                                D[s]= t
                                freeteacher.append(tprime)#Add tprime to the end of the list
                        else:
                                freeteacher.append(t)
        

        return D

#test    

if __name__=="__main__":
        theteacher= ['i1','i2','i3']
        theschool= ['s1','s2','s3']
        thepref= {'i1':['s1','s2','s3'],
                  'i2':['s1','s2','s3'],
                  'i3':['s3','s2','s3'],
                  's1':['i1','i2','i3'],
                  's2':['i1','i3','i2'],
                  's3':['i1','i2','i3']}
        eng=GaleShapley(theteacher, theschool, thepref)
        print eng

Mit der Ausgabe:{'s3': 'i3', 's2': 'i2', 's1': 'i1'}

Jetzt möchte ich das ganze so ändern, dass bestimmte Maschinen/Schulen mehr als eine Zuordnung erhalten können. Dafür ist es meine Idee eine kapazität einzuführen, die dann festlegt wie viele Aufgaben/Schüler jeder Schule zugewiesen werden kann.

[BlackJack]

@Anaconda2016: Hat jetzt erst einmal nichts direkt mit dem Problem zu tun, aber Du solltest die Namen alle mal überarbeiten. `teacher` und `school` stehen für mehrere Lehrer und mehrere Schulen, sollten also `teachers` und `schools` heissen. Dann kann man statt einzelner Buchstaben wie `s` und `t` auch verständliche Namen wie `school` und `teacher` verwenden — diesmal dann korrekt für jeweils eine Schule und einen Lehrer. `numpartners` und der Kommentar ``#get the highest ranked woman that has no been proposed to`` passen nicht zu Schulen und Lehrern und das wiederum passt nicht zu Maschinen und Aufgaben. Du vermischt hier offenbar drei Sätze von semantischen Namen zur Beschreibung eines Problems/einer Lösung. Das ist verwirrend.

Der Präfix `the` macht bei den Namen im Hauptprogramm keinen Sinn.

`prefs` könnte einen besseren Namen und eventuell eine Erklärung vertragen. Ist das gewollt/erlaubt das beim Schlüssel 'i3' im Wert zweimal 's3' vorkommt?

Die Formatierung (Einrückung und Leerraum) entspricht nicht dem Style Guide for Python Code.

Wenn Du da eine Kapazität einführen willst, dann müsste man wohl die `theschool`-Datenstruktur erweitern.

[snafu]

Den Schritt, um die Elemente einer Liste zu verdoppeln, würde ich so machen:

Code: Alles auswählen

old_list = [1, 2, 3]
new_list = sum(([e, e] for e in old_list), [])
print(new_list)  # -> [1, 1, 2, 2, 3, 3]

Sieht auf dem ersten Blick vielleicht etwas nach einem Hack aus, ist es aber IMHO nicht. Denn `sum()` bedeutet ja letztlich ein Addieren von Elementen. Und das Addieren von Listen ist in Python möglich: Es entspricht einem `.extend()`.

Es gäbe noch die Möglichkeit, die Schleife auszuschreiben:

Code: Alles auswählen

old_list = [1, 2, 3]
new_list = []
for e in old_list:
    new_list.extend([e, e])
print(new_list)  # -> [1, 1, 2, 2, 3, 3]

...oder das `itertools`-Modul zu verwenden:

Code: Alles auswählen

from itertools import chain

old_list = [1, 2, 3]
new_list = list(
    chain.from_iterable(
        [e, e] for e in old_list
    )
)
print(new_list)  # -> [1, 1, 2, 2, 3, 3]

Aber besonders die `itertools`-Variante schießt IMO hier über's Ziel hinaus.

[Sirius3]

@snafu: `sum` entspricht eben nicht einem `extend` sondern einem wiederholten Zusammenkopieren von Listen. Da sind Lösung 2 und 3 deutlich besser. Oder gleich zip verwenden:

Code: Alles auswählen

new_list = list(chain.from_iterable(izip(old_list, old_list)))

[BlackJack]

Wobei das alles jetzt nicht so wirklich zum Problem/Algorithmus vom OP passt.

[snafu]

@Sirius3
Mein Fehler. Ein ``list1 + list2`` erzeugt natürlich eine neue Liste und ist somit in einer Schleife eine ziemlich schlechte Idee. Wenn man das so macht, dann will man eigentlich den `+=`-Operator verwenden. Dafür könnte man dann folgenden Code nutzen:

Code: Alles auswählen

from functools import reduce
from operator import iadd

old_list = [1, 2, 3]
new_list = reduce(iadd, ([e, e] for e in old_list))
print(new_list)  # -> [1, 1, 2, 2, 3, 3]

Aber da würde ich die Variante 2 mit der Schleife wiederum bevorzugen, weil mir das mit `reduce()` vom Code her zu aufwändig wäre.

[BlackJack]

Der Code mal überarbeitet so dass er ”pythonischer” ist und Namen verwendet die für *eine* Semantik stimmig sind (Schulen/Lehrer):

Code: Alles auswählen

#!/usr/bin/env python
# coding: utf8
from __future__ import absolute_import, division, print_function


def gale_shapley(teachers, schools, preferences):
    if len(teachers) != len(schools):
        raise ValueError('`teachers` and `schools` have not the same length')
    
    rank = dict()
    for school in schools:
        rank[school] = dict(
            (teacher, i) for i, teacher in enumerate(preferences[school], 1)
        )

    teacher2school_index = dict.fromkeys(teachers, 0)
    unassigned_teachers = list(teachers)
    total_school_count = len(schools)
    school2teacher = dict()
    while unassigned_teachers:
        teacher = unassigned_teachers.pop()
        if teacher2school_index[teacher] <= total_school_count:
            # Get the highest ranked school that has not been assigned to.
            school = preferences[teacher][teacher2school_index[teacher]]
            teacher2school_index[teacher] += 1
            if school not in school2teacher:
                school2teacher[school] = teacher
            else:
                assigned_teacher = school2teacher[school]
                if rank[school][teacher] < rank[school][assigned_teacher]:
                    school2teacher[school] = teacher
                    unassigned_teachers.append(assigned_teacher)
                else:
                    unassigned_teachers.append(teacher)
    return school2teacher


def main():
    teachers = ['i1', 'i2', 'i3']
    schools = ['s1', 's2', 's3']
    preferences = {
        'i1': ['s1', 's2', 's3'],
        'i2': ['s1', 's2', 's3'],
        'i3': ['s3', 's2', 's3'],
        's1': ['i1', 'i2', 'i3'],
        's2': ['i1', 'i3', 'i2'],
        's3': ['i1', 'i2', 'i3'],
    }
    school2teacher = gale_shapley(teachers, schools, preferences)
    print(school2teacher)


if __name__ == '__main__':
    main()

[Anaconda2016]

Danke BlackJack für die Verbesserung.

Aber irgendwie habe ich das Problem ja immer noch nicht gelöst

[Anaconda2016]

Also wie schaffe ich es mit diesem Code:

Code: Alles auswählen

#!/usr/bin/env python
# coding: utf8
from __future__ import absolute_import, division, print_function


def gale_shapley(teachers, schools, preferences):
    if len(teachers) != len(schools):
        raise ValueError('`teachers` and `schools` have not the same length')
    
    rank = dict()
    for school in schools:
        rank[school] = dict(
            (teacher, i) for i, teacher in enumerate(preferences[school], 1)
        )

    teacher2school_index = dict.fromkeys(teachers, 0)
    unassigned_teachers = list(teachers)
    total_school_count = len(schools)
    school2teacher = dict()
    while unassigned_teachers:
        teacher = unassigned_teachers.pop()
        if teacher2school_index[teacher] <= total_school_count:
            # Get the highest ranked school that has not been assigned to.
            school = preferences[teacher][teacher2school_index[teacher]]
            teacher2school_index[teacher] += 1
            if school not in school2teacher:
                school2teacher[school] = teacher
            else:
                assigned_teacher = school2teacher[school]
                if rank[school][teacher] < rank[school][assigned_teacher]:
                    school2teacher[school] = teacher
                    unassigned_teachers.append(assigned_teacher)
                else:
                    unassigned_teachers.append(teacher)
    return school2teacher


def main():
    teachers = ['i1', 'i2', 'i3']
    schools = ['s1', 's2', 's3']
    preferences = {
        'i1': ['s1', 's2', 's3'],
        'i2': ['s1', 's2', 's3'],
        'i3': ['s3', 's2', 's1'],
        's1': ['i1', 'i2', 'i3'],
        's2': ['i1', 'i3', 'i2'],
        's3': ['i1', 'i2', 'i3'],
    }
    school2teacher = gale_shapley(teachers, schools, preferences)
    print(school2teacher)


if __name__ == '__main__':
    main()

Wie kann ich nun für die Schulen eine Kapzität einführen, sodass z.b. die Schule 's1' zwei Schüler aufnehmen kann? Wobei die Präferenzen dann gleich bleiben soll, was z.b. hieße: 's1':['i1','i1', 'i2', 'i2', 'i3', 'i3']

[DasIch]

Gale/Shapely ist eine Lösung für das Stable marriage problem. Das solltest du ja hoffentlich wissen. Wenn man sich mit dem Thema etwas beschäftigt, also den ganzen Wikipedia Artikel liest, dann kommt man zu Similar Problems und dort taucht unter hospitals/residents problem aka college admissions problem, dein Problem auf mit sehr vielen weiteren Informationen. Wenn du es damit nicht schafft das Problem zu lösen ist dass eine Sache aber einen Ansatz solltest du sicherlich hinbekommen.

[Anaconda2016]

Wie man das ganz theoretisch auf dem Blattpapier löst, ist mir schon klar, nur ich schaffe es nicht diese Vorgänge in Python zu implementieren, da ich vorher NIE mit Python gearbeitet habe bzw. nur wenig überhaupt mit Programmiersprachen gearbeitet habe.

[BlackJack]

@Anaconda2016: Wo liegt denn das konkrete Problem beim Umsetzen der ”Papierlösung” in Python? Wie sieht die Lösung auf dem Papier aus?

[Anaconda2016]

Auf dem Blatt Papier sieht es dann ja so aus, dass aus einem one-to-one matching ein many-to-one matching wird, der 'Deferred Acceptance Algorithm' läuft dort wie folgt ab:

Step 1: Each teacher proposes to her most preferred school. Each school tentatively
assigns its spots to its proposers one at a time in the order of its preference.
When all of its sports are tentatively assigned, it rejects all the propoers who remain
unassigned
In general, at Step k: Each teacher who was rejected in the previous step proposes
to her next preferred school. Each school considers the set of teachers it has
been holding and its new proposers. It tentatively assigns its spots to these teachers
one at a time in the order of its preference. When all of its spots are tentatively
assigned, it rejects all the proposers who remain unassigned.
The algorithm terminates when no student proposal is rejected.and each student
is assigned her final tentative assignment.

Man kann den bestehenden Algorithm dann (ohne Bedenken) so abändern, dass man nur die Kapazitäten für die Schule berücksichtigt(die nun neu dazu kommen, da ja eine Schule mehr als einen Teacher aufnehmen kann) und für die Schulen dann quasi pro Kapazität, die Preference Liste kopiert, sprich wenn s1 die Präferenzen (i1,i2,i3) hat, hat Schule s1 bei einer kapazität von 2 die Präferenzen (i1,i1,i2,i2,i3,i3). Hät Schule s1 eine Kapzität von 3 wären die Präferenzen (i1,i1,i1,i2,i2,i2,i3,i3,i3). Das ganze sollte jetzt das neue Programm berücksichtigen.

[BlackJack]

@Anaconda2016: In dem Fall hätte snafu dann aber doch schon mehrere Lösungen zum vervielfachen von solchen Einträgen gezeigt.

[snafu]

Hierzu noch eine rein LC-basierte Lösung:

Code: Alles auswählen

l = [1, 2, 3]
print([elem for pair in zip(l, l) for elem in pair])

[Anaconda2016]

hat sich erledigt, danke, beiträge können gelöscht werden