Предположим, что алфавит "ab c". Тогда:
b, c, cb ...
- это лексикографически отсортированный список, который позволяет вставлять элементы в любое место:
ab, b, bb, c, cab, cb, cbb ...
И в результате остается список, который позволяет вставлять элементы куда угодно:
aab, ab, a c, b, bab , bb, b c, c, caab, cab, ca c, cb, cbab, cbb, cbbb ...
Хитрость заключается в том, чтобы избежать "a" как последний символ элемента, так что вы всегда можете поставить элементы позади других.
Сделайте это с 64 символами ASCII вместо 3.
Я думал об этом для довольно много месяцев. Это мой прогресс в его реализации. У него все еще есть некоторый fl aws, и это немного беспорядок, но я предполагаю, что уберу это и загружу это в npm, когда я найду больше времени.
// Originally written in TypeScript, then removed the types for SO.
const alphabet = 'abc';
function getHigherAsciiChar(char) {
const index = alphabet.indexOf(char);
if (index === alphabet.length - 1) {
return ''; // sorry, there's no higher character
}
const nextIndex = Math.ceil((index + alphabet.length - 1) / 2);
return alphabet.charAt(nextIndex);
}
function getCharBetween(minChar, maxChar) {
if (minChar > maxChar) {
throw new Error('minChar > maxChar, ' + minChar + ' > ' + maxChar);
}
const minIndex = alphabet.indexOf(minChar);
const maxIndex = alphabet.indexOf(maxChar);
const nextIndex = Math.floor((minIndex + maxIndex) / 2);
if (nextIndex === minIndex) {
return ''; // there is no character between these two
}
return alphabet.charAt(nextIndex);
}
function getPaddedString(finalLength, string) {
let result = string;
while (result.length < finalLength) {
result += alphabet.charAt(0);
}
return result;
}
function getOrderString(bounds) {
const console = { log: () => {} }; // uncomment this to log debug stuff
if (!bounds.previous && !bounds.next) {
return getHigherAsciiChar(alphabet[0]);
}
const previousString = bounds.previous || '';
if (!bounds.next) {
const firstPreviousChars = previousString.substr(0, previousString.length - 1);
const lastPreviousChar = previousString.charAt(previousString.length - 1);
return firstPreviousChars + (
getHigherAsciiChar(lastPreviousChar) || (
lastPreviousChar + getHigherAsciiChar(alphabet.charAt(0))
)
);
}
const nextString = bounds.next;
console.log(`Searching between '${previousString}' and '${nextString}'...`);
const bigStringLength = Math.max(previousString.length, nextString.length);
const previous = getPaddedString(bigStringLength, previousString);
const next = getPaddedString(bigStringLength, nextString);
console.log(previous, next);
let result = '';
let i;
for (i = 0; i < bigStringLength; i++) {
const previousChar = previous.charAt(i);
const nextChar = next.charAt(i);
// keep adding common characters
if (previousChar === nextChar) {
result += previousChar;
console.log(result, 'common character');
continue;
}
// when different characters are reached, try to add a character between these two
const charBetween = getCharBetween(previousChar, nextChar);
if (charBetween) {
result += charBetween;
console.log(result, 'character in-between. RETURNING');
// and you're done
return result;
}
// if there was no character between these two (their distance was exactly 1),
// repeat the low character, forget about the upper bound and just try to get bigger than lower bound
result += previousChar;
console.log(result, 'the lower character so we can forget about high bound');
i++;
break;
}
for (; previousString >= result; i++) {
const previousChar = previous.charAt(i);
const higherChar = getHigherAsciiChar(previousChar);
if (higherChar) {
// you found a digit that makes your result greater than the lower bound. You're done.
result += higherChar;
console.log(result, 'a higher character. RETURING');
return result;
}
// the digits are still very close, can't find a digit in-between (yet)
result += previousChar;
console.log(result, 'moving on to next digit');
}
// so you end up depleting all the character slots from the lower bound. Meh, just add any character.
result += getHigherAsciiChar(alphabet.charAt(0));
console.log(result, 'meh, just add any character. RETURNING');
return result;
}
function interleaveTest(order) {
const newOrder = [];
newOrder.push(getOrderString({ next: order[0] }));
for (let i = 0; i < order.length - 1; i++) {
newOrder.push(order[i]);
newOrder.push(getOrderString({ previous: order[i], next: order[i + 1] }));
}
newOrder.push(order[order.length - 1]);
newOrder.push(getOrderString({ previous: order[order.length - 1] }));
return newOrder;
}
let order = ['c'];
console.log('\n' + order.join(', ') + '\n');
order = interleaveTest(order);
console.log('\n' + order.join(', ') + '\n');
order = interleaveTest(order);
console.log('\n' + order.join(', ') + '\n');
order = interleaveTest(order);
console.log('\n' + order.join(', ') + '\n');
let atEnd = ['b'];
for (let i = 0; i < 10; i++) {
atEnd.push(getOrderString({ previous: atEnd[atEnd.length - 1] }));
}
console.log('\nat end: ' + atEnd.join(', ') + '\n');