Oly*_*uck 8 algorithm permutation
我在http://www.interviewstreet.com上遇到了一个问题.
Bob收到了Alice发送的长度为N的二进制字符串.他知道由于传输错误,最多K位可能已被破坏(因此被翻转).但是,他也知道Alice打算传输的字符串不是周期性的.如果字符串不能表示为连接多次的较小字符串,则该字符串不是周期性的.例如,"0001","0110"不是周期性的,而"00000","010101"是周期性字符串.现在他想知道Alice有多少可能的字符串传输.
首先,我使用二项式定理进行了一些测试,并通过使用它,我能够找到在给定字符串和多个损坏位的情况下可以表示字符串的不同方式.我的第二步是找到一种方法来查找周期性字符串的数量.我看到这可以通过带有素数长度的字符串轻松完成.这是通过检查是否有足够的0或1来填充字符串仅用0或1来完成.
1111111或0000000
现在我使用的是一种纯粹的强力算法,当涉及到任何类型的大字符串时,它都不会削减它.是否有任何类型的组合技术可以指出我有助于解决这个问题？谢谢.
计算长度为n的非周期字符串的数量：
\n\n计算长度为n的周期字符串的数量：
\n\n找到n的所有约数，除了 n 本身。例如：如果n =6 - 除数为 1,2,3。
\n\n（这里已经讨论过这种方法 ）
每个除数 m 可以用来表示 2^m 个周期串。例如
m=3: {000,...111} - 2^3 个周期字符串
\n\n所以对于n=6，有2+4+8个周期串
\n\n正如 Jeffery Sax 和 ANeves 指出的那样，其中一些周期字符串是相同的（例如 0* = 00* = 000*），因此我们必须消除这些。
\n\n一种简单的方法是将所有这些字符串添加到存储唯一元素（例如C++ 中的set）的关联容器中，并计算该容器中元素的数量。
\n\n更好的优化是：对于 m=m1，找到 m1 的所有除数，并避免添加这些集合中已有字符串的周期字符串。
下一步是计算任何这些周期字符串与接收到的字符串之间的汉明距离。如果小于K-则计数。
\n\n编辑：大 N 和小 K 的更好解决方案
\n\n检查字符串是否周期性的算法：
\n\n这可以通过将字符串与其自身的移位版本进行比较来完成。如果一个字符串与其 p 位循环移位相同，那么它的循环周期为 p。
\n\n因此，每次循环移位字符串一位 - 我们可以在最多楼层（N/2）字符串比较中检测它是否是周期性的。
\n\n计算可能传输的字符串
\n\n如果没有非周期性传输要求，并且我们收到 N 位消息 - 可能已传输的消息数为C(N, 0) + C(N, 1) + C(N, 2) + ... + C(N, K)
对于 N=1000 且 K=3：C(1000,0)+C(1000,1)+C(1000,2)+C(1000,3)= 166,667,501
\n\n（这是原始字符串中切换0/1/2/3位的组合数量）。
\n\n根据这个数字，我们需要减少无法传输的周期字符串的数量。
\n\n例如：如果接收到的字符串是000000并且K=2，我们可以确定发送的字符串不在{000000,001001,010010,100100}中。这些都是周期性的，与接收到的字符串的汉明距离最大为 K。
\n\nC(6,0)+C(6,1)+C(6,2)=1+6+15=22\n其中，4 个组合是周期性的。
\n\n算法：
\n\n我们将从接收到的字符串开始，并生成上述所有组合。对于每个组合，我们将检查它是否是周期性的。如果是这样 - 我们会将计数减 1。
\n