Probability computation and algorithm for subsequences

Question

Here is a game where cards 1-50 are distributed to two players each having 10 cards which are in random order. Aim is to sort all the cards and whoever does it first is the winner. Every time a person can pick up the card from the deck and he has to replace an existing card. A player can't exchange his cards. i.e only he can replace his card with the card from the deck.A card discarded will go back to deck in random order. Now I need to write a program which does this efficiently.

I have thought of following solution 1) find all the subsequences which are in ascending order in a given set of cards 2) for each subsequence compute a weight based on the probability of the no of ways which can solve the problem. for ex: If I have a subsequence 48,49,50 at index 2,3,4 probability of completing the problem with this subsequnce is 0. So weight is multiplied by 0 . Similarly if I have a sequence 18,20,30 at index 3,4,5 then no of possible ways completing the game is 20 possible cards to chose for 6-10 and 17 possible cards to chose for first 2 position , 3) for each card from the deck, I'll scan through the list and recalculate the weight of the subsequnces to find a better fit.

Well, this solution may have lot of flaws but I wanted to know 1) Given a subsequence , how to find the probability of possible ways to complete the game? 2) What are the best algorithm to find all the subsequences?

Keratitis

Please clarify: (1) Does the player see the card from the deck before selecting the replaced card or does he have to throw off the card, then get the new card? (2) Does he see other player's cards (the ones he throws off or gets)? (3) Do you want to consider the knowledge about which cards are in the deck? – Graaf

Answer 1

So if I understand correctly, the goal is to obtain an ordered hand by exchanging as few cards as possible, right? Have you tried the following approach? It is very simplistic, yet I would guess it has a pretty good performance.

N=50
I=10
while hand is not ordered:
   get a card from the deck
   v = value of the card
   put card in position round(v/N*I)

Quagmire

can't this go in to an infinite loop? – Lardner

no, i'm quite sure this converges rather quickly. My algorithm casts the problem as a coupon collector's problem which has quasilinear expected time. It is simplistic because it does not try to take advantage of the initial hand, but I suspect only minor improvements can be obtained if you do. – Quagmire