SHARE
TWEET

Untitled

kristianholsheimer Nov 28th, 2014 (edited) 217 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. (* this is needed to cluster the largest layer 'L' in such a way that
  2. it's compatible with the size of the second-largest layer 'l' *)
  3.  
  4. ClusterLargestLayer[L_, l_] := Module[{n, m, c, out},
  5.    n = Length[L];
  6.    m = Length[l];
  7.    c = Floor[n/m];   (* cluster size *)
  8.    
  9.    out = Partition[Take[L, m c], c];
  10.    out[[-1]] = Join[out[[-1]], Drop[L, m c]];
  11.    
  12.    out
  13.    ];
  14.  
  15.  
  16.  
  17. (* this generates a tree from ls = {l,m,r} *)
  18.  
  19. Tree[ls_] := Module[{clusterSize, ls3},
  20.    
  21.    (* cluster largest layer *)
  22.    ls3 = ClusterLargestLayer[ls[[3]], ls[[2]]];
  23.    
  24.    (* generate a tree using the above clustering *)
  25.    Flatten[Table[{ls[[1, 1]], ls[[2, j]], #} & /@ ls3[[j]], {j, Length[ls[[2]]]}], 1]
  26.    ];
  27.  
  28.  
  29.  
  30. (* show the tree, example use: ShowTree@Tree[{l,m,r}] *)
  31.  
  32. ShowTree[tree_] :=
  33.   Graph[DirectedEdge @@ # & /@
  34.     Flatten[Partition[#, 2, 1] & /@ tree, 1], VertexLabels -> "Name"];
  35.  
  36.  
  37.  
  38. (* the main function *)
  39.  
  40. FindMinimalPaths[list_] := Module[{l, m, r, paths},
  41.    (* reorder from smallest to largest number of elements *)
  42.    {l, m, r} = SortBy[list, Length];
  43.    
  44.    (* intialize *)
  45.    paths = {};
  46.    
  47.    (* the main loops *)
  48.    Do[
  49.     Do[
  50.      AppendTo[paths, #] & /@ Tree[{l, m, r}];    (* append the paths in 'tree' to 'paths' *)
  51.      m = RotateLeft[m];    (* prepare for next inner iteration *)
  52.      , {Ceiling[ Length[m]/Length[l] ]}];
  53.     l = RotateLeft[l];    (* prepare for next outer iteration *)
  54.     , {Length[l]}];
  55.    
  56.    
  57.    (* output *)
  58.    Sort /@ paths
  59.    
  60.    ];
  61.  
  62.  
  63. FindMinimalPaths[{{a, b}, {c, d, e, f}, {X, Y, Z, W}}]
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
Top