Algorithm of quizzes, friends to try it

  1. test = {8: ',3,4,5,6,7,9,13,15,',
  2. 9: ',6,7,10',
  3. 3: ',2,16,21',
  4. 21: ',8,9,11,14'}
The above is a dictionary, which, for example, there are 8, 9, 3, 21, test[8] value, 3,4,5,6,7,9,13,15 value, test[3] ', 2,16,21' ', test[21] value, 8,9,11,14', write a function, asked to return to the cycle of value

Data shown on the code (such as the return value of function as required):

test[8] = 3
test[3] = 21
test[21] = 8

The left-hand side of the key 8, 3, 21 as a group leader, the right of the equal sign is the direct subordinates, including lead 8 subordinates is 3, lead 3 subordinates is 21, lead 21 subordinates is 8,
So the three formed a circle, was leading 8 should be the highest executive, but in the end into the lowest position 21 subordinates, so, write a function, return some tips, as long as you find out to find this a few cycle can be.
Say my solution, Also the equivalent form to help the reader understand the questions, First traversal test[8], Find the first 3, And then look for the test[3], Test traversal[3], The first value is 2, Keep looking for test[2], When this value is not found, Delete test[3]=2, A value of 16 to second test[3] traversal, And so on, All the way to the left
test[8] = 3
test[3] = 21
test[21] = 8
Then the output of these values, if no such cycle, quit.

Note: the dictionary of unknown length, and number of cycles is unknown, for example, key / only three corresponding sample value circulation, however, may actually have four, five or more corresponding key / value cycle.
So I can add if you don't understand.

Started by Meredith at February 01, 2016 - 9:48 AM

Recursive?

Posted by Brady at February 05, 2016 - 10:11 AM

What value cycle?

Posted by Vivian at February 12, 2016 - 10:19 AM

For example I written dictionary test example, return
test[8] = 3
test[3] = 21
test[21] = 8
Or
Return what can, just find out the circulation data.

Posted by Meredith at February 17, 2016 - 10:32 AM

The small partners, a bit more specific about the pictures.

Posted by Meredith at March 03, 2016 - 11:24 AM

Basically, it is a recursive algorithm. The only difference is, you need to exit the recursive loop

Posted by Brady at March 15, 2016 - 12:19 PM

A code chant, or pseudo code can also be

Posted by Meredith at March 18, 2016 - 1:05 PM

At the two day the python, want to Study hard, and fear not hold... Hey. . .
But I understand you mean. . .

======================
The landlord is to through a dictionary in one key A to find the corresponding tuple is included in the other key B and find it,
Then through the key B to find the corresponding tuple whether there are other key C.
Until this was finally found the key N= initial value A is a cycle. . .

With only four keys in a dictionary, but test[9]= (6,7,10) does not contain any other key(8,3,21)
Is respectively set C1 = (3,4,5,6,7,9,13,15) C2 = (6,7,10) C3 = (2,16,21) C4 = (8,9,11,14) with the set K = (8, 9, 3, 21) to get the intersection.
C1K= (3, 9) C2K= (C3K set)=(21) C4K=(8,9)
testK={8 : '3,9' , 9: '', 3: '21', 21: '8,9'} Should be test[9]=None (class leading 9 may not have subordinate, does not need to be included in the cycle), all the 9 delete
We get a testKD={8 : '3' , 3: '21', 21: '8'}
return testKD[key]
They should get a
test[8] = 3
test[3] = 21
test[21] = 8
======================
Can't write... Fucking. . .

Posted by Gustave at March 29, 2016 - 1:27 PM

If a word can be summarized above long winded:


First calculate their leadership set B, then the leaders set B with pseudo leadership set A intersection get all under the leadership.
These leaders are not necessarily at the bottom of the food chain.

Posted by Gustave at April 03, 2016 - 2:16 PM

Still do not know how to write. . .

Posted by Gustave at April 06, 2016 - 2:44 PM

Found register for more than a year, virgin post here.... Since it seems to often come around. . .

Posted by Gustave at April 09, 2016 - 3:13 PM

  1. test = {8: ',3,4,5,6,7,9,13,15,',
  2. 9: ',6,7,10',
  3. 3: ',2,16,21',
  4. 21: ',8,9,11,14'}

  5. test[8] = ',3,4,5,6,7,9,13,15,'
  6. test[9] = ',6,7,10'
  7. test[3] = ',2,16,21'
  8. test[21] = ',8,9,11,14'
  1. for xx in test:
  2. if test.get(test[xx]):
  3. print xx, test[xx], test[test[xx]]
Casually write, I didn't test

Posted by Brady at April 14, 2016 - 3:59 PM

The problem, from the point of view of graph theory angle, which is "how in a map to find the ring" problem: a dictionary is a point of the edge set, the output cycle is a map to the "ring", so the question is"how to detect circles in a directed graph?"

If this description, algorithm is not hard to find:
From the Internet search two Webpage:
Chinese:

English:


Busy, Python code is not written. Look forward to. . .

Posted by Edmund at January 09, 2017 - 8:36 AM

Today, start practicing.
  1. """
  2. To check whether there is cycle in a graph(Direction based),
  3. have to perform deep first search based navigation.
  4. If there is a node appeared more than 1 times in path,
  5. then, the path is a cycle.

  6. Direction Graps is stored with following style:
  7. { Node1: [NodeName1, NodeName2],
  8. Node2: [NodeName1, NodeName2]}
  9. In the format, Node1, Node2 are represent related nodes in graph.
  10. And [NodeName, NodeName2] represent relate curve from curent node to next node.
  11. """

  12. from copy import deepcopy

  13. def dfs(node, graph, path):
  14. '''Deep first search navigation, if node appeared in path, cycle found.'''
  15. # if could find node
  16. if graph.has_key(node):
  17. # If node in navigation path, find cycle, return result and path
  18. if node in path:
  19. return path
  20. # If could not find node in path, for each sub-arc, recursive dfs
  21. else:
  22. for arc in graph[node]:
  23. # deepcopy is required, avoid dfs pollute tracking
  24. newpath = deepcopy(path)
  25. newpath.add(node)
  26. result = dfs(arc, graph, newpath)
  27. if result:
  28. return result
  29. else:
  30. # If could not find coming node, navigation end, navigation back
  31. return None

  32. def main():
  33. testData = {8: [3,4,5,6,7,9,13,15],
  34. 9: [6,7,10],
  35. 3: [2,16,21],
  36. 21: [8,9,11,14]}
  37. path = set()
  38. for node in testData.iterkeys():
  39. result = dfs(node, testData, path)
  40. if result:
  41. print result
  42. break;

Posted by Don at January 13, 2017 - 9:26 AM