haydum
BAN USERCreate a graph of connections between elements (undirected) and a set containing every single element (etc. unvisited(1,2,3,9,5,6)) . Start from any element in the unvisited set and make a dfs or bfs on the graph. Delete the element from the set when it's visited. And as long as there are still elements at the end of each bfs/dfs, continue the above algorithm. Each separate dfs/bfs gives you the different connections
import collections
def findComponents(connections):
unvisited = set()
graph = collections.defaultdict(list)
for x, y in connections:
graph[x].append(y)
graph[y].append(x) # Graph is undirected
unvisited.add(x)
unvisited.add(y)
components = [[]]
stack = collections.deque()
stack.append(unvisited.pop())
while len(stack) != 0:
node = stack.pop()
components[-1].append(node)
print node, unvisited
for nbr in graph[node]:
if nbr in unvisited:
stack.append(nbr)
unvisited.remove(nbr)
if len(stack) == 0:
if len(unvisited) == 0:
return components
else:
components.append([])
stack.append(unvisited.pop())
connections = [(1,2), (2,3), (5,6), (2,9)]
components = findComponents(connections)
print components
Repmarthahiggs71, Intern at Achieve Internet
Hi, I am Martha from Toledo, OH. Working with Top NYC consulting engineers by helping them design controls projects. Have ...
Find the number of all subsets first; 2^n where n is the size of the array. Then think in binary: start from zero to 2^n-1 and check for the bit positions. 2^n-1 has n 1's in binary. Loop from 0 to 2^n-1, print the numbers in the array when there is a 1 in the counter at this position of the array where the sum of them is zero:
n = 6 (size of the array)
2^n = 64 (size of all possible subsets)
loop from zero to 2^n-1
start = 000000
end = 111111
Example: When counter is 33
array : 8, 3, 5, 1,-4,-8
counter: 1 0 0 0 0 1 (33)
counter: 0 1 1 0 0 1 (25)
Time complexity is: O(2^n)
Space complexity: O(n)
Python solution is here:
- haydum January 17, 2015