Given:
1. A list of strings
2. A reference string
3. x where x is an int
Pick out x strings from 1 to get the candidate string such that the BLEU score with the reference string is as high as possible.
I know the naive solution will be to get all possible x length strings and then calculate the BLEU score for all of them and choose the best one.
I wonder if I can do this greedily?
For a greedy algorithm, we need to prove two properties: 1) Greedy Choice property and 2) Optimal Substructure. I however, have not been able to prove or disprove it so far.