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

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

最小化字符串长度

如果要使字符串长度最小，则可以创建一个按字典顺序位于左右字符串中间的字符串，这样就有空间插入其他字符串，并且在绝对必要时仅创建更长的字符串。

我将假定一个字母[az]和一个字典顺序，其中在’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 ~ _  ->  abhwabh  ~ 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的直接转换。用空的以null终止的字符串调用该函数以生成第一个字符串，或在最左边或最右边的字符串之后插入。字符串缓冲区

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] = '';    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’）字符，即：（

aanab 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(' '));