Skip to content

Instantly share code, notes, and snippets.

@aksh1618
Last active October 16, 2018 09:10
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save aksh1618/2de9b45da2d0eee07ad7b3145407a610 to your computer and use it in GitHub Desktop.
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
#!/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