如何计算完全不匹配且至多 d 不匹配的字符串的邻居数？

Question

给定一个字符串和一组四个字母（A、B、C、D），用于生成长度为 n 的字符串。我需要一个通用的数学公式来计算任何长度为 n 且至多 d 不匹配的字符串的邻居数，以及具有恰好 d 个不匹配。

例如：给定一个字符串=”AAA”和d=3

我们有 9 个字符串正好 d=1

    BAA  
    CAA  
    DAA  
    ABA  
    ACA  
    ADA  
    AAB   
    AAC   
    AAD

我们有 27 个字符串正好 d=2

BBA   BCA   BDA   
BAB   BAC   BAD
CBA   CCA   CDA   
CAB   CAC   CAD
DBA   DCA   DDA   
DAB   DAC   DAD
ABB   ABC   ABD
ACB   ACC   ACD
ADB   ADC   ADD

我们有 27 个字符串正好 d=3

BBB   CBB   DBB   
BCB   CCB   DCB
BDB   CDB   DDB   
BBC   CBC   DBC
BCC   CCC   DCC    
BDC   CDC   DDC   
BBD   CBD   DBD    
BCD   CCD   DCD   
BDD   CDD   DDD

最多的字符串数d=3是9+27+27=63个字符串

Answer 1

让我们考虑一个大小为 n 的字符串。
我们想知道这个字符串有多少个'neighbors'，距离d。我们首先要注意的是，根据您对 'distance' 的定义，这意味着我们必须在字符串的 n 中选择 d 个字符并修改它们。所以有 n choose d 个可能的字符组合可以修改。
这些中的每一个都可以以 3 不同的方式修改（因为字母表的大小是 4.
所以最终，我们有：

n choose d 可能的字符组合将被修改
d个字符会被修改，每个字符都可以3不同的方式修改。

所以公式最终是(s - 1) ^ d * (n choose d)，其中s是字母表的大小（这里是4）。我让您验证它是否适合您提供的第一个示例。

Answer 2

如果你想尝试一下：

#include <iostream>
#include <string>
using namespace std;

int n = 3; int d = 2;
string s = "AAA";
    
int counter(string curr, int index, int currd){
    if(currd == 0 || index == n){
        cout<<curr<<s.substr(index, n - index)<<endl;
        return 1;
    }
    int ans = 0;
    for(char c = 'A'; c < 'E'; c++){
        if(c != s[index]){
            ans += counter(curr + c, index + 1, currd - 1);
        }
        else{
            ans += counter(curr + c, index + 1, currd);
        }
    }
    return ans;
}

int main(){
    cout<<"answer = "<<counter("", 0, d) - 1;
}

如何计算完全不匹配且至多 d 不匹配的字符串的邻居数？

How to calculate the number of neighbors of a string with exact and at most d mismatches?

string

algorithm

combinations

enumeration

data-structures