main.py 4.71 KB
Newer Older
Hrishee Shastri's avatar
Hrishee Shastri committed
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
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
120
121
122
import csv
import SBR
import AdaptiveTBS
import TripartiteBinarySort
from itertools import permutations
from math import factorial
import random

"""
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)']
    algs = [SBR.odd_even_sort, TripartiteBinarySort.GDC_TBS, AdaptiveTBS.GDC_ATBS]
    new_rand_perms_file(algs, algnames, list(range(LENGTH_FROM,LENGTH_TO + 1)), NUM_PERMS_PER_LENGTH)
Eddie Schoute's avatar
Eddie Schoute committed
123
124
125
126
127
128
129
130
131


# 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()]
        reversals = TripartiteBinarySort.permutationsort_divideconquer_tbs(perm)
        print(reversals) # TODO: Implement pretty print