24小时热门版块排行榜

返回列表

当前只显示满足指定条件的回帖，点击这里查看本话题的所有回帖

香果果洋洋

新虫 (初入文坛)

应助: 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客户端

回复此楼

» 猜你喜欢

论文终于录用啦！满足毕业条件了已经有10人回复
2025年遐想已经有4人回复
投稿Elsevier的杂志（返修），总是在选择OA和subscription界面被踢皮球已经有8人回复
自然科学基金委宣布启动申请书“瘦身提质”行动已经有4人回复
求个博导看看已经有18人回复

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