Combining pairs in a string (Matlab)

Question

I have a string:

 sup_pairs = 'BA CE DF EF AE FC GD DA CG EA AB BG'

How can I combine pairs which have the last character of 1 pair is the first character of the follow pairs into strings? And the new strings must contain all of the character 'A','B','C','D','E','F' , 'G', those characters are appeared in the sup_pairs string. The expected output should be:

 S1 = 'BAEFCGD' % because BA will be followed by AE in sup_pairs string, so we combine BAE, and so on...we continue the rule to generate S1

 S2 = 'DFCEABG'

If I have AB, BC and BD, the generated strings should be both : ABC and ABD . If there is any repeated character in the pairs like : AB BC CA CE . We will skip the second A , and we get ABCE .

Answer 1

This, like all good things in life, is a graph problem. Each letter is a node, and each pair is an edge.

First we must transform your string of pairs into a numeric format so we can use the letters as subscripts. I will use A=2, B=3, ..., G=8:

sup_pairs = 'BA CE DF EF AE FC GD DA CG EA AB BG';
p=strsplit(sup_pairs,' ');
m=cell2mat(p(:));
m=m-'?';
A=sparse(m(:,1),m(:,2),1);

The sparse matrix A is now the adjacency matrix (actually, more like an adjacency list) representing our pairs. If you look at the full matrix of A, it looks like this:

>> full(A)
ans =
   0   0   0   0   0   0   0   0
   0   0   1   0   0   1   0   0
   0   1   0   0   0   0   0   1
   0   0   0   0   0   1   0   1
   0   1   0   0   0   0   1   0
   0   1   0   0   0   0   1   0
   0   0   0   1   0   0   0   0
   0   0   0   0   1   0   0   0

As you can see, the edge BA, which translates to subscript (3,2) is equal to 1.

Now you can use your favorite implementation of Depth-first Search (DFS) to perform a traversal of the graph from your starting node of choice. Each path from the root to a leaf node represents a valid string. You then transform the path back into your letter sequence:

treepath=[3,2,6,7,4,8,5];
S1=char(treepath+'?');

Output:
S1 = BAEFCGD

---

Here's a recursive implementation of DFS to get you going. Normally in MATLAB you have to worry about not hitting the default limitation on recursion depth, but you're finding Hamiltonian paths here, which is NP-complete. If you ever get anywhere near the recursion limit, the computation time will be so huge that increasing the depth will be the least of your worries.

function full_paths = dft_all(A, current_path)
   % A - adjacency matrix of graph
   % current_path - initially just the start node (root)
   % full_paths - cell array containing all paths from initial root to a leaf

   n = size(A, 1);   % number of nodes in graph 
   full_paths = cell(1,0);   % return cell array 

   unvisited_mask = ones(1, n);
   unvisited_mask(current_path) = 0;   % mask off already visited nodes (path)
   % multiply mask by array of nodes accessible from last node in path
   unvisited_nodes = find(A(current_path(end), :) .* unvisited_mask);

   % add restriction on length of paths to keep (numel == n)
   if isempty(unvisited_nodes) && (numel(current_path) == n)
      full_paths = {current_path};   % we've found a leaf node
      return;
   end

   % otherwise, still more nodes to search
   for node = unvisited_nodes
      new_path = dft_all(A, [current_path node]);   % add new node and search
      if ~isempty(new_path)   % if this produces a new path...
         full_paths = {full_paths{1,:}, new_path{1,:}};   % add it to output 
      end
   end

end

This is a normal Depth-first traversal except for the added condition on the length of the path in line 15:

   if isempty(unvisited_nodes) && (numel(current_path) == n)

The first half of the if condition, isempty(unvisited_nodes) is standard. If you only use this part of the condition you'll get all paths from the start node to a leaf, regardless of path length. (Hence the cell array output.) The second half, (numel(current_path) == n) enforces the length of the path.

I took a shortcut here because n is the number of nodes in the adjacency matrix, which in the sample case is 8 rather than 7, the number of characters in your alphabet. But there are no edges into or out of node 1 because I was apparently planning on using a trick that I never got around to telling you about. Rather than run DFS starting from each of the nodes to get all of the paths, you can make a dummy node (in this case node 1) and create an edge from it to all of the other real nodes. Then you just call DFS once on node 1 and you get all the paths. Here's the updated adjacency matrix:

A =
   0   1   1   1   1   1   1   1
   0   0   1   0   0   1   0   0
   0   1   0   0   0   0   0   1
   0   0   0   0   0   1   0   1
   0   1   0   0   0   0   1   0
   0   1   0   0   0   0   1   0
   0   0   0   1   0   0   0   0
   0   0   0   0   1   0   0   0

If you don't want to use this trick, you can change the condition to n-1, or change the adjacency matrix not to include node 1. Note that if you do leave node 1 in, you need to remove it from the resulting paths.

Here's the output of the function using the updated matrix:

>> dft_all(A, 1)
ans =
{
  [1,1] =

     1   2   3   8   5   7   4   6

  [1,2] =

     1   3   2   6   7   4   8   5

  [1,3] =

     1   3   8   5   2   6   7   4

  [1,4] =

     1   3   8   5   7   4   6   2

  [1,5] =

     1   4   6   2   3   8   5   7

  [1,6] =

     1   5   7   4   6   2   3   8

  [1,7] =

     1   6   2   3   8   5   7   4

  [1,8] =

     1   6   7   4   8   5   2   3

  [1,9] =

     1   7   4   6   2   3   8   5

  [1,10] =

     1   8   5   7   4   6   2   3

}