Does Two Integer arrays Come from one sequence

Question:

There is a list of int arrays; the next int array is the explanation of the previous one.

For example, if the first one is [1], the next int array would be [1, 1], it means the previous array has a number one, the next array would be [2, 1], means the previous array has two one, and so on.

1

1 1

2 1

1 2 1 1

1 1 1 2 2 1

3 1 2 2 1 1

So the question would be: given a two int arrays A and B, you need determine whether they come form one sequence? In other word, whether you can induce from A to B, or from B to A?

Answer:

It seems that we can just induce from A, and get its next int array, and its next's next array, if one int array equals B, then we can return true.

But this problem is that what if A and B don't come from one sequence, when we stop?

We don't know.

In this problem, we can think reversely, if we starts from A, and get A's previous array, if it equals B, we can return true, if not, we continue. But if not, when we stop?

The first case: we can’t conclude previous array from the curry array:

Two cases:

1.      When the current int array has odd numbers, we stop, as it's impossible to get its previous array. The reason is simple: (a[i], b[i]) describes one item of previous array, if current array has odd numbers, (a0, b0) .. (a[n], b[n]), a[n+1], a[n+1] can't describe one item of previous array.

2.      When the current int array has even digits, but have some invalid pairs, such as (0 1).

Another case: if we deduce from A, and get it's parent, and its parent's parent, what if we get A again, if we continue, it will loop for ever. So in this case, we should return false, why?

A's parent array A[p'] is unqiue, A[p']'s parent A[p''] is also unique.

..

A[p'']

A[p']

A <--

..

...

A[p'']

A[p']

A <--

So the whole array sequence would be a loop. if we search from A, and meet A again, and no B during the path. So B would not be in the sequence.

Also remember that if the previous process determines whether B is in front of A in one sequence, we still need determine whether A is in front of B in some sequence.

Code:

The complete algorithm/test code and also many other algorithm problems and solutions are available from https://github.com/jefferyyuan/myAlgorithms.

package org.codeexample.jefferyyuan.sameSequence;
import java.util.ArrayList;
import java.util.List;
import org.codeexample.common.Utils;

public class AlgorithmSameSequnce {
 
    /**
     * see
     * http://programer-tips.blogspot.com/2011/08/
         * two-integer-arrays-from-same-sequence.html
     * <p>
     * 
     * @param arrayA
     * @param arrayB
     * @return
     */
    public static boolean isInSameSequnce(int[] arrayA, int[] arrayB) {
        return isInSameSequnce(Utils.toList(arrayA), Utils.toList(arrayB));
    }
 
    /**
     * see
     * http://programer-tips.blogspot.com/2011/08/
         * two-integer-arrays-from-same-sequence.html
     */
    public static boolean isInSameSequnce(List<Integer> listA,
            List<Integer> listB) {
        List<Integer> listACopy = new ArrayList<Integer>(listA);
        if (isInSameSequnceImpl(listA, listACopy, listB))
            return true;
        List<Integer> listBCopy = new ArrayList<Integer>(listB);
        return isInSameSequnceImpl(listB, listBCopy, listA);
    }
 
    private static boolean isInSameSequnceImpl(List<Integer> listA,
            List<Integer> interim, List<Integer> listB) {
        List<Integer> previous = getPrevious(interim);
        if (previous.equals(listB))
            return true;
        // meet listA again
        if (previous.equals(listA))
            return false;
        if (previous.isEmpty())
            return false;
        return isInSameSequnceImpl(listA, previous, listB);
    }
 
    /**
     * Return the previous array, for example, the previous array of [2, 1]
     * would be [1, 1], the previous of [1, 2, 1, 1] would be [2, 1]. 
 
     * If the list is invalid or can't induce its previous array, return one
     * empty list.
     * 
     * @param list
     * @return
     */
    private static List<Integer> getPrevious(List<Integer> list) {
        ArrayList<Integer> result = new ArrayList<Integer>();
        // if the list has odd number, return empty list;
        if (list.size() % 2 == 1)
            return result;
 
        for (int i = 0; i <= list.size() - 2;) {
            int times = list.get(i++);
 
            // no previous row for input [0, 1],
            if (times == 0)
                return new ArrayList<Integer>();
            int digit = list.get(i++);
            for (int j = 0; j < times; j++) {
                result.add(digit);
            }
        }
        return result;
    }
}