import csv from itertools import permutations from math import factorial import random from reversal_sort import SBR, adaptive_tbs, tripartite_binary_sort """ 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, tripartite_binary_sort.GDC_TBS, adaptive_tbs.GDC_ATBS] new_rand_perms_file(algs, algnames, list(range(LENGTH_FROM,LENGTH_TO + 1)), NUM_PERMS_PER_LENGTH) # 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()] # 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) print(reversals) # TODO: Implement pretty print