This is the MATLAB implementation of the idea explained here by using the useful graph functions already given in MATLAB. Here an additional feature is given, which is the possibility to stop to the first found path (also shortest) from the starting to the target number, or to continue and find all possible paths.

A short mathematical background in the comments explain what main formulas were used.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 |
% FUN.m % Function list. Each function is identified by an index f_nr and works % on the input in function out=fun(in,f_nr) if f_nr == 1 out = in*2; elseif f_nr == 2 out = bitshift(in,1); elseif f_nr == 3 out = in-1; elseif f_nr == 4 out = in+1; end end |

The main code:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 |
% REGR.m % Mathematical Background: % There exists n^0+n^1+n^2+...+n^depth total node in such network % The first successor of a node X is n*(X-1)+2 % Each node X>1 corresponds to the (X-2)%n+1 function clear input = 15; % Starting value output = 121; % Final value depth = 6; stopIfMatched = 1; % 1 = find all paths; 0 = find the first paths n = 4; % Number of functions to apply from fun.m (1,2,3...n) G = digraph; totalNodes = sum(repmat(n,1,depth).^[0:depth-1]);% Total nodes with depth % decreased by 1 paths = {}; index = 1; matched = 0; for Node=[1:totalNodes] if Node == 1 in = input; else in = G.Edges{inedges(G, Node), 'Weight'}; end for funIndex = [0:n-1] Next = n*(Node-1)+2+funIndex; out = fun(in,funIndex+1); G = addedge(G,Node,Next,out); if out == output sh = shortestpath(G,1,Next); paths(index) = {sh(2:end)}; if stopIfMatched matched = 1; break; end index = index + 1; end end if stopIfMatched && matched break; end end paths=cellfun(@(e)mod((e-2),n)+1,paths,'UniformOutput',false); celldisp(paths);% Display results plot(G); plot(G,'EdgeLabel',G.Edges.Weight);% Plot the weigthed tree |

Example of a plotted tree with n=2,depth=4, input=10, stopIfMatched=0:

Possible developments & applications:

- Given a limited set of functions and a few input / output pairs a common path between inputs and outputs could be found (if exists). In this case all inputs would be part of the domain and all outputs of the co-domain of a single function made by the composition of the user defined functions.
- A brute force way to solve Rubik’s cube from any initial configuration could be implemented and the shortest set of moves can be given as output.
- The script can be extended to symbolic functions. Let’s suppose we have a set of possible operations (like integration, derivative, elevation to some power, addition of constant, multiplication by constant). The question “How to turn a given function f(x) in another given function g(x) just by combining the given operations” could be answered.
- Something (chess piece, robots, …) has a limited and well defined set of moves and need to go from point A to point B.

## Leave a Reply