Last active
October 16, 2018 09:10
-
-
Save aksh1618/2de9b45da2d0eee07ad7b3145407a610 to your computer and use it in GitHub Desktop.
Python script to return family of sets formed by taking union of all combinations of input sets
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
#!/usr/bin/env python3 | |
""" | |
Python script to return family of sets formed by taking union of all combinations of input sets | |
Input: Number of input sets on first line, Space separated set elements on subsequent lines | |
Output: List containing members of union family of input sets | |
Example: | |
$~ ./sets_union_family.py | |
3 | |
1 2 | |
2 3 | |
3 1 | |
[{1, 2}, {1, 3}, {2, 3}, {1, 2, 3}] | |
""" | |
import itertools # For combinations | |
import multiprocessing # For Process | |
def get_union(*sets): | |
"""Returns union of given sets""" | |
return sets[0].union(*sets) | |
def get_hash(set): | |
""" | |
Returns comma separated string representation of given set with | |
elements sorted in asccending order. | |
""" | |
return f"{{{', '.join([str(i) for i in sorted(set)])}}}" | |
def get_union_family_sets_list(dict, input_sets_list, r): | |
"""Returns list containing the sets constituting the union family""" | |
union_family_sets_dict = {} | |
set_combinations = itertools.combinations(input_sets_list, r) | |
for combination in set_combinations: | |
union_set = tuple(get_union(*combination)) | |
if union_set not in union_family_sets_dict: | |
union_family_sets_dict[get_hash(union_set)] = 1 | |
dict[r] = union_family_sets_dict.keys() | |
def main(): | |
# Input sets | |
input_sets_list = [] | |
num_sets = int(input()) | |
for _ in range(num_sets): | |
set_elements = [int(num) for num in input().split(' ')] | |
input_sets_list.append(set(set_elements)) | |
# Use separate process for each iteration | |
p = [] | |
union_family_sets_dict = multiprocessing.Manager().dict() | |
for i in range(1, num_sets + 1): | |
p.append(multiprocessing.Process( | |
target=get_union_family_sets_list, | |
args=(union_family_sets_dict, input_sets_list,i) | |
)) | |
p[i - 1].start() | |
for process in p: | |
process.join() | |
# Eliminate duplicates, converting to tuples as sets aren't hashable | |
all_sets = [] | |
for string_list in union_family_sets_dict.values(): | |
all_sets += string_list | |
union_family_set = set(all_sets) | |
print() | |
for set_ in union_family_set: | |
print(set_) | |
if __name__ == '__main__': | |
main() | |
# TODO: Try https://gist.github.com/axolx/3068001 | |
""" | |
28 | |
1 2 | |
3 4 | |
5 6 | |
7 8 | |
1 2 3 | |
1 2 4 | |
1 2 5 | |
1 2 6 | |
1 2 7 | |
1 2 8 | |
1 3 4 | |
1 5 6 | |
1 7 8 | |
2 3 4 | |
2 5 6 | |
2 7 8 | |
3 4 5 | |
3 4 6 | |
3 4 7 | |
3 4 8 | |
3 5 6 | |
3 7 8 | |
4 5 6 | |
4 7 8 | |
5 6 7 | |
5 6 8 | |
5 7 8 | |
6 7 8 | |
""" |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment