子序列的概率计算和算法
这是一个游戏，其中 1-50 张牌被分发给两个玩家，每个玩家有 10 张牌，并且顺序是随机的。目标是对所有卡片进行排序，谁先完成，谁就是胜利者。每当一个人可以从牌堆中拿起卡片时，他就必须更换现有的卡片。玩家不能交换他的牌。即只有他可以用牌堆中的牌替换他的牌。被丢弃的牌将按随机顺序返回牌堆。现在我需要编写一个程序来有效地执行此操作。
我想到了以下解决方案 1）找到给定的一组卡片中所有按升序排列的子序列 2）对于每个子序列，根据解决问题的方法的概率计算一个权重。 例如：如果我在索引 2,3,4 处有一个子序列 48,49,50 ，用这个子序列完成问题的概率是 0 。所以权重乘以 0 。 类似地，如果我在索引 3,4,5 处有一个序列 18,20,30，那么完成游戏的所有可能方法都不是为 6-10 选择 20 张可能的牌，为前 2 个位置选择 17 张可能的牌， 3）对于这副牌中的每张牌，我将扫描列表并重新计算子序列的权重以找到更合适的牌。
嗯，这个解决方案可能有很多缺陷，但我想知道 1）给定一个子序列，如何找到完成游戏的可能方式的概率？ 2）找到所有子序列的最佳算法是什么？
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?
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（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.