24小时热门版块排行榜

南方科技大学公共卫生及应急管理学院2026级博士研究生招生报考通知（长期有效）

返回列表

香果果洋洋

新虫 (初入文坛)

应助: 0 (幼儿园)
金币: 324.4
帖子: 47
在线: 6.9小时
虫号: 4383476
注册: 2016-01-27
性别: GG
专业: 组合数学

[求助] 排列组合已有1人参与

一个长度为n的向量，向量的元素由0，1排列而成。现知道其中有k个元素为1（n>=k），另外也知道这些1之间的位置信息：位置差1的有k1个，位置差2的有k2个……位置信息举例说明：假设有一个长度为10的上述0，1向量，已知在向量的第2、6、9位置上为1，其余为0。这些1之间的位置信息是指：位置差3的有一个，位置差4的有一个，位置差7的有一个。
能否有一种算法能找到一种满足这种排列要求的0，1向量。

发自小木虫Android客户端

回复此楼

» 猜你喜欢

三甲基碘化亚砜的氧化反应已经有4人回复
请问下大家为什么这个铃木偶联几乎不反应呢已经有5人回复
请问有评职称，把科研教学业绩算分排序的高校吗已经有5人回复
孩子确诊有中度注意力缺陷已经有12人回复
2025冷门绝学什么时候出结果已经有3人回复
天津工业大学郑柳春团队欢迎化学化工、高分子化学或有机合成方向的博士生和硕士生加入已经有4人回复
康复大学泰山学者周祺惠团队招收博士研究生已经有6人回复
AI论文写作工具：是科研加速器还是学术作弊器？已经有3人回复
论文投稿，期刊推荐已经有4人回复
硕士和导师闹得不愉快已经有13人回复

1楼2016-04-02 15:17:24

已阅回复此楼关注TA 给TA发消息送TA红花 TA的回帖

hank612

至尊木虫 (著名写手)

数学EPI: 14
应助: 225 (大学生)
金币: 14270.6
散金: 1055
红花: 95
帖子: 1526
在线: 1375.8小时
虫号: 2530333
注册: 2013-07-03
性别: GG
专业: 理论和计算化学

【答案】应助回帖

如果楼主手头有可以多项式因式分解的数学软件，问题会变得相对简单。

假设这k个球位置在a1,a2,...,ak处，那么乘积 $(x^{a_1}+x^{a_2}+\dots+x^{a_k})\cdot(x^{-a_1}+x^{-a_2}+\dots+x^{-a_k})$ 恰好包括了所有的相对距离 $\pm(a_i-a_j)$ 的信息(含重数), 因此，楼主把手头上数据数列转换成 x的幂次，再加上数据数列每项取负号后的幂次，再加上k（由k个点到自身的距离为0而产生）, 然后做因式分解，把因式重新组合成两个相等次数的多项式，立刻得到想要的位置序列。

譬如，假如k=4, 距离序列是(1,3,4,5,7,8), 那么要做因式分解的多项式是 $x^1+x^3+x^4+x^5+x^7+x^8+x^{-1}+x^{-3}+x^{-4}+x^{-5}+x^{-7}+x^{-8}+4$ ,
见下图。于是因子乘积 $(x+1)(x^7+x^2-x+1)=x^8+x^7+x^3+1$ 告诉我们四个位置为(0,3,7,8). 楼主还可以试试另外一个8次的因子 $(x+1)(x^7-x^6+x^5+1)=x^8+x^5+x+1$ ，得到位置(0,1,5,8). 而实际上，这两组位置在数轴上关于点x=4是中心对称的，它们应该算是同一组解。

Factor.png

赞一下

回复此楼

We_must_know. We_will_know.

2楼2016-05-29 22:16:07

已阅回复此楼关注TA 给TA发消息送TA红花 TA的回帖

相关版块跳转我要订阅楼主香果果洋洋的主题更新

返回列表