Optimize the algorithm for finding a learning curve

Question

Suppose that the course consists of 5 training programs, named from A to E, and during the course the student learns 7 unique pieces of information, which I number from 1 to 7. The information obtained in this textbook is set in stone, however I I can study textbooks in any order. For example, I could teach Tut C first if I wanted to.

Tut A: (1,2,3,4)
Tut B: (5,6,7)
Tut C: (2,3)
Tut D: (5,6)
Tut E: (1,2,3)

So let's say I had to teach textbooks in the following order:

Ordering 1:

Tut A: (1,2,3,4)
Tut B: (5,6,7)
Tut C: (2,3)
Tut D: (5,6)
Tut E: (1,2,3)
Tut F: (1,3)

Then the student will study 4 pieces of information in the first textbook and 3 new pieces of information in the second textbook. There is nothing to learn in subsequent textbooks. This is not a good way to order training programs, as the student must learn too much new information at the beginning of the course (steep learning curve). The following order is better:

Ordering 2:

Tut C: (2,3)
Tut F: (1,3)
Tut E: (1,2,3) 
Tut A: (1,2,3,4)
Tut D: (5,6)
Tut B: (5,6,7)

: 1 , 1 , , 1 ,

:

Ordering 3:

Tut C: (2,3)
Tut E: (1,2,3)
Tut F: (1,3) 
Tut A: (1,2,3,4)
Tut D: (5,6)
Tut B: (5,6,7)

:

def curve(tutorials):
    covered = set()
    for t in tutorials:
        new = set(t).difference(covered)
        covered.update(new)
        yield len(new)


# Ordering 1:
print(tuple(curve(((1,2,3,4), (5,6,7), (2,3), (5,6), (1,2,3), (1,3)))))

# Ordering 2:
print(tuple(curve(((2,3), (1,3), (1,2,3,4), (1,2,3), (5,6), (5,6,7)))))

# Ordering 3:
print(tuple(curve(((2,3), (1,2,3), (1,3), (1,2,3,4), (5,6), (5,6,7)))))

, . :

(4, 3, 0, 0, 0, 0)
(2, 1, 1, 0, 2, 1)
(2, 1, 0, 1, 2, 1)

, :

def steepness(r):
    return sum((r[i]*(len(r)-i) for i in range(len(r))))

:

39
26
25

, .

, :

import itertools

def curve(tutorials):
    covered = set()
    for t in tutorials:
        new = set(t).difference(covered)
        covered.update(new)
        yield len(new)

def steepness(r):
    r = tuple(r)
    return sum((r[i]*(len(r)-i) for i in range(len(r))))

tutorials = ((1,2,3,4), (5,6,7), (2,3), (5,6), (1,2,3), (1,3))
print(min(itertools.permutations(tutorials), key=lambda x: steepness(curve(x))))

:

((2, 3), (1, 2, 3), (1, 3), (1, 2, 3, 4), (5, 6), (5, 6, 7))

, 30 , 5, 20 . , ?

Answer 1

, ( 2) (~ 20) (30).

- , , . , . S1, S2, T , S2 = S1 T. | S2 - S1 | ( ) , S1.

#!/usr/bin/env python3
import itertools


def optimize(tutorials):
    tutorials = [frozenset(tutorial) for tutorial in tutorials]
    topics = frozenset(topic for tutorial in tutorials for topic in tutorial)
    cost = {frozenset(): 0}
    predecessor = {}
    for r in range(len(topics)):
        for s1_tuple in itertools.combinations(topics, r):
            s1 = frozenset(s1_tuple)
            if s1 not in cost:
                continue
            cost1 = cost[s1]
            marginal_cost = sum(not tutorial.issubset(s1) for tutorial in tutorials)
            for tutorial in tutorials:
                s2 = s1 | tutorial
                cost2 = cost1 + len(s2 - s1) * marginal_cost
                if s2 not in cost or cost2 < cost[s2]:
                    cost[s2] = cost2
                    predecessor[s2] = s1
    order = []
    s2 = topics
    while s2 in predecessor:
        s1 = predecessor[s2]
        order.extend(tutorial for tutorial in tutorials if tutorial.issubset(s2) and not tutorial.issubset(s1))
        s2 = s1
    order.reverse()
    return order


print(optimize([{1, 2, 3, 4}, {5, 6, 7}, {2, 3}, {5, 6}, {1, 2, 3}, {1, 3}]))

Answer 2

, , . , . . - :

MIQP ( ). (, NEOS). . (MIP), ( ).

, :

Answer 3

- itertools.permutations, .

greedy .

Answer 4

- 30! () 30 , , , 30! : 265252859812191058636308480000000 . , -

( - , - , , .)

( ), , . ( , - , , , , - - , .)

- (, ), , ( ). , ( ) . , - - .

"" - "" NEXT-, , . , .

. O (n!) ( "Oh of an factorial" ), 10 , 10! , 20, 20!, .. - n! n .

, - , , . ( n , n ) n (- ). , set-diff - , 20 , set-diff 20 20, . . , , , , , , 30 , 30 , , 30 ^ 2 = 900 . 265252859812191058636308480000000.

, n , n , O (n ^ 2) ( "oh en squared" ). .

, , , , , , , : , . , .