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: [2, 3, 8, 10],   # Lost In The Brain
  7.     2: [3, 4, 5, 10],   # Afraid Of The Dark
  8.     3: [2, 4, 6, 8],         # Total Annihilation
  9.     4: [3, 8, 9, 10],   # Humps
  10.     5: [2, 3, 6, 7, 8, 10],       # U Break My Heart
  11.     6: [1, 2, 3, 4, 5, 8, 10 ],   # Walking Home
  12.     7: [1, 3, 4, 5, 8],      # Hey Last Night
  13.     8: [1, 3, 9],         # Mellow Vibes
  14.     9: [3, 5, 8, 10],   # O Oh
  15.     10: [1, 3, 5, 9],      # Strawberry Wine
  16. }
  17.  
  18. # allowed starting nodes
  19. starts = [1]
  20.  
  21.  
  22.  
  23. def find_all_paths(graph, start, totallen, path=[]):
  24.     path = path + [start]
  25.     if len(path) == totallen:
  26.         return [path]
  27.     if not graph.has_key(start):
  28.         return []
  29.     paths = []
  30.     for node in graph[start]:
  31.         if node not in path:
  32.             newpaths = find_all_paths(graph, node, totallen, path)
  33.             for newpath in newpaths:
  34.                 paths.append(newpath)
  35.     return paths
  36.  
  37. cycles = []
  38.  
  39. for start in starts:
  40.     print "Non-cyclic paths starting with", start
  41.     paths = find_all_paths(graph, start, len(graph), [])
  42.     for path in paths:
  43.         first = path[0]
  44.         last = path[-1]
  45.         if first in graph[last]:
  46.             cycles.append(path)
  47.         else:
  48.             print path
  49.  
  50. print "Cycles (duplicated for each start song):"
  51. for cycle in cycles:
  52.     print cycle
Success #stdin #stdout 0.07s 65172KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Non-cyclic paths starting with 1
[1, 2, 3, 6, 4, 10, 5, 7, 8, 9]
[1, 2, 3, 6, 8, 9, 10, 5, 7, 4]
[1, 2, 3, 6, 10, 5, 7, 4, 8, 9]
[1, 2, 4, 3, 6, 10, 5, 7, 8, 9]
[1, 2, 4, 10, 3, 6, 5, 7, 8, 9]
[1, 2, 4, 10, 5, 7, 3, 6, 8, 9]
[1, 2, 5, 7, 4, 8, 3, 6, 10, 9]
[1, 2, 5, 7, 4, 10, 3, 6, 8, 9]
[1, 2, 5, 7, 8, 3, 6, 4, 10, 9]
[1, 2, 5, 7, 8, 9, 10, 3, 6, 4]
[1, 2, 10, 3, 6, 5, 7, 4, 8, 9]
[1, 2, 10, 3, 6, 8, 9, 5, 7, 4]
[1, 2, 10, 5, 7, 3, 6, 4, 8, 9]
[1, 2, 10, 5, 7, 4, 3, 6, 8, 9]
[1, 2, 10, 5, 7, 8, 3, 6, 4, 9]
[1, 2, 10, 5, 7, 8, 9, 3, 6, 4]
[1, 2, 10, 9, 5, 7, 8, 3, 6, 4]
[1, 2, 10, 9, 8, 3, 6, 5, 7, 4]
[1, 3, 6, 2, 4, 10, 5, 7, 8, 9]
[1, 3, 6, 2, 10, 5, 7, 4, 8, 9]
[1, 8, 3, 6, 2, 5, 7, 4, 10, 9]
[1, 8, 3, 6, 2, 10, 5, 7, 4, 9]
[1, 8, 3, 6, 2, 10, 9, 5, 7, 4]
[1, 8, 9, 3, 6, 2, 10, 5, 7, 4]
[1, 8, 9, 5, 7, 4, 10, 3, 6, 2]
[1, 8, 9, 10, 3, 6, 2, 5, 7, 4]
[1, 8, 9, 10, 5, 7, 3, 6, 2, 4]
[1, 8, 9, 10, 5, 7, 4, 3, 6, 2]
[1, 10, 3, 6, 2, 5, 7, 4, 8, 9]
[1, 10, 5, 7, 3, 6, 2, 4, 8, 9]
[1, 10, 5, 7, 4, 8, 9, 3, 6, 2]
[1, 10, 5, 7, 4, 9, 8, 3, 6, 2]
[1, 10, 5, 7, 8, 3, 6, 2, 4, 9]
[1, 10, 5, 7, 8, 9, 3, 6, 2, 4]
[1, 10, 9, 5, 7, 4, 8, 3, 6, 2]
[1, 10, 9, 5, 7, 8, 3, 6, 2, 4]
[1, 10, 9, 8, 3, 6, 2, 5, 7, 4]
Cycles (duplicated for each start song):
[1, 2, 3, 6, 4, 8, 9, 10, 5, 7]
[1, 2, 3, 6, 4, 9, 10, 5, 7, 8]
[1, 2, 3, 6, 4, 10, 9, 5, 7, 8]
[1, 2, 3, 6, 5, 7, 4, 8, 9, 10]
[1, 2, 3, 6, 5, 7, 4, 10, 9, 8]
[1, 2, 3, 6, 8, 9, 5, 7, 4, 10]
[1, 2, 3, 6, 10, 5, 7, 4, 9, 8]
[1, 2, 3, 6, 10, 9, 5, 7, 4, 8]
[1, 2, 4, 3, 6, 5, 7, 8, 9, 10]
[1, 2, 4, 3, 6, 8, 9, 10, 5, 7]
[1, 2, 4, 3, 6, 10, 9, 5, 7, 8]
[1, 2, 4, 8, 3, 6, 10, 9, 5, 7]
[1, 2, 4, 8, 9, 3, 6, 10, 5, 7]
[1, 2, 4, 8, 9, 5, 7, 3, 6, 10]
[1, 2, 4, 8, 9, 10, 3, 6, 5, 7]
[1, 2, 4, 8, 9, 10, 5, 7, 3, 6]
[1, 2, 4, 9, 3, 6, 10, 5, 7, 8]
[1, 2, 4, 9, 5, 7, 8, 3, 6, 10]
[1, 2, 4, 9, 8, 3, 6, 10, 5, 7]
[1, 2, 4, 9, 10, 3, 6, 5, 7, 8]
[1, 2, 4, 9, 10, 5, 7, 3, 6, 8]
[1, 2, 4, 9, 10, 5, 7, 8, 3, 6]
[1, 2, 4, 10, 3, 6, 8, 9, 5, 7]
[1, 2, 4, 10, 5, 7, 8, 9, 3, 6]
[1, 2, 4, 10, 9, 3, 6, 5, 7, 8]
[1, 2, 4, 10, 9, 5, 7, 3, 6, 8]
[1, 2, 4, 10, 9, 5, 7, 8, 3, 6]
[1, 2, 4, 10, 9, 8, 3, 6, 5, 7]
[1, 2, 5, 7, 3, 6, 4, 8, 9, 10]
[1, 2, 5, 7, 3, 6, 4, 10, 9, 8]
[1, 2, 5, 7, 4, 3, 6, 8, 9, 10]
[1, 2, 5, 7, 4, 3, 6, 10, 9, 8]
[1, 2, 5, 7, 4, 8, 9, 3, 6, 10]
[1, 2, 5, 7, 4, 8, 9, 10, 3, 6]
[1, 2, 5, 7, 4, 9, 8, 3, 6, 10]
[1, 2, 5, 7, 4, 9, 10, 3, 6, 8]
[1, 2, 5, 7, 4, 10, 9, 3, 6, 8]
[1, 2, 5, 7, 4, 10, 9, 8, 3, 6]
[1, 2, 5, 7, 8, 3, 6, 4, 9, 10]
[1, 2, 5, 7, 8, 9, 3, 6, 4, 10]
[1, 2, 10, 3, 6, 4, 8, 9, 5, 7]
[1, 2, 10, 3, 6, 4, 9, 5, 7, 8]
[1, 2, 10, 3, 6, 5, 7, 4, 9, 8]
[1, 2, 10, 5, 7, 3, 6, 4, 9, 8]
[1, 2, 10, 5, 7, 4, 8, 9, 3, 6]
[1, 2, 10, 5, 7, 4, 9, 3, 6, 8]
[1, 2, 10, 5, 7, 4, 9, 8, 3, 6]
[1, 2, 10, 9, 3, 6, 5, 7, 4, 8]
[1, 2, 10, 9, 5, 7, 3, 6, 4, 8]
[1, 2, 10, 9, 5, 7, 4, 3, 6, 8]
[1, 2, 10, 9, 5, 7, 4, 8, 3, 6]
[1, 3, 6, 2, 4, 8, 9, 10, 5, 7]
[1, 3, 6, 2, 4, 9, 10, 5, 7, 8]
[1, 3, 6, 2, 4, 10, 9, 5, 7, 8]
[1, 3, 6, 2, 5, 7, 4, 8, 9, 10]
[1, 3, 6, 2, 5, 7, 4, 10, 9, 8]
[1, 3, 6, 2, 10, 5, 7, 4, 9, 8]
[1, 3, 6, 2, 10, 9, 5, 7, 4, 8]
[1, 8, 3, 6, 2, 4, 9, 10, 5, 7]
[1, 8, 3, 6, 2, 4, 10, 9, 5, 7]
[1, 8, 3, 6, 2, 5, 7, 4, 9, 10]
[1, 8, 9, 3, 6, 2, 4, 10, 5, 7]
[1, 8, 9, 3, 6, 2, 5, 7, 4, 10]
[1, 8, 9, 5, 7, 3, 6, 2, 4, 10]
[1, 8, 9, 5, 7, 4, 3, 6, 2, 10]
[1, 10, 3, 6, 2, 4, 8, 9, 5, 7]
[1, 10, 3, 6, 2, 4, 9, 5, 7, 8]
[1, 10, 3, 6, 2, 5, 7, 4, 9, 8]
[1, 10, 5, 7, 3, 6, 2, 4, 9, 8]
[1, 10, 9, 3, 6, 2, 5, 7, 4, 8]
[1, 10, 9, 5, 7, 3, 6, 2, 4, 8]
https://ideone.com/kM0Szx
language:
Python (PyPy 2.7.13)
created:
10 days 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!