版块导航: 正在加载中...

登录注册

应《网络安全法》要求，自2017年10月1日起，未进行实名认证将不得使用互联网跟帖服务。为保障您的帐号能够正常使用，请尽快对帐号进行手机号验证，感谢您的理解与支持！

24小时热门版块排行榜

>论坛更新日志 (4875)
>基金申请 (1505)
>有奖起名 (995)
>休闲灌水 (458)
>虫友互识 (457)
>海外博后 (443)
>文献求助 (390)
>博后之家 (288)
>论文投稿 (279)
>硕博家园 (248)
>考博 (206)
>导师招生 (203)
>学术会议 (192)
>考研 (191)
>找工作 (149)
>公派出国 (138)

返回列表

香果果洋洋

新虫 (初入文坛)

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

回复此楼

» 猜你喜欢

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