string - 返回一个在两个给定字符串之间排序的新字符串

Question

给定两个字符串 a 和 b，其中 a 按字典顺序 < b，我想返回一个字符串 c，使得 a < c < b。用例是在按此类键排序的数据库中插入一个节点。您可以根据需要指定 a、b 和 c 的格式，只要可以在插入时生成初始值和新值。

有没有实用的算法呢？

Answer 1

最小化字符串长度

如果您想将字符串长度保持在最短，您可以创建一个按字典顺序位于左右字符串中间的字符串，以便有空间插入其他字符串，并且仅在绝对必要时创建更长的字符串。

我将假设一个字母 [a-z] 和一个字典顺序，其中一个空格位于“a”之前，例如“ab”出现在“abc”之前。

基础案例

您首先从字符串的开头复制字符，直到遇到第一个差异，这可能是两个不同的字符，也可能是左侧字符串的结尾:

abcde ~ abchi  ->  abc  +  d ~ h  
abc   ~ abchi  ->  abc  +  _ ~ h  

然后通过在左侧字符(或字母表的开头)和右侧字符之间附加字母表中的字符来创建新字符串:

abcde ~ abchi  ->  abc  +  d ~ h  ->  abcf  
abc   ~ abchi  ->  abc  +  _ ~ h  ->  abcd  

连续字符

如果两个不同的字符在字典上是连续的，首先复制左边的字符，然后在左边字符串中的下一个字符和字母表末尾之间附加字符:

abhs ~ abit  ->  ab  +  h ~ i  ->  abh  +  s ~ _  ->  abhw
abh  ~ abit  ->  ab  +  h ~ i  ->  abh  +  _ ~ _  ->  abhn

如果左侧字符串中的下一个字符是一个或多个 z，则复制它们并将字符附加在第一个非 z 字符和字母表末尾之间的中间:

abhz   ~ abit  ->  ab  +  h ~ i  ->  abh  +  z ~ _  ->  abhz  +  _ ~ _  ->  abhzn  
abhzs  ~ abit  ->  ab  +  h ~ i  ->  abh  +  z ~ _  ->  abhz  +  s ~ _  ->  abhzw  
abhzz  ~ abit  ->  ab  +  h ~ i  ->  abh  +  z ~ _  ->  ... ->  abhzz  +  _ ~ _  ->  abhzzn

右字符是 a 或 b

你永远不应该通过在左边的字符串后面附加一个 'a' 来创建一个字符串，因为这会创建两个按字典顺序连续的字符串，在这两个字符串之间不能再添加更多的字符串。解决方案是始终在字母表开头和右侧字符串的下一个字符之间附加一个附加字符:

abc  ~ abcah   ->  abc  +  _ ~ a  ->  abca  +  _ ~ h  ->  abcad  
abc  ~ abcab   ->  abc  +  _ ~ a  ->  abca  +  _ ~ b  ->  abcaa  +  _ ~ _  ->  abcaan  
abc  ~ abcaah  ->  abc  +  _ ~ a  ->  abca  +  _ ~ a  ->  abcaa  +  _ ~ h  ->  abcaad  
abc  ~ abcb    ->  abc  +  _ ~ b  ->  abca  +  _ ~ _  ->  abcan

代码示例

下面是演示该方法的代码片段。因为 JavaScript 有点繁琐，但实际上并不复杂。要生成第一个字符串，请使用两个空字符串调用该函数；这将生成字符串“n”。要在最左边的字符串之前或最右边的字符串之后插入一个字符串，请使用该字符串和一个空字符串调用该函数。

function midString(prev, next) {
    var p, n, pos, str;
    for (pos = 0; p == n; pos++) {               // find leftmost non-matching character
        p = pos < prev.length ? prev.charCodeAt(pos) : 96;
        n = pos < next.length ? next.charCodeAt(pos) : 123;
    }
    str = prev.slice(0, pos - 1);                // copy identical part of string
    if (p == 96) {                               // prev string equals beginning of next
        while (n == 97) {                        // next character is 'a'
            n = pos < next.length ? next.charCodeAt(pos++) : 123;  // get char from next
            str += 'a';                          // insert an 'a' to match the 'a'
        }
        if (n == 98) {                           // next character is 'b'
            str += 'a';                          // insert an 'a' to match the 'b'
            n = 123;                             // set to end of alphabet
        }
    }
    else if (p + 1 == n) {                       // found consecutive characters
        str += String.fromCharCode(p);           // insert character from prev
        n = 123;                                 // set to end of alphabet
        while ((p = pos < prev.length ? prev.charCodeAt(pos++) : 96) == 122) {  // p='z'
            str += 'z';                          // insert 'z' to match 'z'
        }
    }
    return str + String.fromCharCode(Math.ceil((p + n) / 2)); // append middle character
}

var strings = ["", ""];
while (strings.length < 100) {
    var rnd = Math.floor(Math.random() * (strings.length - 1));
    strings.splice(rnd + 1, 0, midString(strings[rnd], strings[rnd + 1]));
    document.write(strings + "<br>");
}

下面是对 C 的直接翻译。使用以空结尾的空字符串调用该函数以生成第一个字符串，或者在最左边的字符串之前或最右边的字符串之后插入。字符串缓冲区 buf应该足够大以容纳一个额外的字符。

int midstring(const char *prev, const char *next, char *buf) {
    char p = 0, n = 0;
    int len = 0;
    while (p == n) {                                           // copy identical part
        p = prev[len] ? prev[len] : 'a' - 1;
        n = next[len] ? next[len] : 'z' + 1;
        if (p == n) buf[len++] = p;
    }
    if (p == 'a' - 1) {                                        // end of left string
        while (n == 'a') {                                     // handle a's
            buf[len++] = 'a';
            n = next[len] ? next[len] : 'z' + 1;
        }
        if (n == 'b') {                                        // handle b
            buf[len++] = 'a';
            n = 'z' + 1;
        }
    }
    else if (p + 1 == n) {                                     // consecutive characters
        n = 'z' + 1;
        buf[len++] = p;
        while ((p = prev[len] ? prev[len] : 'a' - 1) == 'z') { // handle z's
            buf[len++] = 'z';
        }
    }
    buf[len++] = n - (n - p) / 2;                              // append middle character
    buf[len] = '\0';
    return len;
}

平均字符串长度

最好的情况是元素以随机顺序插入。在实践中，当以伪随机顺序生成 65,536 个字符串时，平均字符串长度约为 4.74 个字符(理论最小值，在移动到更长的字符串之前使用每个组合，将是 3.71)。

最坏的情况是按顺序插入元素时，总是生成一个新的最右边或最左边的字符串；这将导致重复出现的模式:

n, u, x, z, zn, zu, zx, zz, zzn, zzu, zzx, zzz, zzzn, zzzu, zzzx, zzzz...  
n, g, d, b, an, ag, ad, ab, aan, aag, aad, aab, aaan, aaag, aaad, aaab...  

每四个字符串后添加一个额外的字符。

如果您有一个想要为其生成键的现有有序列表，请使用如下算法生成按字典顺序排列的等距键，然后在插入新元素时使用上述算法生成新键。

该代码检查需要多少个字符，最低有效位需要多少个不同的字符，然后在字母表中的两个选择之间切换以获得正确数量的键。例如。两个字符的键可以有 676 个不同的值，所以如果你要求 1600 个键，即每个两个字符组合有 1.37 个额外的键，所以在每个两个字符的键之后附加一个 ('n') 或两个 ('j' ,'r') 字符被附加，即: aan ab abj abr ac acn ad adn ae aej aer af afn ... (跳过最初的'aa')。

function seqString(num) {
    var chars = Math.floor(Math.log(num) / Math.log(26)) + 1;
    var prev = Math.pow(26, chars - 1);
    var ratio = chars > 1 ? (num + 1 - prev) / prev : num;
    var part = Math.floor(ratio);
    var alpha = [partialAlphabet(part), partialAlphabet(part + 1)];
    var leap_step = ratio % 1, leap_total = 0.5;
    var first = true;
    var strings = [];
    generateStrings(chars - 1, "");
    return strings;

    function generateStrings(full, str) {
        if (full) {
            for (var i = 0; i < 26; i++) {
                generateStrings(full - 1, str + String.fromCharCode(97 + i));
            }
        }
        else {
            if (!first) strings.push(stripTrailingAs(str));
            else first = false;
            var leap = Math.floor(leap_total += leap_step);
            leap_total %= 1;
            for (var i = 0; i < part + leap; i++) {
                strings.push(str + alpha[leap][i]);
            }
        }
    }
    function stripTrailingAs(str) {
        var last = str.length - 1;
        while (str.charAt(last) == 'a') --last;
        return str.slice(0, last + 1);
    }
    function partialAlphabet(num) {
        var magic = [0, 4096, 65792, 528416, 1081872, 2167048, 2376776, 4756004,
                     4794660, 5411476, 9775442, 11097386, 11184810, 22369621];
        var bits = num < 13 ? magic[num] : 33554431 - magic[25 - num];
        var chars = [];
        for (var i = 1; i < 26; i++, bits >>= 1) {
            if (bits & 1) chars.push(String.fromCharCode(97 + i));
        }
        return chars;
    }

}
document.write(seqString(1600).join(' '));