Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- (* this is needed to cluster the largest layer 'L' in such a way that
- it's compatible with the size of the second-largest layer 'l' *)
- ClusterLargestLayer[L_, l_] := Module[{n, m, c, out},
- n = Length[L];
- m = Length[l];
- c = Floor[n/m]; (* cluster size *)
- out = Partition[Take[L, m c], c];
- out[[-1]] = Join[out[[-1]], Drop[L, m c]];
- out
- ];
- (* this generates a tree from ls = {l,m,r} *)
- Tree[ls_] := Module[{clusterSize, ls3},
- (* cluster largest layer *)
- ls3 = ClusterLargestLayer[ls[[3]], ls[[2]]];
- (* generate a tree using the above clustering *)
- Flatten[Table[{ls[[1, 1]], ls[[2, j]], #} & /@ ls3[[j]], {j, Length[ls[[2]]]}], 1]
- ];
- (* show the tree, example use: ShowTree@Tree[{l,m,r}] *)
- ShowTree[tree_] :=
- Graph[DirectedEdge @@ # & /@
- Flatten[Partition[#, 2, 1] & /@ tree, 1], VertexLabels -> "Name"];
- (* the main function *)
- FindMinimalPaths[list_] := Module[{l, m, r, paths},
- (* reorder from smallest to largest number of elements *)
- {l, m, r} = SortBy[list, Length];
- (* intialize *)
- paths = {};
- (* the main loops *)
- Do[
- Do[
- AppendTo[paths, #] & /@ Tree[{l, m, r}]; (* append the paths in 'tree' to 'paths' *)
- m = RotateLeft[m]; (* prepare for next inner iteration *)
- , {Ceiling[ Length[m]/Length[l] ]}];
- l = RotateLeft[l]; (* prepare for next outer iteration *)
- , {Length[l]}];
- (* output *)
- Sort /@ paths
- ];
- FindMinimalPaths[{{a, b}, {c, d, e, f}, {X, Y, Z, W}}]
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement