main.py 4.9 KB
Newer Older
Hrishee Shastri's avatar
Hrishee Shastri committed
1
2
3
4
5
import csv
from itertools import permutations
from math import factorial
import random

Eddie Schoute's avatar
Eddie Schoute committed
6
7
from reversal_sort import SBR, adaptive_tbs, tripartite_binary_sort

Hrishee Shastri's avatar
Hrishee Shastri committed
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
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
"""
Collects routing time data for the algorithms GDC(TBS), GDC(ATBS), and OES.
Spits out the data into csv files in the "/data/" directory. 
"""

def perm_to_str(perm):
    """
    Converts a given list or tuple permutation to a string in the proper format (comma and space separated line without
    brackets)
    """
    if type(perm) is list:
        return str(perm).strip('[]')
    if type(perm) is tuple:
        return str(perm).strip('()')
    raise Exception('perm must be a list or a tuple')


def str_to_perm(string):
    """
    Converts a string representation of a permutation into a list of ints
    """
    return [int(x) for x in string.split(',')]


def new_algs(algs, algnames, nlist):
    """
    Adds a new column to the data files for the values of n given in nlist.  The column corresponds to the given
    algorithm alg. Creates a new file called new_filename with which is a copy of the old data file with the new
    column added on.
    """
    for n in nlist:
        with open('data/len_{:.0f}_perms.csv'.format(n), 'r') as readfile, \
                open('data/new_len_{:.0f}_perms.csv'.format(n), 'w', newline='') as writefile:
            reader = csv.reader(readfile)
            writer = csv.writer(writefile)
            firstrow = True
            for row in reader:
                if firstrow:
                    assert (all(algname not in row for algname in algnames))
                    firstrow = False
                    row += algnames
                else:
                    perm = str_to_perm(row[0])
                    for alg in algs:
                        newcost = alg(perm.copy())
                        row.append(newcost)
                writer.writerow(row)
        print(n, 'complete...')



def new_data_file(alglist, algnames, nlist):
    """
    Creates a new data file for the n values given in nlist with columns corresponding to the algorithms given in
    alglist
    """
    assert (len(alglist) == len(algnames))
    for n in nlist:
        with open('data/len_{:.0f}_perms.csv'.format(n), 'w', newline='') as writefile:
            writer = csv.writer(writefile)
            firstrow = ['Permutation'] + algnames
            writer.writerow(firstrow)
            ct = 1
            ident = [x + 1 for x in range(n)]
            for perm in permutations(ident):
                row = [perm_to_str(perm)]
                for alg in alglist:
                    row.append(alg(list(perm)))
                writer.writerow(row)
                ct += 1
                if ct % (factorial(n) / n) == 0:
                    print('{:.0f}% complete'.format(ct / factorial(n) * 100))


def new_rand_perms_file(alglist, algnames, nlist, count):
    """

    alglist = list of algorithms as functions that take a single argument L, the list to be sorted
    algnames = list of algorithm names, as strings 
    nlist = list of permutation lengths
    count = number of random perms of each length to run algorithms over

    Runs each algorithm in alglist on the same random perms and spits the data for 
    each permutation length X into a csv file called 
    "data/len_X_random_perms.csv"

    Note: folder "data/" needs to exist in the top level directory from where 
    this script is running
    """
    assert (len(alglist) == len(algnames))
    for n in nlist:
        with open('data/len_{:.0f}_random_perms.csv'.format(n), 'w', newline='') as writefile:
            writer = csv.writer(writefile)
            firstrow = ['Permutation'] + algnames
            writer.writerow(firstrow)
            data = []
            for i in range(count):
                perm = [x + 1 for x in range(n)]
                random.shuffle(perm)
                row = [perm_to_str(perm)]
                for alg in alglist:
                    row.append(alg(perm.copy()))
                data.append(row)
                # writer.writerow(row)
                if i % (count // 10) == 0:
                    print('\t{:.0f}% complete'.format(i / count * 100))
            writer.writerows(data)
        print(n, 'complete')


def main(NUM_PERMS_PER_LENGTH, LENGTH_FROM, LENGTH_TO):
    algnames = ['OES', 'GDC(TBS)', 'GDC(ATBS)']
Eddie Schoute's avatar
Eddie Schoute committed
120
    algs = [SBR.odd_even_sort, tripartite_binary_sort.GDC_TBS, adaptive_tbs.GDC_ATBS]
Hrishee Shastri's avatar
Hrishee Shastri committed
121
    new_rand_perms_file(algs, algnames, list(range(LENGTH_FROM,LENGTH_TO + 1)), NUM_PERMS_PER_LENGTH)
Eddie Schoute's avatar
Eddie Schoute committed
122
123
124
125
126
127
128


# Now you can run `echo "0 1 3 2" | python main.py`
if __name__ == "__main__":
    import sys
    for line in sys.stdin:
        perm = [int(el) for el in line.split()]
Eddie Schoute's avatar
Eddie Schoute committed
129
130
131
132
        # Check if is permutation
        if set(range(0, len(perm))) != set(perm):
            raise ValueError(f"Given permutation does not contain all elements in [0,{len(perm)-1}].")
        reversals = tripartite_binary_sort.routing_divideconquer_tbs(perm)
Eddie Schoute's avatar
Eddie Schoute committed
133
        print(reversals) # TODO: Implement pretty print