论坛 › 编程擂台 › 完美间隔配对排列

mathe 发表于 2025-3-6 10:26:25

明白了，应该两个序列，其中一个0可以放在边界上，一个不允许。

mathe 发表于 2025-3-7 08:22:51

提交序列中，发现
A176127
表示了不带零情况的数目

mathe 发表于 2025-3-7 09:33:33

根据OEIS中链接，可以找到一篇文章，模仿这篇文章利用多项式解决这个问题，可以有下面代码，不过发现效率上比我前面代码提升不多，好处对内存需求非常之低
1. 允许头尾是0的情况
#include <iostream>

typedef __int128_t dtype;
#ifndef N
#define N 2
#endif
#define R (2*N+1)

dtype evalf(long v)
{
   int i,k;
   dtype prod=2*__builtin_popcountl(v)-R;
   for(i=1;i<=N;i++){
   long t= (v^(v>>(i+1)))&((1L<<(R-(i+1)))-1);
   prod*=(R-(i+1))-2*__builtin_popcountl(t);
   }
   long numneg = R-__builtin_popcountl(v);
   if(numneg&1)prod=-prod;
   return prod;
}

int main()
{
dtype v=0;
long i;
#pragma omp parallel for reduction(+:v)
for(i=0;i<(1L<<R);i++){
    dtype localv = evalf(i);
    v+=localv;
}
v>>=R;
std::cout<<(long)(v+1)/2<<std::endl;
return 0;
}

2. 不允许头尾是0的情况
#include <iostream>

typedef __int128_t dtype;
#ifndef N
#define N 2
#endif
#define R (2*N+1)

dtype evalf(long v)
{
   int i,k;
   long v2=v&~((1L<<(R-1))|1L);
   dtype prod=2*__builtin_popcountl(v2)-(R-2);
   for(i=1;i<=N;i++){
   long t= (v^(v>>(i+1)))&((1L<<(R-(i+1)))-1);
   prod*=(R-(i+1))-2*__builtin_popcountl(t);
   }
   long numneg = R-__builtin_popcountl(v);
   if(numneg&1)prod=-prod;
   return prod;
}

int main()
{
dtype v=0;
long i;
#pragma omp parallel for reduction(+:v)
for(i=0;i<(1L<<R);i++){
    dtype localv = evalf(i);
    v+=localv;
}
v>>=R;
std::cout<<(long)(v+1)/2<<std::endl;
return 0;
}

缺乏的还是算力
原理是定义函数\[ F(n)=\left(\sum_{k=0}^{2n}x_k\right)\prod_{s=1}^n \sum_{k=0}^{2n-s-1}x_kx_{k+s+1}\\G(n)=\left(\sum_{k=1}^{2n-1}x_k\right)\prod_{s=1}^n \sum_{k=0}^{2n-s-1}x_kx_{k+s+1}\]
那么多项式中\(\D\prod_{k=0}^{2n}x_k\)的系数就代表了答案。也就是表达式中各乘积项分别代表0，1，2，..., n出现的位置。
由于多项式是齐次的，每项次数都是2n+1,所以除了上面这一项，其余项都会缺乏某个变量，于是函数\(\D F(n)\prod_{k=0}^{2n}x_k\)对$x_k$取遍-1和1的组合进行累加，那么所有其他项全部消除，而只留下\(\D \prod_{k=0}^{2n}x_k^2\)项，它被重复累加了$2^{2n+1}$次，结果除以这个常数即可

mathe 发表于 2025-3-8 08:30:00

mathe 发表于 2025-3-6 10:15
很奇怪，我计算的部分结果和大家相同，但是有些不同
1 1
2 1


n=21时为443385597340544,这时两个序列相等

王守恩 发表于 2025-3-8 11:34:58

一眨眼 9 年！藉众多网友接力, 这串数已经有20个数!谢谢各位网友！

题目：将 0,1,1,2,2,…,n,n 排成一列，
要求两个 k 中间有 k 个数（k=1,2,…,n)，
譬如。
1有1种排法： ("101")
2有1种排法 :("12102")
3有1种排法：("1312032")
4有3种排法：("131423024" "141302432" "240231413")
5有11种排法,

我们约定：第1个数(不能是0)要比最后1个数小。

011,
021,
031,
043,
0511,
0638,   
07130,   
08638,    谢谢 aimisiyou！谢谢 adlpg070！
094158,    谢谢 aimisiyou！谢谢 adlpg070！
1023384,   谢谢 aimisiyou！谢谢 adlpg070！
11124520,   谢谢 aimisiyou！谢谢 adlpg070！
12847484,   谢谢 aimisiyou！谢谢 adlpg070！
136987380,   谢谢网友时间的音符(Excel论坛)！
1453746000,   谢谢网友yjh_27(Excel论坛)！
15400346544,    谢谢网友uk702！
163529108816,    谢谢网友l4m2！
1735963592624,    谢谢网友l4m2！
18351432650816,    谢谢网友l4m2！
193346590201888,   谢谢网友l4m2！
2036341624453568,   谢谢网友l4m2！
......
谢谢各位网友！

mathe 发表于 2025-3-8 20:45:35

n=22结果为5245806847699840

northwolves 发表于 2025-3-8 21:03:55

mathe版主算力太高

A381759

A381760

王守恩 发表于 2025-3-9 06:45:40

一个好玩的游戏——原题是这样的。

1,1,2,2,3,3——2,3,1,2,1,3——满足2个1中间有1个数, 2个2中间有2个数, 2个3中间有3个数。

1,1,2,2,3,3,4,4——2,3,4,2,1,3,1,4——满足2个1中间有1个数, 2个2中间有2个数, 2个3中间有3个数, 2个4中间有4个数。

原题三十年前很流行, 几乎每个小朋友都在做。遗憾的是, 不是每对数都有答案。本人在此基础上加了1个0, 能使每对数都有答案, 可以连续做题目了。

同事们搓麻将,打扑克, 小朋友也是挺烦人的。我说我来出道题, 用0,1,1——0,1,1,2,2把题意解释清楚, 就让小朋友自己动手去折腾, 只要找到1个答案就可以！做对了再发2张牌, 骗小朋友蛮好的。

我的初衷是每对数找1个答案就可以！！尽可能往前走！！！享受每次找到答案的喜悦, 更鼓励自己去寻找下一个答案的冲动。也许来个小朋友第二天还在兴奋的告诉我：我把9做出来了！！

对于每个数都有解, 我好像不怀疑, 但不曾想某个数有多少解, 更不曾想有怎么多解！谢谢各位网友！

做题目最好的方法是动手, 希望看到道题的网友, 享受每次找到答案时的喜悦, 更在意信任自己一定能找到答案的信念, 因为探索比结果更诱人。

王守恩 发表于 2025-7-31 16:50:50

继续整理。

题目：将 0, 1, 1, 2, 2, 3, 3, …, n, n 排成一列,要求两个 k 中间有 k 个数 (k = 1, 2, 3,…, n)。

譬如。
1有1种排法:("101")
2有1种排法:("12102")
3有1种排法：("1312032")
4有3种排法：("131423024" "141302432" "240231413")
5有11种排法: ("13145320425" "14135243205" "14153042352" "15103425324" "15104235243" "15123425304" "20425314135" "20524131543" "23425314105" "30523421514" "31513420524")
6有38种排法: ("1014562342536" "1014635243265" "1015364235246" "1015623425364" "1016352432654" "1016425324635" "1314635240265" "1316435024625" "1413564320526" "1415364235206" "1415604235263" "1416254230653"
"1416354032652" "1510463524326" "1510642532463" "1512642530463" "1514603542362" "1516304532642" "1612532463504" "1613504362542" "2042635413165" "2062514136543" "2342635410165" "2362531416504" "2462514136503"
"2532463514106" "2562141536403" "2612145360435" "2612153460354" "2632503461514" "3046325421615" "3062352416154" "3151364250246" "3161345026425" "3450364251216" "4161345236205" "4260245316135" "4263245316105")

我们约定：第1个数(不能是0)要比最后1个数小。

011,
021,
031,
043,
0511,
0638,   
07130,   
08638,    谢谢 aimisiyou！谢谢 adlpg070！
094158,    谢谢 aimisiyou！谢谢 adlpg070！
1023384,   谢谢 aimisiyou！谢谢 adlpg070！
11124520,   谢谢 aimisiyou！谢谢 adlpg070！
12847484,   谢谢 aimisiyou！谢谢 adlpg070！
136987380,   谢谢网友时间的音符(Excel论坛)！
1453746000,   谢谢网友yjh_27(Excel论坛)！
15400346544,    谢谢网友uk702！
163529108816,    谢谢网友l4m2！
1735963592624,    谢谢网友l4m2！
18351432650816,    谢谢网友l4m2！
193346590201888,   谢谢网友l4m2！
2036341624453568,   谢谢网友l4m2！
21443385597340544,   谢谢网友mathe！
225245806847699840,   谢谢网友mathe！
......
A381760——1, 1, 1, 3, 11, 38, 130, 638, 4158, 23384, 124520, 0847484, 6987380, 53746000, 400346544, 3529108816, 35963592624, 351432650816, 3346590201888, 36341624453568, 443385597340544, 5245806847699840,

A381759——1, 1, 3, 5, 11, 38, 182, 938, 4158, 23384, 160104, 1063772, 6987380, 53746000, 479965824, 4182552416, 35963592624, 351432650816, 3860219984448, 41614300175968, 443385597340544, 5245806847699840,
A381760——1, 1, 1, 3, 11, 38, 130, 638, 4158, 23384, 124520, 0847484, 6987380, 53746000, 400346544, 3529108816, 35963592624, 351432650816, 3346590201888, 36341624453568, 443385597340544, 5245806847699840,
A176127——0, 0, 2, 2, 00, 00, 052, 300, 0000, 00000, 035584, 0216288, 0000000, 00000000, 079619280, 0653443600, 00000000000, 000000000000, 0513629782560, 05272675722400, 000000000000000, 0000000000000000,
7598911885030976, 93690316113031872, 0, 0, 223367222197529806464, 3214766521218764786304, 0, 0,
A014552——0, 0, 1, 1, 00, 00, 026, 150, 0000, 00000, 017792, 0108144, 0000000, 00000000, 039809640, 0326721800, 00000000000, 000000000000, 0256814891280, 02636337861200, 000000000000000, 0000000000000000,
3799455942515488, 46845158056515936, 0, 0, 111683611098764903232, 1607383260609382393152, 0, 0,

A381759——a(n) = A381760(n) + A176127(n).
A176127——a(n) = 2 * A014552(n)

我们这串数——A381760——还是很关键的一串数。 比较——A014552——我们还应该有潜力！

王守恩 发表于 2025-8-1 10:59:19

我们只是想要一个答案——好玩！！！

a(0)=0,
a(1)=1,0,1,
a(2)=1,2,1,0,2,
a(3)=1,3,1,2,0,3,2,
a(4)=3,1,4,1,3,2,0,4,2,
a(5)=3,1,5,1,3,4,2,0,5,2,4,
a(6)=5,3,1,6,1,3,5,4,2,0,6,2,4,
a(7)=5,3,1,7,1,3,5,6,4,2,0,7,2,4,6,
a(8)=7,5,3,1,8,1,3,5,7,6,4,2,0,8,2,4,6,
a(9)=7,5,3,1,9,1,3,5,7,8,6,4,2,0,9,2,4,6,8,

——把头尾去掉——

a(0)=0,
a(1)=1,0,——"1"排那里?——答案是唯一的。
b(2)=2,1,0,——"2"排那里?——答案是唯一的——"1"排那里?——答案是唯一的。
b(3)=3,1,2,0,——"3"排那里?——答案是唯一的——"1"排那里?——答案是唯一的——"2"排那里?——答案是唯一的。
b(4)=4,1,3,2,0,——"4"排那里?——答案是唯一的——"1"排那里?——答案是唯一的——"3"排那里?——答案是唯一的,...
b(5)=5,1,3,4,2,0,——"5"排那里?——答案是唯一的——"1"排那里?——答案是唯一的——"3"排那里?——答案是唯一的,...
b(6)=6,1,3,5,4,2,0.
b(7)=7,1,3,5,6,4,2,0,
b(8)=8,1,3,5,7,6,4,2,0,
b(9)=9,1,3,5,7,8,6,4,2,0,
b(10)=10,1,3,5,7,9,8,6,4,2,0,
b(11)=11,1,3,5,7,9,10,8,6,4,2,0,
b(12)=12,1,3,5,7,9,11,10,8,6,4,2,0,
b(13)=13,1,3,5,7,9,11,12,10,8,6,4,2,0,
b(14)=14,1,3,5,7,9,11,13,12,10,8,6,4,2,0,
b(15)=15,1,3,5,7,9,11,13,14,12,10,8,6,4,2,0,

——b(n)还是回归a(n)——答案是唯一的！！！

查看完整版本: 完美间隔配对排列