TransitionTreesComplexity/reconstruct_permutation.py at master · jmoh3/TransitionTreesComplexity · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
import bisect

def reconstruct_permutation(l):
    w = [l[0]+1]
    sorted_w = [l[0]+1]

    for boxes in l[1:]:
        counter = boxes + 1
        idx = 0
        while idx < len(sorted_w) and sorted_w[idx] <= counter:
            counter += 1
            idx += 1
        to_add = counter
        w.append(to_add)
        bisect.insort(sorted_w, to_add)

    return w

def reconstruct_permutation_complete(l):
    w = [l[0]+1]
    sorted_w = [l[0]+1]

    for boxes in l[1:]:
        counter = boxes + 1
        idx = 0
        while idx < len(sorted_w) and sorted_w[idx] <= counter:
            counter += 1
            idx += 1
        to_add = counter
        w.append(to_add)
        bisect.insort(sorted_w, to_add)

    last = 1

    for idx in range(0, len(sorted_w)):
        if last < sorted_w[idx]:
            while last < sorted_w[idx]:
                w.append(last)
                last += 1
        if sorted_w[idx] == last:
            last += 1

    return w

print(reconstruct_permutation_complete([5, 2, 0, 2]))