Question: I have a file "linked_policies.txt" that looks like the following (small sample of data): 0000001G|11111111 0000002G|10000018 0000002G|10000320 0000002G|10000337 0000002G|10000343 101359B|10000018 101359B|16023380 504529A|10000018 504529A|15856008 504529A|16007139 504529A|16007151 504529A|16526483 620667G|16526483 0000003G|22222222 0000003G|33333333  The first column represents 'policy' and second column represents 'customer'. Policy 0000001G is not linked to any other policies as it contains only one customer number not linked to any other policies. Similarly, Policy 0000003G is not linked to any other policies as it contains two customer numbers not linked to any other policies. All of the other policies (0000002G, 101359B, 504529A and 620667G) are considered to be linked to each other because for instance policy 0000002G is directly linked to policies 101359B and 504529A (as they all share the same customer 10000018) but policy 0000002G is also indirectly linked to policy 620667G because even though they do not share a customer number directly between them, policy 620667G shares customer 16526483 with policy 504529A and this policy itself has a shared customer with 0000002G so therefore all are considered to be linked policies. I want to process the input file and end up with a new "output_file.txt" whereby for each policy, the policy is listed in the first column and in the second column (space delimited between first and second column) the list of associated policy/ies are listed (including the policy in question itself). For example, from the sample input file following processing, file "output_file.txt" would look as follows: 0000001G 0000001G 0000002G 0000002G|101359B|504529A|620667G 101359B 101359B|0000002G|504529A|620667G 504529A 504529A|0000002G|101359B|620667G 0000003G 0000003G  First column shows each unique policy number (from the input file) and the second column shows all of the policy/ies that this policy is directly or indirectly linked to. Looking for a way for this to be done using either AWK or Python (noting that the Python version available to me is earlier than version 3.6) My (Python) script "linked_policies.py" attempt is as follows: # Read the input data with open('linked_policies.txt', 'r') as f: lines = f.readlines() # Create a dictionary to store the customers and their associated policies customer_policies = {} # Iterate through the lines for line in lines: # Split the line into policy and customer policy, customer = line.strip().split('|') # Add the customer to the customer_policies dictionary if customer not in customer_policies: customer_policies[customer] = set() customer_policies[customer].add(policy) # Create a dictionary to store the linked policies linked_policies = {} # Link policies based on shared customers for customer, policies in customer_policies.items(): for policy in policies: if policy not in linked_policies: linked_policies[policy] = set(policies) else: linked_policies[policy].update(policies) # Write the output to a file with open('output_file.txt', 'w') as f: for policy, linked_policies_set in linked_policies.items(): linked_policies_str = '|'.join(sorted(linked_policies_set)) f.write('{} {}\n'.format(policy, linked_policies_str))  When I run this: python ./linked_policies.py  ....the resulting output file "output_file.txt" looks like this: 620667G 504529A|620667G 504529A 0000002G|101359B|504529A|620667G 0000003G 0000003G 0000002G 0000002G|101359B|504529A 101359B 0000002G|101359B|504529A 0000001G 0000001G  The second, third and sixth lines are all correct. The other lines are incorrect (first, fourth and fifth lines) as they are not correctly showing all of the linked policies.

Answer: OP has posted that the original awk answer (see 2nd half of this answer) ran for a few minutes and then ran out of memory (on a host with 23 GB of RAM). Here'a rewrite using 1-dimensional arrays: awk ' function get_customer (p, c, i, n) { n = split(pol_cus[p],c,",") for (i=1; i<=n; i++) get_policy(c[i]) } function get_policy (c, p, i, n) { n = split(cus_pol[c],p,",") for (i=1; i<=n; i++) if (! (p[i] in links)) { links[p[i]] get_customer(p[i]) } } BEGIN { FS = "|" } { sep = ($1 in pol_cus) ? "," : "" pol_cus[$1] = pol_cus[$1] sep $2 sep = ($2 in cus_pol) ? "," : "" cus_pol[$2] = cus_pol[$2] sep $1 } END { PROCINFO["sorted_in"] = "@ind_str_asc" for (policy in pol_cus) { delete links links[policy] get_customer(policy) delete links[policy] printf "%s %s", policy, policy for (link in links) printf "|%s", link print "" } } ' policy.dat  To simulate OP's environment I used the following script: awk 'BEGIN { for (i=1;i<=2900000;i++) printf "p%07d|c%07d\np%07d|C%07d\n", i,i,i,i+1 } ' > policy.big.dat  The resulting file: 104 MBytes in size 5.8 million lines 2.9 million unique policy #s 5.8 million unique customer #s  Test environment: i7-1260P 64 GB RAM gawk v 5.1.0  Results of running both awk scripts against the 104 MByte, 5.8 million line policy.big.dat file:  RAM time ----------------------------------------------------------------- awk (2-dimensional arrays) 4.4 GB 12 secs awk (1-dimensional arrays) 2.6 GB 14 secs  A diff of the two resulting data sets report no differences. Running the same tests in a virtual machine (Windows 10, 16 GB RAM, gawk v 5.3.0) and making sure Windows Antimalware service is disabled:  RAM time ----------------------------------------------------------------- awk (2-dimensional arrays) 7.5 GB 17 secs awk (1-dimensional arrays) 2.9 GB 24 secs  Not sure at this point how the original awk answer (below) could take minutes to run and generate an OOM error on OP's host with 23 GB of RAM ...  Original answer General approach:  save policy/customer and customer/policy pairs in 2-dimensional array for each policy in the policy/customer array recursively search for linked policies  One awk approach: awk ' function get_customer (p, c) { for (c in pol_cus[p]) # for each customer associated with this policy ... get_policy(c) # find the associated policies } function get_policy (c, p) { for (p in cus_pol[c]) # for each policy associated with this customer ... if (! (p in links)) { # if we have not seen this policy yet then ... links[p] # add to our list of links and then ... get_customer(p) # find the associated customer(s) } } BEGIN { FS = "|" } { pol_cus[$1][$2] # policy/customer array cus_pol[$2][$1] # customer/policy array } END { PROCINFO["sorted_in"] = "@ind_str_asc" # process array indices in sorted order for (policy in pol_cus) { # loop through our list of policies delete links # clear list of links links[policy] # self link this policy; insures recursive search halts if we see this policy again get_customer(policy) # start the recursive search delete links[policy] # delete the self link printf "%s %s", policy, policy for (link in links) # loop through links and append to current line of output printf "|%s", link print "" # terminate current line of output } } ' policy.dat  NOTES:  requires GNU awk for a) multi-dimensional arrays (aka array of arrays) and b) sorting the policies (via PROCINFO["sorted_in"]) if sorting is not required you can remove the line PROCINFO["sorted_in"] = "@ind_str_asc" see predefined array scanning orders for details on PROCINFO["sorted_in"] = "@ind_str_asc"  This generates: 0000001G 0000001G 0000002G 0000002G|101359B|504529A|620667G 0000003G 0000003G 101359B 101359B|0000002G|504529A|620667G 504529A 504529A|0000002G|101359B|620667G 620667G 620667G|0000002G|101359B|504529A