3
组合的编码/解码
source link: http://z-rui.github.io/post/2020/07/combination-code/
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.
组合的编码/解码
Fri Jul 24, 2020
n 元集合 {0,1,…,n-1} 的 k 元子集共有 (nk) 个。 设某个子集的元素为 c1<c2<⋯<ck， 则该子集可以编码为 (ckk)+⋯+(c22)+(c11).
此编码最小值为 0， 最大值为 (n−1k)+⋯+(n−k+12)+(n−k1)=(nk)−1. 上式的证明： 在两边加上 (n−k0) 并使用恒等式 (nk)=(n−1k−1)+(n−1k)。
Recommend
About Joyk
Aggregate valuable and interesting links.
Joyk means Joy of geeK