Given some words, find a sequence such that any ad

Question

Given some words, e.g. banana , cat , dog, elephant, type, middle, lake

find a sequence such that

(1) every word is on the sequence

(2) any adjacent words cannot have same characters.

If the seq cannot be found, return false. otherwise, return true and the seq.

No duplicated. No permutations of words.

My idea:

Set up a graph, and use Hamiltonian path to find the seq.

But, it is a NP complete.

How to avoid Hamiltonian path ?

Any better ideas ?

thanks

Answer 1

Note that if you have constructed a partial sequence, it is only the last word that determines which other words you may continue the sequence with. For instance, if you have selected "banana" and "dog", you may continue with "type" or "lake" (it doesn't matter that "lake" collides with "banana", because "lake" will be adjacent to "dog"). Since you must use the words in the order they appear (if I understand your description correctly), you can use dynamic programming to solve the problem "what is the longest sequence of words I can produce that ends with the i th word?"

Answer 2

My approach would involve a struct:

struct node{
    char c1, c2;
    char* str;
    int used;
    int ind;
    std::vector<struct node*> valid;
};

c1 would be the first character in str, and c2 would be the last. I would loop over the input array and generate a node for each item, and probably put them into a std::vector. Then on each node, push_back() a reference to all the nodes that could be validly placed in front of that node in to valid. Then I would recursively look for the path. Just start with the first node, label it used, navigate to the first index of valid, repeat for that node, then when control returns to that point, go to the next node in valid, do the same, then when returning from here, reset the used value in all the nodes. If a match isn't found, return false.

Here's a bit of code. It makes sure that the first and last letter of each word do not match. Modify the qualifying expression to suit your needs.

#include<stdio.h>
#include<string.h>
#include<vector>

struct node{
    char c1, c2;
    char* str;
    int used;
    int ind;
    std::vector<struct node*> valid;
};

int ispath_rec( std::vector<node*> &nodes, int depth, int* returnarray );

int ispath( char** value, int valuec, int* returnarray ){
    std::vector<node*> nodes;
    for( int i = 0; i < valuec; i ++ ){
        node* a = new node;
        nodes.push_back(a);
        a->used = 0;
        a->str = value[i];
        a->c1 = value[i][0];
        a->c2 = value[i][strlen(value[i])-1];
        a->ind = i;
    }
    for( int i = 0; i < valuec; i ++ ){
        node* a = nodes[i];
        for( int j = 0; j < valuec; j ++ ){
            node* b = nodes[j];
            if( b->c1 != a->c2 && b != a ) /*b->c1 != a->c2 is the qualifying expression*/
                a->valid.push_back( b );
        }
    }
    return ispath_rec( nodes, valuec, returnarray );
}

int ispath_rec( std::vector<struct node*> &nodes, int depth, int* returnarray ){
    if( depth <= 0 )
        return 1;
    for( int i = 0; i < nodes.size(); i ++ ){
        if( nodes[i]->used == 0 ){
            nodes[i]->used = 1;
            *returnarray = nodes[i]->ind;
            if( ispath_rec( nodes[i]->valid, depth-1, returnarray + 1 ) == 1 )
                return 1;
            nodes[i]->used = 0;
        }
    }
    return 0;
}

int main(){
    char* tmp[] = {"hello","oeyh","aol", "loks", "sol"};
    int rets[5];
    if( ispath( tmp, 5, rets ) ){
        for( int i = 0; i < 5; i ++ ){
            printf(" %s ", tmp[rets[i]] );
        }
    }
}