CODEWITHSUNDEEP
algorithmmathdynamic-programming
Yippie-Ki-Yay
Yippie-Ki-Yay

Reputation: 22814

Dynamic programming - basic algorithm

Consider the following problem:

We have two sequences of cargo loads which can contain either grain or cattle. Now, we also have a sequence of cargo loads which we want to get from the initial sequences.

The initial sequences might look the following way, sequence we want to achieve is displayed to the right:

C   G                     
G   C                     
C   G                     G
C   C                     C
G   G                     G
 \ /
  ?

Now, at the ? spot one can pick the left cargo load or the right one. The picking should be done to match the wanted final sequence.

For example, we should pick Grain at the beginning and then the picture would become this:

    G                     
C   C                     
G   G                     G
С   C                     C
С   G                     G
 \ /
  ?  ---> G (we took it from the left)

So, does this problem has a well-known name? I realize that this can be solved by a simple dynamic programming algorithm, but I want to know more.

Basically, if there is something more to read about this problem, I would like to read it. For example, I have no ideas about the complexity of the algorithm if we have an infinite number of finite input sequences.

Upvotes: 2

Views: 444

Answers (2)

Per
Per

Reputation: 2624

A formal language theorist would describe your problem as testing whether a string w is a shuffle of two strings u, v. There appears to have been some work on the complexity of recognizing languages constructed with shuffles (e.g., the shuffle of a context-free language and a regular language is context-free).

Upvotes: 2

solendil
solendil

Reputation: 8468

I don't have much insight to share, but here it is:

  • Let's call the cargoes 0 and 1 instead of C and G, moreover, let's label the two queues 0 and 1 instead of right and left.

  • First the algorithm can not be solved with infinite (streamed) input sequences. In the case of two input seqs having only 0 then a 1 outside of the "streaming visibility window", you can't aim for this 1 if your result sequence needs it, so you could be stuck, while there was an answer.

  • Since we can't talk about infinity, let's analyze the complexity of a solver. I can't see much better than your algorithm... If result sequence has length m and we modelize the result as a sequence of 0 and 1 (for right and left), there are 2^m possible solutions. If we consider that at every step, on average there's one chance out of two that only one input sequence will be valid, it means the other sequence will be invalid as well as other subsequent sequences. This should lead to an O(m!) complexity.

Upvotes: 2

Related Questions