Lussen in lussen¶
Geneste lussen!
Lijsten¶
Een lijst is een reeks waarden op volgorde. Met één lus loop je er in één keer overheen.
scores = [88, 82, 91, 79, 83, 79, 86, 92, 77, 88, 93, 82, 85, 86, 92, 79]
def compute_sum(numbers):
"""Geeft de som van alle getallen in numbers terug."""
sum_values = 0
# ix is de gebruikelijke afkorting voor index
for ix in range(len(numbers)):
sum_values += numbers[ix]
return sum_values
def compute_avg(numbers):
"""Geeft het gemiddelde van de getallen in numbers terug."""
sum_list = compute_sum(numbers)
return sum_list / len(numbers)
compute_avg(scores)
85.125
assert compute_sum(scores) == 1362
assert compute_avg(scores) == 85.125
assert compute_sum([]) == 0
2D-lijsten¶
Een 2D-lijst is een lijst waarvan elk element zelf een lijst is. Zo krijg je rijen en kolommen.
Denk bijvoorbeeld aan spreadsheets …
[
["Naam", "Vraag 1", "Vraag 2", "Vraag 3", "Vraag 4"],
["Peter Been", 88, 82, 91, 79],
["Jasper Klein", 83, 79, 86, 92],
["Linda Buitendijk", 77, 88, 93, 82],
["Myrthe Zomer", 85, 86, 92, 79],
]
Afbeeldingen zijn rasters van pixels¶
Of natuurlijk afbeeldingen! Deze bestaan voornamelijk uit lijsten van pixels
[
[[255, 255, 255], [255, 255, 255]],
[[0, 0, 0], [0, 0, 0]],
[[255, 255, 255], [255, 255, 255]],
[[0, 0, 0], [0, 0, 0]],
]
Indices¶
L = [
[3, 2, 6, 8],
[9, 2, 5, 7],
[0, 3, 2, 3],
[1, 2, 3, 4],
]
L[3]
[1, 2, 3, 4]
L[3][3]
4
![Hetzelfde raster, met pijlen die L[1][3], L[3][0] en L[3][3] bij hun cel aanwijzen](../_images/ex_1b.png)
Eerst de rij, dan de kolom. L[3] is een hele rij en dus zelf een lijst; L[3][3] is één getal uit die rij.
Dit lijkt veel op hoe velden op een schaakbord worden aangegeven, maar daar worden rijen (8 tot en met 1) en kolommen (a tot en met h) anders benoemd.
Een raster doorlopen¶
Tot nu toe hebben we een 2D-lijst alleen bekeken. Om er iets mee te doen heb je twee lussen nodig: één over de rijen, en daarbinnen één over de kolommen.
Een bord als toestand¶
Een bord van boter, kaas en eieren is een 2D-lijst van drie bij drie. Elk element is een string van één teken: "X", "O" of " ".
L = [["X", " ", "O"], [" ", "X", " "], ["O", " ", "X"]]
Witruimte verandert de waarde niet. Je mag hetzelfde bord ook over meerdere regels schrijven, en dan zie je het bord staan:
board_over_regels = [
["X", " ", "O"],
[" ", "X", " "],
["O", " ", "X"],
]
assert L == board_over_regels
Het bord afdrukken¶
Twee geneste lussen lopen alle posities langs. De buitenste kiest de rij, de binnenste de kolom, en L[row][col] is de waarde op die positie.
def print_board(L):
"""Drukt het bord L af, met een regel per rij."""
for row in range(len(L)):
for col in range(len(L[0])):
print(L[row][col], end=" ")
print()
print_board(L)
X O
X
O X
len(L) is het aantal rijen en len(L[0]) het aantal kolommen: de lengte van de eerste rij.
Tellen in een raster¶
Voorspel eerst wat hier uit komt, en voer het daarna uit.
L = [["X", " ", "O"], [" ", "X", " "], ["O", " ", "X"]]
count = 0
for row in range(len(L)):
for col in range(len(L[0])):
if L[row][col] == "X":
count = count + 1
print(count)
# controleer jouw antwoord
Van de ene toestand naar de volgende¶
Een zet levert een nieuw bord op. Dat bouw je op dezelfde manier: loop alle posities langs, en kies per positie een waarde. Op de gekozen plek het nieuwe teken, overal elders wat er al stond.
def place(L, row, col, symbol):
"""Geeft een nieuw bord terug met symbol op positie (row, col).
Het bord dat je meegeeft blijft ongewijzigd.
"""
new_board = []
for r in range(len(L)):
new_row = []
for c in range(len(L[0])):
if r == row and c == col:
new_row = new_row + [symbol]
else:
new_row = new_row + [L[r][c]]
new_board = new_board + [new_row]
return new_board
after = place(L, 0, 1, "O")
assert after[0] == ["X", "O", "O"]
assert after[1] == [" ", "X", " "]
assert L[0] == ["X", " ", "O"]
assert place(L, 0, 0, "X") == L
Let op de laatste twee regels: L is na de aanroep nog precies hetzelfde. place verandert niets, het rekent een nieuw bord uit en geeft dat terug. Zo werkt alles in deze cursus tot nu toe.
Loop to the max¶
numbers = [6, 5, 21, 8, 2, 42, 7, 1]
max_value = numbers[0]
for item in numbers:
if item > max_value:
max_value = item
max_value
42
assert max_value == 42
Een reeks analyseren¶
Aandelenkoersen en prijzen¶
prices = [40, 80, 10, 30, 27, 52, 5, 15]
de elementen: prijzen
de indices: dagen
TR Investeringen¶
Wij selecteren de beste dag voor aan- en verkoop om uw winst te maximaliseren…
index |
element |
|---|---|
Dag |
Prijs |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Wat is de beste investeringsstrategie voor de lijst prices?
Hoe kunnen lussen hier bij helpen?
All Pairs algoritme¶
Wanneer kopen en wanneer verkopen voor maximale winst?
Vergelijk alle mogelijke combinaties!
Twee geneste lussen dus, maar niet zoals bij het bord. Daar liep de buitenste lus over de rijen en de binnenste over de kolommen van een 2D-lijst. Hier lopen beide lussen over dezelfde eendimensionale lijst: de buitenste kiest het ene element van een paar, de binnenste het andere. Geneste lussen zijn de techniek; een 2D-lijst is de data. Je hebt ze niet allebei tegelijk nodig.
(40, 80), (40, 10), (40, 30), (40, 27), ... # dag 0
(80, 10), (80, 30), (80, 27), (80, 52), ... # dag 1
Let op, elke dag wordt steeds met de volgende dag vergeleken!
Paarsgewijze vergelijkingen¶
Vergelijkbare problemen
n-body probleem
shortest path probleem
closest pair probleem
Lussen!¶
Paarsgewijs vergelijken
max-so-far = 0
for each buy-day, b:
for each sell-day, s:
compute the profit
if profit is > max-so-far:
remember it in a variable!
return profit, its b-day, and s-day
Verkoop is natuurlijk alleen toegestaan nadat aandelen zijn gekocht…
Het kleinste verschil in een lijst¶
Hierboven staat het All Pairs-algoritme nog als schets. We schrijven het nu uit in Python, op een iets kleiner probleem: de functie min_diff geeft het kleinste absolute verschil terug tussen twee elementen in een lijst:
min_diff([42, 3, 100, -9, 7])
geneste lussen
tussentijdse waarde bijhouden
Geneste lussen¶
Gebruik twee geneste lussen voor het vergelijken van paren, bijvoorbeeld
for ix1 in range(4):
for ix2 in range(4):
Alle paren vormen¶
Wat is de uitvoer? Voorspel eerst, en voer het daarna uit.
numbers = [1, 2, 3]
for ix1 in range(len(numbers)):
for ix2 in range(len(numbers)):
print(numbers[ix1], numbers[ix2])
# controleer jouw antwoord
Dit is een voorbeeld om te zien hoe met geneste lussen paren van elementen kunnen worden gevormd. Je ziet dat dit nog niet correct is omdat hier ook paren van dezelfde elementen worden gevormd (1 en 1, 2 en 2, etc.) én combinaties die twee keer voorkomen (bijvoorbeeld 1 en 3 en 3 en 1). Voor min_diff zal daar een oplossing voor moeten worden gevonden!
Waarde bijhouden¶
Bewaar steeds de waarde van het minimum terwijl je twee keer door de elementen van numbers loopt
Begin met een startwaarde, die je per iteratie (wel of niet) aanpast.
mdiff = abs(numbers[0] - numbers[1])
Had mdiff niet 0 kunnen zijn? Dit had inderdaad gekund, maar er zijn nu in ieder geval waarden gebruikt die zich in de lijst bevinden, dus geen verassingen!
Paarsgewijs¶
Begin ix2 altijd één positie na ix1, bijvoorbeeld:
numbers = [1, 2, 3]
for ix1 in range(len(numbers)):
for ix2 in range(ix1 + 1, len(numbers)):
print(numbers[ix1], numbers[ix2])
1 2
1 3
2 3
De functie min_diff¶
def min_diff(numbers):
"""Geeft het kleinste absolute verschil tussen twee elementen van numbers terug."""
mdiff = abs(numbers[0] - numbers[1]) # startwaarde
for ix1 in range(len(numbers)):
for ix2 in range(ix1 + 1, len(numbers)):
if abs(numbers[ix1] - numbers[ix2]) < mdiff:
mdiff = abs(numbers[ix1] - numbers[ix2])
return mdiff
assert min_diff([42, 3, 100, -9, 7]) == 4
assert min_diff([1, 2, 3]) == 1
assert min_diff([5, 5]) == 0
assert min_diff(prices) == 3
Controleer iedere iteratie of het absolute verschil tussen de twee huidige elementen kleiner is dan het verschil dat eerder is gezien.
Van de schets naar de code¶
min_diff is de schets van hierboven, regel voor regel:
In de schets |
In |
|---|---|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Dezelfde vorm, maar met de winst in plaats van het verschil, is wat je bij menu-optie 6 van de basisopgave schrijft. Dat ix2 één positie ná ix1 begint, is daar precies de eis dat je pas verkoopt nadat je hebt gekocht.
De lussen stap voor stap¶
min_diff([42, 3, 100, -9, 7])
Wat gebeurt in de lussen?
abs(42 - 3) = 39 # ix1 = 0, ix2 = 1, mdiff = 39
abs(42 - 100) = 58 # ix1 = 0, ix2 = 2
abs(42 - -9) = 51 # ix1 = 0, ix2 = 3
abs(42 - 7) = 35 # ix1 = 0, ix2 = 4, mdiff = 35
abs(3 - 100) = 97 # ix1 = 1, ix2 = 2
abs(3 - -9) = 12 # ix1 = 1, ix2 = 3, mdiff = 12
abs(3 - 7) = 4 # ix1 = 1, ix2 = 4, mdiff = 4
abs(100 - -9) = 109 # ix1 = 2, ix2 = 3
abs(100 - 7) = 93 # ix1 = 2, ix2 = 4
abs(-9 - 7) = 16 # ix1 = 3, ix2 = 4
Waar deze week ophoudt¶
Je kunt nu een raster bouwen, afdrukken en doorlopen, en je kunt uit een oud raster een nieuw raster afleiden. Daarmee kom je verder dan je misschien denkt: een bord na een zet, en zelfs generatie na generatie doorrekenen, is een geneste lus die per positie een waarde kiest.
Eén vakje van een raster veranderen terwijl de rest blijft staan, is met het gereedschap van deze week niet uit te drukken. Wat je opschrijft is niet die ene verandering, maar de opbouw van een heel nieuw raster. En omdat elke functie die iets verandert dat nieuwe raster moet teruggeven, moet de aanroeper het steeds opvangen. Bij één functie valt dat mee. Bij een programma waarin vijf functies elk iets aan hetzelfde bord doen, bepaalt het de vorm van het hele programma.
Dat is een echte prijs, en de vraag is of hij nodig is. In week 7 komt daar een nieuw vermogen voor: mutatie, een lijst veranderen die er al is. Game of Life is daar de aanleiding, want dat is een raster dat generatie na generatie wordt bijgewerkt.