Storseminarium 3.2 - En sak i taget

Innan seminariet ska du ha gått igenom Inför seminariet nedan och gjort tillhörande quiz. Syftet med detta är att du ska bekanta dig med innehållet så eventuella frågor kan redas ut under seminariet.

Denna sida visar en del av det som kommer att diskuteras på seminariet. Det kan hända att handledarna också tar upp andra uppgifter som inte behöver något specifikt studiematerial och då syns dessa uppgifter inte på sidan.

Inför seminariet

• Förberedelsematerial

Hyperoperationer

Vi ska börja med att titta på en funktion som är dubbelrekursiv och se hur tunga beräkningar detta kan leda till. Vi ska inte gå på djupet in i vad funktionen faktiskt gör och man behöver inte känna sig stressad om man inte förstår varför funktionen kan göra vad den gör. Det gäller även assistenterna, för vilka detta troligtvis är en ny funktion.

Detta ska istället dels som en övning i att översätta matematisk notation till Python, och dels som en illustration av hur snabbt dubbelrekursion kan leda till så många rekursiva anrop att det inte är praktiskt görbart att beräkna. Lägg alltså inte för mycket tid på denna enda uppgift.

Vi ska titta på konceptet hyperoperation. Hyperoperationer definieras med hjälp av dubbelrekursion. Hyperoperationen $H_n(a, b)$ omnämndes först i början av 1900-talet men är mest associerad med Wilhelm Ackermann som definierade den snarlika Ackermannfunktionen i slutet av 1920-talet. Både hyperoperationen och Ackermannfunktionen är relaterade till den teoretiska grunden för datavetenskap och varför vissa funktioner är eller inte är beräkningsbara. Mer specifikt är de exempel på funktioner som inte kan lösas med for-loopar eftersom det inte är möjligt att beräkna antalet steg som krävs utan att genomföra själva beräkningen.

Vad hyperoperationen faktiskt gör ska vi försöka lista ut genom att implementera den i Python och testa med olika värden.

Den n:te hyperoperationen av två tal $a$ och $b$ definieras som följande:

$$ H_n(a,b) =% a[n]b = \begin{cases} S(b) & \text{if } n = 0 \\ a & \text{if } n = 1 \text{ och } b = 0 \\ 0 & \text{if } n = 2 \text{ och } b = 0 \\ 1 & \text{if } n \ge 3 \text{ och } b = 0 \\ H_{n-1}(a, H_n(a, b - 1)) & \text{i alla andra fall} \end{cases} $$

I definitionen används $S(b)$ för att beteckna successor-funktionen, dvs. funktionen som returnerar “nästa heltal”. Alltså, $S(b) = b + 1$. Vi kan, om än på ett lite opraktiskt sätt, definiera alla positiva heltal med hjälp av successor-funktionen och utgångsvärdet $0$, t.ex. gäller att $1 = S(0)$ och $2 = S(S(0))$, osv. Det här sättet att definiera heltal kallas Peano-aritmetik och är en grundläggande byggsten i matematiken. Faktiskt så grundläggande att det är svårt att föreställa sig att det finns något mer grundläggande än så, och också så grundläggande att man nog aldrig ens tänkt på att det kan behöva definieras.

I Python kan vi dock helt enkelt byta ut alla ställen där $S(b)$ används med b + 1.

Ett annat sätt att definiera $H_n$, som introducerades av Reuben Goldstein på 40-talet, kan vara lite lättare att översätta till Python:

$$ H_n(a,b) = G(n,a,b) =% a[n]b = \begin{cases} S(b) & \text{if } n = 0 \\ a & \text{if } n = 1 \text{ och } b = 0 \\ 0 & \text{if } n = 2 \text{ och } b = 0 \\ 1 & \text{if } n \ge 3 \text{ och } b = 0 \\ G(n-1, a, G(n, a, b - 1)) & \text{i alla andra fall} \end{cases} $$

Uppgift:

Vi ska definiera en funktion hyperop(n, a, b) som tar tre argument: ett icke-negativt heltal n, och två positiva heltal a och b. Funktionen ska beräkna hyperoperationen av ordning n av a och b.

def hyperop(n, a, b):
    if n == 0:
        return b + 1
    elif n == 1 and b == 0:
        return a
    elif n == 2 and b == 0:
        return 0
    elif n >= 3 and b == 0:
        return 1
    else:
        return hyperop(n-1, a, hyperop(n, a, b - 1))

Uppgift:

Vi kan nu testa vår funktion med några små värden på n, a och b. Sätter vi a och b till 0, 1, eller till och med 2, så är resultatet svårt att tolka. Det är först när vi sätter a eller b till 3 eller mer som det börjar bli lättare att se vad som händer. Vi kan t.ex. beräkna hyperop(n, 2, 3) för olika värden på n. Testa följande kod:

print(f"{hyperop(0, 2, 3)=}")
print(f"{hyperop(1, 2, 3)=}")
print(f"{hyperop(3, 2, 3)=}")
print(f"{hyperop(4, 2, 3)=}")

Vi kan också testa att sätta a till 3 och b till 2. Testa följande kod:

print(f"{hyperop(0, 3, 2)=}")
print(f"{hyperop(1, 3, 2)=}")
print(f"{hyperop(3, 3, 2)=}")
print(f"{hyperop(4, 3, 2)=}")

Kan vi tänka oss vad hyperop egentligen beräknar? Vad är det för operationer som sker när n är 0, 1, 2, 3 och 4?

hyperop(0, 2, 3)=4 # 3 + 1
hyperop(1, 2, 3)=5 # 2 + 3
hyperop(2, 2, 3)=6 # 2 * 3
hyperop(3, 2, 3)=8 # 2 ** 3
hyperop(4, 2, 3)=16 # (2 ** 2) ** 2
hyperop(0, 3, 2)=3 # 2 + 1
hyperop(1, 3, 2)=5 # 3 + 2
hyperop(2, 3, 2)=6 # 3 * 2
hyperop(3, 3, 2)=9 # 3 ** 2
hyperop(4, 3, 2)=27 # 3 ** 3

Uppgift:

Vad händer om vi försöker beräkna hyperop(5, 7, 3)? Kan vi tänka oss vad resultatet borde bli? Kan vi beräkna det?

import sys
sys.setrecursionlimit(100000)
print(f"{hyperop(4, 5, 7)=}")

uppgift:

Modifiera hyperop så att de första raderna i funktionen ser ut så här:

    global call_count
    call_count += 1

Testa sedan att köra:

call_count = 0
print(f"{hyperop(3, 3, 2)=} took {call_count} calls")
call_count = 0
print(f"{hyperop(3, 2, 3)=} took {call_count} calls")
call_count = 0
print(f"{hyperop(3, 3, 3)=} took {call_count} calls")
call_count = 0
print(f"{hyperop(3, 4, 3)=} took {call_count} calls")
call_count = 0
print(f"{hyperop(3, 3, 4)=} took {call_count} calls")
call_count = 0
print(f"{hyperop(3, 4, 4)=} took {call_count} calls")

Vad ser du? Kan du förklara varför det blir så många anrop?

Maximal nivå av nästlade listor

Nu när vi sett den praktiska gränsen för vad en dubbelrekursiv funktion kan göra så ska vi titta på några mer realistiska exempel. Vi ska börja med att definiera en funktion max_nesting_level(struct) som tar en struktur struct av listor och heltal som argument och returnerar den maximala nivån av nästling i listan. Nivån av nästling definieras som det största antalet nivåer av inbäddade listor inom listan.

Exempel

>>> max_nesting_level([1, 2, 3])
0
>>> max_nesting_level([1, [2, 3], 4])
1
>>> max_nesting_level([1, [2, [3, 4]], 5])
2
>>> max_nesting_level([1, [2, [3, [4, 5]]], 6])
3

1
2
3
4
5
6
7
8
9

def max_nesting_level(struct):
    if not struct:
        return 0
    elif isinstance(struct[0], list):
        return max(
            max_nesting_level(struct[0]) + 1, max_nesting_level(struct[1:])
        )
    else:
        return max_nesting_level(struct[1:])

1
2
3
4
5
6

def max_nesting_level2(struct):
    depths = []
    for element in struct:
        if isinstance(element, list):
            depths.append(max_nesting_level2(element) + 1)
    return max(depths, default=0)

1
2
3
4
5

def max_nesting_level3(struct):
    return max(
        (max_nesting_level3(e) + 1 for e in struct if isinstance(e, list)),
        default=0,
    )

Maximal nivå av nästling med olika typer

Nu ska vi modifiera max_nesting_level så att den kan hantera listor som innehåller olika typer av element, inklusive andra listor, tuples, mängder och dictionaries. Funktionen ska fortfarande returnera den maximala nivån av nästling i strukturen. Kalla funktionen max_nesting_level_any(struct).

Exempel

>>> max_nesting_level_any([])
0
>>> max_nesting_level_any((1, 2, 3))
0
>>> max_nesting_level_any((1, 2, 3, []))
1
>>> max_nesting_level_any([1, (2, 3), 4])
1
>>> max_nesting_level_any([1, (2, 3, []), 4])
2
>>> max_nesting_level_any([1, [2, {3: 4}], {5}])
3
>>> max_nesting_level_any([1, (2, {3: [4, 5]}, 6)])
4
>>> max_nesting_level_any([1, (2, {(3, (4, 5)): [6, 7]}, 8)])
5

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22

def max_nesting_level_any(struct):
    if not struct:
        return 0
    # Gör om mängder till tupler
    if isinstance(struct, set):
        struct = tuple(struct)
    # Gör om dictionaries till tuples av deras items
    elif isinstance(struct, dict):
        struct = tuple(struct.items())
    # Traversera strukturen med dubbelrekursion
    if (
        isinstance(struct[0], list)
        or isinstance(struct[0], tuple)
        or isinstance(struct[0], set)
        or isinstance(struct[0], dict)
    ):
        return max(
            max_nesting_level_any(struct[0]) + 1,
            max_nesting_level_any(struct[1:]),
        )
    else:
        return max_nesting_level_any(struct[1:])

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18

def max_nesting_level_any2(struct):
    # Gör om mängder till tupler
    if isinstance(struct, set):
        struct = tuple(struct)
    # Gör om dictionaries till tuples av deras items
    elif isinstance(struct, dict):
        struct = tuple(struct.items())
    depths = []
    # Iterera över strukturen och undersök nästlade strukturer rekursivt
    for element in struct:
        if (
            isinstance(element, list)
            or isinstance(element, tuple)
            or isinstance(element, set)
            or isinstance(element, dict)
        ):
            depths.append(max_nesting_level_any2(element) + 1)
    return max(depths, default=0)

Ta bort värden ur nästlade listor

Vi ska nu definiera en funktion remove_value(struct, value) som tar en struktur struct som kan innehålla listor och heltal och vara nästlad på flera nivåer. Funktionen ska returnera ett objekt med samma struktur som struct men där alla förekomster av value har tagits bort.

Exempel

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

>>> remove_value([], 1)
[]
>>> remove_value([1, 2, 3], 2)
[1, 3]
>>> remove_value([1, [2, 3], 4], 2)
[1, [3], 4]
>>> remove_value([1, [2, [3, 4]], 5], 3)
[1, [2, [4]], 5]
>>> remove_value([1, [2, [3, [4, 5]]], 6], 4)
[1, [2, [3, [5]]], 6]
>>> remove_value([1, 2, 3, 2, 4, 2], 2)
[1, 3, 4]
>>> remove_value([1, [2, [2], 4], 2], 2)
[1, [[], 4]]
>>> remove_value([1, [2, [3, [4, 2]], 5], 2], 2)
[1, [[3, [4]], 5]]

1
2
3
4
5
6
7
8
9

def remove_value(struct, value):
    if not struct:
        return struct
    if isinstance(struct[0], list):
        return [remove_value(struct[0], value)] + remove_value(struct[1:], value)
    elif struct[0] == value:
        return remove_value(struct[1:], value)
    else:
        return [struct[0]] + remove_value(struct[1:], value)

1
2
3
4
5
6
7
8
9

def remove_value2(struct, value):
    acc = []
    for element in struct:
        if isinstance(element, list):
            acc.append(remove_value2(element, value))
        elif element != value:
            acc.append(element)
    return acc

Räkna upp heltal

Vi ska nu definiera funktion increment_ints(struct) som tar en struktur som kan innehålla listor, tupler, dictionaries, heltal, flyttal och strängar och vara nästlad på flera nivåer. Funktionen ska returnera ett objekt med samma struktur som struct men där alla heltal har ökats med 1.

Exempel

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

>>> increment_ints(1)
2
>>> increment_ints([1, '2', 3])
[2, '2', 4]
>>> increment_ints((1, 2, 3))
(2, 3, 4)
>>> increment_ints([1, (2, 3.0), 4])
[2, (3, 3.0), 5]
>>> increment_ints([1, [2, {3: 4}], 5])
[2, [3, {4: 5}], 6]
>>> increment_ints([1.0, (2, {3: ['4', 5]}, 6)])
[1.0, (3, {4: ['4', 6]}, 7)]
>>> increment_ints([1, (2, {(3, (4, '5')): [6, 7]}, 8)])
[2, (3, {(4, (5, '5')): [7, 8]}, 9)]

def increment_ints(struct):
    if isinstance(struct, int):
        return struct + 1
    if not struct:
        return struct
    if isinstance(struct, list):
        return [increment_ints(struct[0])] + increment_ints(struct[1:])
    elif isinstance(struct, tuple):
        return (increment_ints(struct[0]),) + increment_ints(struct[1:])
    elif isinstance(struct, dict):
        # Vi konverterar dictionaryt till en tuple av dess items
        # för att kunna traversera den som en sekvens
        struct = tuple(struct.items())
        # Vi försäkrar att nyckel-värde-paren i dictionaryt återställs till
        # dictionaryformatet när vi är klara med traverseringen
        return dict((increment_ints(struct[0]),) + increment_ints(struct[1:]))
    else:
        return struct

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17

def increment_ints(struct):
    if isinstance(struct, int):
        return struct + 1
    elif isinstance(struct, list) or isinstance(struct, tuple):
        acc = []
        for element in struct:
            acc.append(increment_ints(element))
        if isinstance(struct, list):
            return acc
        else:  # tuple
            return tuple(acc)
    elif isinstance(struct, dict):
        acc = {}
        for key, value in struct.items():
            acc[increment_ints(key)] = increment_ints(value)
        return acc
    return struct