can anyone help with a possible dynamic programming algorithm

Let me first apologise for the crude manner in which I am about to phrase my question. I have been refered here by a member on another site who tells me that i am looking for a dynamic programming algorithm....my question is as follows.

I am trying to sort through some data and need to find a possible sequence in the numbers Both sets of data include the same numbers listed in different orders as in the example below.

54 47 33 58 46 38 48 37 56 52 61 25 ………………first set

54 52 33 61 38 58 37 25 48 56 47 46 ………………second set

In this example Reading from left to right the numbers 54 52 61 and 25 occur in both sets in the same order.

So other possible solutions would be…

54 52 61 25

54 33 58 46

54 33 46

54 33 38 48 56

54 48 56…. Etc.

Although this can be done by hand, I have tons of this to get through and I keep making mistakes. Does anyone know of an existing program or script that would output all of the possible开发者_运维问答 solutions?

I understand the basic structure of c++ and virtual basic programs and should be able to cobble something together in ether but to be honest I haven’t done any serious programing since the days of the zx spectrum, so please go easy on me. my main problem however is not with the program language itself but that for some reason, I am finding it impossible to catalogue the steps required in order to complete this task in English let alone in any other language.

Darcy

---

Sounds like you are looking for 'all common subsequences (ACS)', which is a cousin of the (more common) longest common subsequence problem (LCS).

Here's a paper discussing ACS (though they focus on just counting subsequences, not enumerating).

To come up with an algorithm you should define the desired output more precisely. For the sake of argument, say you want the set of subsequences not contained in any longer subsequence. Then one algorithm would be:

1) Apply the DP algorithm for LCS, generating the alignment/backtrack matrix

2) Backtrack all possible LCS, marking the alignment positions visited.

3) Select the largest element of the matrix not yet marked (longest remaining subsequence)

4) Backtrack, recording the sequence and marking visited alignment positions.

5) While there exists an unmarked alignment positions, goto (3)

Backtracking in your case is complicated because you will have to visit all possible paths (called "all longest common subsequences"). You can find example implementations of LCS here, which may help to get you started.

---

I wrote this code and it outputs the longest common sequence. It is not super optimized though, the order is O(n*m) n-> array1 size, m-> array2 size:

private void start() {
    int []a = {54, 47, 33, 58, 46, 38, 48, 37, 56, 52, 61, 25};
    int []b = {54, 52, 33, 61, 38, 58, 37, 25, 48, 56, 47, 46};

    System.out.println(search(a,b));
}

private String search(int[] a, int[] b)
{
    return search(a, b, 0, 0).toString();       
}

private Vector<Integer> search(int[] a, int[] b, int s1, int s2) {

    Vector<Vector<Integer>> v = new Vector<Vector<Integer>>(); 

    for ( int i = s1; i < a.length; i++ )
    {
        int newS2 = find(b, a[i], s2);
        if ( newS2 != -1 )
        {
            Vector<Integer> temp = new Vector<Integer>();
            temp.add(a[i]);
            Vector<Integer> others = search(a, b, i+1, newS2 + 1); 
            for ( int k = 0; k < others.size(); k++)
                temp.add( others.get(k));
            v.add(temp);
        }
    }

    int maxSize = 0;
    Vector<Integer> ret = new Vector<Integer>();
    for ( int i = 0; i < v.size(); i++)
        if ( v.get(i).size() > maxSize )
        {
            maxSize = v.get(i).size(); 
            ret = v.get(i);
        }

    return ret;
}

private int find(int[] b, int elemToFind, int s2) {
    for ( int j = s2; j < b.length; j++)
        if ( b[j] == elemToFind)
            return j;
    return -1;
}