a**6
发帖数: 4 | 1 题不是原题, 改了点
给一手有序列n张的扑克牌, 无视花色, 只视数字(倒如: 4 9 7 7), 牌由无限副扑克抽
出来, 所以一个数字也能出现无数次, 求该序列在该手牌所能组合的所有序例中的顺
增的位置:
例: 4 9 7 7
4 7 7 9 – 1
4 7 9 7 – 2
4 9 7 7 – 3 ←
除此以外, 也限时, 所以不能用暴力生成所有组合
我的答法:
首先想到先排序再DFS, 每到leaf count+=1, leaf 是该序列就+1 之后return 或者将
counter写入class的member, 但这也可能要生成所有组合, 而且有n!组合, O(n!)就算
再优化也过不了
然后就是用dp, 从头算, 算第i张的时候就找出前面可以肯定的排序, 也就是(i-1)! 乘
以第i张在剩下卡牌可能出现的位置. 这算法很快, 但因为重复组合重复算, 对重复数
字组合无效
例4 9 7 7
4 7 7 9 – 1
4 7 7 9 – 1
4 7 9 7 – 3
4 7 9 7 – 3
4 9 7 7 – 5 ←
最后想了一整天, 没办法, 只好用greedy 给一个大约, 就是把以上得出的排名, 把排
在前面的组合除以可能重复的次数, 例如7 7 可以重复2! = 2次, 所以 本来是第5名的
把前面4个除2变成第3名, 但运作起来根本不準, 原因是int div不準, 本序也是重复等
结果没过, 被锯. 一直在想这题是有P答法我不知道, 还是是NP只想考考优化能力或者
是出考题的都不知道, 求这里高手指教 | b******b
发帖数: 713 | 2 sorry cannot type in Chinese, in general case, the possible number of
permutation of numbers with possible duplication can be calculated with, e.g
.
a1,a1,...a1,a2,a2...a2,a3,a3,...a3,ak,ak,...ak,
let's say we have i1 numbers of a1, i2 numbers of a2, ...ik numbers of ik,
and sum(i1, ...ik) =n, the number of possible permutation is:
n! / i1! * i2! * i3! ...* ik!
use this formula, you can quickly find out the number of sequence, e.g. in
your example, when start with 4, the number of sequence is 3! / 2! = 3
【在 a**6 的大作中提到】
: 题不是原题, 改了点
: 给一手有序列n张的扑克牌, 无视花色, 只视数字(倒如: 4 9 7 7), 牌由无限副扑克抽
: 出来, 所以一个数字也能出现无数次, 求该序列在该手牌所能组合的所有序例中的顺
: 增的位置:
: 例: 4 9 7 7
: 4 7 7 9 – 1
: 4 7 9 7 – 2
: 4 9 7 7 – 3 ←
: 除此以外, 也限时, 所以不能用暴力生成所有组合
: 我的答法:
| a**6
发帖数: 4 | 3 不是找number of sequence , 是找ascending order of given sequence in all
sequences, 例如 4 9 7 7 有 12 个组合, 要找出4977在12个组合中的顺序排名(第3名
),期间也想过用bisection, 但是tree不是对称 | l****5
发帖数: 5865 | | s********g
发帖数: 92 | 5 backstab的解答是对的 比如拿到41977这手牌 第一个数为1则index一定比41977小 个
数等于4 7 7 9全排列
第一个数选4 第二个数没有可能比1小 直接选1 第三个数选7则index一定比41977小 个
数等于 7 9全排列
所以41977的index等于 4!/2! ＋2!
【在 a**6 的大作中提到】
: 不是找number of sequence , 是找ascending order of given sequence in all
: sequences, 例如 4 9 7 7 有 12 个组合, 要找出4977在12个组合中的顺序排名(第3名
: ),期间也想过用bisection, 但是tree不是对称
| a**6
发帖数: 4 | 6 那我明白了,谢谢
DP那方法没错, 只是算前面的时候要算重复的, 具体就是1个loop就完了
答案是
index = 1
while hand:
head = hand[0]
indexInHead = sorted(hand).index(head)
dupCards = [card for card in hand if hand.count(card) > 1]
uniDupCards = dupCards.distinct()
numDupComboPoss = 1
for dupCard in uniDupCards:
numDupCombPoss *= fact(dupCards.count(dupCard))
index += fact(len(hand)-i-1)*indexInHead/numDupComboPoss
hand.remove(head)
return index
【在 s********g 的大作中提到】
: backstab的解答是对的 比如拿到41977这手牌 第一个数为1则index一定比41977小 个
: 数等于4 7 7 9全排列
: 第一个数选4 第二个数没有可能比1小 直接选1 第三个数选7则index一定比41977小 个
: 数等于 7 9全排列
: 所以41977的index等于 4!/2! ＋2!
| h*******l
发帖数: 22 | 7 正解
.g
【在 b******b 的大作中提到】
: sorry cannot type in Chinese, in general case, the possible number of
: permutation of numbers with possible duplication can be calculated with, e.g
: .
: a1,a1,...a1,a2,a2...a2,a3,a3,...a3,ak,ak,...ak,
: let's say we have i1 numbers of a1, i2 numbers of a2, ...ik numbers of ik,
: and sum(i1, ...ik) =n, the number of possible permutation is:
: n! / i1! * i2! * i3! ...* ik!
: use this formula, you can quickly find out the number of sequence, e.g. in
: your example, when start with 4, the number of sequence is 3! / 2! = 3
|
|
