二进制字符串排列

Question

我在 http://www.interviewstreet.com 上遇到问题。

Bob 收到了 Alice 发送的长度为 N 的二进制字符串。他知道由于传输错误，多达 K 位可能已被损坏（并因此被翻转）。然而，他也知道爱丽丝想要传输的字符串不是周期性的。如果一个字符串不能表示为连接一定次数的较小字符串，则该字符串不是周期性的。例如，“0001”、“0110”不是周期性的，而“00000”、“010101”是周期性字符串。 现在他想知道 Alice 可以传输多少个可能的字符串。

因此，首先我用二项式定理做了一些测试，通过使用它，我能够找到给定一个字符串和许多损坏的位可以表示一个字符串有多少种不同的方式。我的第二步是找到一种方法来查找周期字符串的数量。我发现使用具有素数长度的字符串可以轻松完成此操作。这是通过检查是否有足够的 0 或 1 来仅用 0 或 1 填充字符串来完成的。

1111111 或 0000000

现在我使用纯粹的强力算法，当涉及到任何类型的大字符串时，它不会削减它。有人可以向我指出任何类型的组合技术可以帮助解决这个问题吗？谢谢。

Answer 1

利奥尔走在正确的道路上。

长度为 N 的字符串总数为 2^N。其中一些是周期性的。其他人则不然。我们将周期字符串的数量称为A(N)，将非周期字符串的数量称为B(N)。那么

A(N) + B(N) = 2^N

如果我们将长度为 1 的字符串定义为非周期性的，那么

A(1) = 0
B(1) = 2

现在让我们假设 N > N。 1..那么长度为N的周期串集合包括周期短于N的周期串。然而，对于长度为 N 的非周期字符串集来说，情况并非如此。

长度为 N 的周期性字符串集合由长度为 n 的约数的非周期性字符串的重复组成，包括长度为 1 的字符串。换句话说：

A(N) = sum(B(k) where k divides N and k < N)

例如：

A(6) = B(1) + B(2) + B(3)
     = (2^1 - A(1)) + (2^2 - A(2)) + (2^3 - A(3))
     = 2 + (4 - B(1)) + (8 - B(1))
     = 2 + 2 + 6
     = 10

现在我们有一个关于长度N的周期和非周期字符串数量的递推方程。

不幸的是，这对我们回答实际问题没有多大帮助。

这个问题意味着 Bob 收到了一个特定的字符串，他想知道有多少个非周期字符串与该字符串相差最多 K 位。接收到的字符串可能有 C(N,K) 种可能的突变，而这些突变可能是传输的字符串。我们需要从中减去该集合中周期串的数量。我们该怎么做呢？

首先，我们可以观察到任何周期串都是非周期串的重复。因此，对于每个潜在周期 k（N 的除数），我们查看长度 k 的子串。如果所有字符串与公共字符串的差异加起来不超过 K 位，则该公共字符串是周期字符串的基础，我们应该将计数减一。如果最小距离为d，并且K - d > N/k，那么我们可以翻转每个子字符串中的各个位并且仍然有匹配项，并且我们必须相应地减少计数。

Answer 2

计算长度为n的非周期字符串的数量：

• 字符串总数：2ⁿ
• 减去长度为n的周期字符串的数量

计算周期字符串的数量关于长度n：

• 找到n的所有约数，除了n本身。例如：如果n=6 - 除数为1,2,3。

  （此处讨论了此方法）< /p>

• 每个除数 m 可用于表示 2^m 个周期字符串。例如

• m=1: {0,1} - 2^1 个周期字符串
• m=2: {00,01,10,11} - 2^2 个周期字符串

• m=3: {000,...111 } - 2^3 周期字符串

  因此，对于 n=6，有 2+4+8 个周期串

  正如 Jeffery Sax 和 ANeves 指出的，其中一些周期字符串是相同的（例如 0* = 00* = 000*），因此我们必须消除这些。

  一个简单的方法是将所有这些字符串添加到存储唯一元素的关联容器中（例如 在 C++ 中设置），并计算该容器中的元素数量。

  更好的优化是：对于 m=m1，找到 m1 的所有除数，并避免添加这些集合中已有字符串的周期性字符串。

下一步是计算任何这些周期字符串与接收到的字符串之间的汉明距离 。如果小于K-则计数。

---

编辑：大 N 和小 K 的更好解决方案

检查字符串是否周期性的算法：

这可以通过将字符串与其自身的移位版本进行比较来完成。如果一个字符串与其 p 位循环移位相同，那么它的循环周期为 p。

因此，每次循环移位字符串一位 - 我们可以在最多楼层（N/2）字符串比较中检测它是否是周期性的。

计算可能传输的字符串

如果没有非周期性传输要求，并且我们收到了 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

（这是原字符串中切换0/1/2/3位的组合数）。

根据这个数字，我们需要减少无法传输的周期字符串的数量。

例如：如果接收到的字符串是000000并且K=2，我们可以确定发送的字符串不在{000000,001001,010010,100100}中。这些都是周期性的，与接收到的字符串的汉明距离最大为 K。

C(6,0)+C(6,1)+C(6,2)=1+6+15=22
其中，有 4 个组合是周期性的。

算法：

我们将从接收到的字符串开始，并生成上述所有组合。对于每个组合，我们将检查它是否是周期性的。如果是这样 - 我们会将计数减 1。

Answer 3

Lior 和 Jeffrey 的答案构成了解决该问题的基础，但本文仍有待解决的一个有趣问题是，如何有效地计算给定 [input string, N, K]。我的回答主要集中在这一点上。

正如 Lior 和 Jeffrey 所指出的，在检查周期性字符串时，我们只需要关心长度等于 n 的约数的子字符串。让我们看一个例子，看看实现这一目标的效率如何。

周期为 m 的周期串的数量

假设输入字符串为

0110 0011 0101 0001

，让我们尝试找到周期为 m=4 的周期串的数量

第一位

如果我们比较每个子串的第一位，我们会发现它们全部都是是0。如果我们假设所有子串中的所有后续位都相同，则在执行 0 位翻转或 4 位翻转时，可以使输入字符串成为周期性的（周期为 4）。

0110 0011 0101 0001
^    ^    ^    ^
Number of 0s = 4
Number of 1s = 0
Number of bitflips to make all 0s to 1s = 4
Number of bitflips to make all 1s to 0s = 0


Number of periodic strings with period=4 for:
k = 0  =>  1
k = 4  =>  1

现在我们知道存在 2 个周期性字符串，一个用于 k=0，另一个用于 k=4（假设所有子串中的后续位都相同）。

第二位

现在让我们进入第二位。

0110 0011 0101 0001
 ^    ^    ^    ^
Number of 0s = 2
Number of 1s = 2
Number of bitflips to make all 0s to 1s = 2
Number of bitflips to make all 1s to 0s = 2

但是等等，上面的陈述是正确的，前提是子串中当前位之前的所有位也有助于使字符串具有周期性。我们知道，只有 k=0 和 k=4 各自使字符串周期到第 1 位。

因此，当考虑到第 2 位之前的所有位时，我们可以在以下 4 种情况下获得周期字符串：

When previousK = 0:
    Flip the 2 `0`s to `1`s => new k = 2
    Flip the 2 `1`s to `0`s => new k = 2
When previousK = 4:
    Flip the 2 `0`s to `1`s => new k = 6
    Flip the 2 `1`s to `0`s => new k = 6

Number of periodic strings with period=4 for:
k = 2  =>  2
k = 6  =>  2

第三位

转到第三位，我们将看到：

0110 0011 0101 0001
  ^    ^    ^    ^
Number of 0s = 2
Number of 1s = 2
Number of bitflips to make all 0s to 1s = 2
Number of bitflips to make all 1s to 0s = 2

We can get a periodic string in the following 4 cases:
When previousK = 2:
    Flip the 2 `0`s to `1`s => new k = 4
    Flip the 2 `1`s to `0`s => new k = 4
When previousK = 6:
    Flip the 2 `0`s to `1`s => new k = 8
    Flip the 2 `1`s to `0`s => new k = 8

Number of periodic strings with period=4 for:
k = 4  =>  4
k = 8  =>  4

第四位

对于第四位也是最后一位：

0110 0011 0101 0001
   ^    ^    ^    ^
Number of 0s = 1
Number of 1s = 3

We can get a periodic string in the following 4 cases:
When previousK = 4:
    Flip the 1 `0`s to `1`s => new k = 5
    Flip the 3 `1`s to `0`s => new k = 7
When previousK = 8:
    Flip the 1 `0`s to `1`s => new k = 9
    Flip the 3 `1`s to `0`s => new k = 11

Number of periodic strings with period=4 for:
k = 5  =>  4
k = 7  =>  4
k = 9  =>  4
k = 11 =>  4

我们现在完成了加上子串的最后一位以及最后一步中各种 k 值的周期串的总数，得出 16。

递归关系和伪代码

让我们表示任何变化的 k 的周期串的当前计数从使用 R[k] 将 1 转换为 K。对于每次迭代，我们需要查找前一次迭代的 R[] 值。

我们在每次迭代中最终要做的事情是：

for offset = 0 to periodLen - 1
    flip R[] and previousR[]

    for currentK = 1 to K
        R[currentK] = 0

    numZeroes = 0
    for (pos = offset; pos < n; pos += periodLen)
        if (str[pos] == '0')
            ++numZeros

    numOnes = (n / m) - numZeroes;

    for currentK = 1 to K
        if m == 0
            R[currentK + numZeroes] = 1
            R[currentK + numOnes] = 1
        else if (previousR[currentK] > 0)
            R[currrentK + numZeroes] += previousR[currentK]
            R[currentK + numOnes] += previousR[currentK]

    totalPeriodicCount = 0
    for currentK = 1 to K
        totalPeriodicCount += R[currentK]

如果我们通过从最低到最高迭代所有周期来执行上述过程，我们将获得所有周期字符串的计数。将选择的周期将是小于 N 的 N 的约数。从最低到最高的顺序查看它们会有优势，请阅读下一节以了解详细信息。

考虑可被较小周期整除的周期

仔细观察，您会发现我们还会多次计算某些周期字符串。

例如。以下周期字符串：

0001 0001 0001 0001

最终将被计为 m = 4 和 m = 8 的一部分

让 C[m] 表示在长度为 的周期内获得的周期字符串的总数m 使用上面的伪代码获得。令C[m']表示使用长度为m的周期获得的周期串的实际计数，但不计算使用periods 可以形成的周期串。 m

更具体地说，如果当前周期 m 具有除数 t、u 和 v，它们是小于 m，那么我们将计算周期 t、u 和 v 周期字符串的数量同样，即

C[m] = C[t'] + C[u'] + C[v'] + C[m']

当计算所有 m 值的周期串总数时，我们需要注意排除 C[t]、C[u] 和 C[v] 并仅考虑 C[m']。

因为当我们计算 C[m] 时，我们已经计算了 C[t']、C[u'] 的值> 和 C[v']，我们只需查找它们并用 C[m] 减去它们即可得到 C[m']。我将把这个简单的部分作为读者的练习。

C[m'] = C[m] - C[t'] - C[u'] - C[v']

Answer 4

checkperiodic(char [] string, int i, int length)
{
for(l=i; l <=length-i ; l=l+i)
if(strncmp(string, &string[l],i) != 0)
    return 0;
return 1;
}

N=strlen(string);
n= sqrt(N);
for(i=2;i <= n; i++)
{
if (N%i == 0)
    if(checkperiodic(string,i,N) || checkperiodic(string,N/i,N))
        break;
}

复杂度 N^1/2 * N * （除数之和）

Answer 5

扩展 Lior Kogan 的答案 二进制字符串排列

设 F(n) 为非周期数可以形成给定长度n的字符串。

为了找到 n 的非周期字符串 F(n) 的数量，我们需要从 n 的所有排列中消除所有 F(m)，其中 m 是 n 的约数。

| n |     m | F(m)                     | answer |
| 1 |       | 2^1                      |      2 |
| 2 |     1 | 2^2-F(1)                 |      2 |
| 3 |     1 | 2^3-F(1)                 |      6 |
| 4 |   1,2 | 2^4-F(2)-F(1)            |     12 |
| 5 |     1 | 2^5 - F(1)               |     30 |
| 6 | 1,2,3 | 2^6 - F(1) - F(2) - F(3) |     54 |

简单的 python 实现

nperiodics = [0, 2] # for n = 1(0,1) and n = 2(01, 10)

def divisors(n):
    for d in xrange(1, n / 2 + 1):
        if n %  d == 0:
            yield d

def periodic(n, counts):
    return 2**n - sum(counts[d] for d in divisors(n))


for i in xrange(2, 10):
    nperiodics.append(periodic(i, nperiodics))

print nperiodics

输出：[0, 2, 2, 6, 12, 30, 54, 126, 240, 504]

Answer 6

我用下面的算法解决了这个答案，这是非常基本的。希望我解决的问题是您所问问题的答案。

如果字符串中有 8 个二进制字符，并且我想获得它的所有可能的排列，那么以下算法将正确地给出这些值。在其中，我特意跳过了排列“00000000”，因为它对我来说没有价值:)。

下面的代码是用 Ruby 编写的：

size = 8
max_binary_value = (2 ** size) - 1  # In this case, 255

permutations = 1.upto(max_binary_value).map do |num|
  # This will zero-padd the string, ie: "%08d" % "10" # => "00000010",
  #   while to_s(2) will convert it to Base 2 in String form:
  "%0#{size}d" % num.to_s(2)
end