fork download
copy 
  1. # based on this:
  2. # https://stackoverflow.com/questions/28518369/build-all-hamiltonian-paths-from-an-edge-list
  3.  
  4. graph = {
  5. #   node: [list of allowed followers]
  6.     1: [10],   # Song Name 1
  7.     2: [5, 3],      # Song Name 2
  8.     3: [2, 4, 6, 8],         # Song Name 3
  9.     4: [1, 3, 8, 9],   # Song Name 4
  10.     5: [1, 2, 3, 6, 7, 8],      # Song Name 5
  11.     6: [3, 8, 10, 4, 5, 2],   # Song Name 1
  12.     7: [1, 3, 4, 5, 8],      # Song Name 2
  13.     8: [3, 9],         # Song Name 3
  14.     9: [3, 5],   # Song Name 4
  15.     10: [2],    # Song Name 5
  16. }
  17.  
  18. # allowed starting nodes
  19. starts = [1, 2, 3]
  20.  
  21. def find_all_paths(graph, start, totallen, path=[]):
  22.     path = path + [start]
  23.     if len(path) == totallen:
  24.         return [path]
  25.     if not graph.has_key(start):
  26.         return []
  27.     paths = []
  28.     for node in graph[start]:
  29.         if node not in path:
  30.             newpaths = find_all_paths(graph, node, totallen, path)
  31.             for newpath in newpaths:
  32.                 paths.append(newpath)
  33.     return paths
  34.  
  35. cycles = []
  36.  
  37. for start in starts:
  38.     print "Non-cyclic paths starting with", start
  39.     paths = find_all_paths(graph, start, len(graph), [])
  40.     for path in paths:
  41.         first = path[0]
  42.         last = path[-1]
  43.         if first in graph[last]:
  44.             cycles.append(path)
  45.         else:
  46.             print path
  47.  
  48. print "Cycles (duplicated for each start song):"
  49. for cycle in cycles:
  50.     print cycle
Success #stdin #stdout 0.05s 64692KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Non-cyclic paths starting with 1
[1, 10, 2, 5, 7, 3, 6, 4, 8, 9]
[1, 10, 2, 5, 7, 4, 3, 6, 8, 9]
[1, 10, 2, 5, 7, 4, 8, 9, 3, 6]
[1, 10, 2, 5, 7, 4, 9, 3, 6, 8]
[1, 10, 2, 5, 7, 8, 3, 6, 4, 9]
[1, 10, 2, 3, 6, 4, 9, 5, 7, 8]
[1, 10, 2, 3, 6, 5, 7, 4, 8, 9]
Non-cyclic paths starting with 2
Non-cyclic paths starting with 3
Cycles (duplicated for each start song):
[1, 10, 2, 5, 7, 8, 9, 3, 6, 4]
[1, 10, 2, 3, 6, 8, 9, 5, 7, 4]
[1, 10, 2, 3, 6, 4, 8, 9, 5, 7]
[2, 5, 7, 8, 9, 3, 6, 4, 1, 10]
[2, 3, 6, 8, 9, 5, 7, 4, 1, 10]
[2, 3, 6, 4, 8, 9, 5, 7, 1, 10]
[3, 6, 8, 9, 5, 7, 4, 1, 10, 2]
[3, 6, 4, 1, 10, 2, 5, 7, 8, 9]
[3, 6, 4, 8, 9, 5, 7, 1, 10, 2]
https://ideone.com/pYYHZB
language:
Python (PyPy 2.7.13)
created:
4 hours ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!