algorithm - 多级计数器迭代

Question

我坚持按如下方式创建算法。我知道这应该不会太难，但我就是无法理解它，也找不到对这种模式的正确描述。

基本上我需要一个多级计数器，当数据库中存在组合时，通过从右侧递增来尝试下一个值。

1 1 1 - Start position. Does this exist in database? YES -> Extract this and go to next
1 1 2 - Does this exist in database? YES -> Extract this and go to next
1 1 3 - Does this exist in database? YES -> Extract this and go to next
1 1 4 - Does this exist in database? NO -> Reset level 1, move to level 2
1 2 1 - Does this exist in database? YES -> Extract this and go to next
1 2 2 - Does this exist in database? NO -> Reset level 2 and 1, move to level 3
2 1 1 - Does this exist in database? YES -> Extract this and go to next
2 1 2 - Does this exist in database? YES -> Extract this and go to next
2 1 3 - Does this exist in database? NO -> Reset level 1 and increment level 2
2 2 1 - Does this exist in database? YES -> Extract this and go to next
2 2 2 - Does this exist in database? YES -> Extract this and go to next
2 2 3 - Does this exist in database? YES -> Extract this and go to next
2 3 1 - Does this exist in database? NO -> Extract this and go to next
3 1 1 - Does this exist in database? NO -> Extract this and go to next
3 2 1 - Does this exist in database? NO -> End, as all increments tried

不过，可能不止三个级别。

在实践中，每个值(如 1、2 等)实际上是一个 $value1、$value2 等，其中包含与 XML 文档匹配的运行时字符串。因此，这不仅仅是提取数据库中已存在的每个组合的情况。

Answer 1

假设数据库 key 的长度是预先知道的，下面是一种实现方式。我使用的是 TypeScript，但可以用您喜欢的语言编写类似的代码。

首先，为方便起见，我声明了一些类型定义。

export type Digits = number[];
export type DbRecord = number;

然后我初始化用作模拟数据源的 fakeDb 对象。我编写的函数将对这个对象起作用。此对象的键代表数据库记录的键(string 类型)。这些值是简单的数字(有意顺序)；它们代表数据库记录本身。

export const fakeDb: { [ dbRecordKey: string ]: DbRecord } = {
  '111': 1,
  '112': 2,
  '113': 3,
  '211': 4,
  '212': 5,
  '221': 6,
  '311': 7,
};

接下来，您可以看到有趣的部分，该函数使用“数字”的counterDigits 数组根据记录的存在与否递增。

请不要认为这是生产就绪代码! A) 有不必要的console.log() 调用存在用于演示目的。 B) 最好不要从数据库中读取大量 DbRecords 到内存中，而是使用 yield/return 或某种缓冲区或流。

export function readDbRecordsViaCounter(): DbRecord[] {
  const foundDbRecords: DbRecord[] = [];

  const counterDigits: Digits = [1, 1, 1];
  let currentDigitIndex = counterDigits.length - 1;

  do {
    console.log(`-------`);

    if (recordExistsFor(counterDigits)) {
      foundDbRecords.push(extract(counterDigits));

      currentDigitIndex = counterDigits.length - 1;
      counterDigits[currentDigitIndex] += 1;
    } else {
      currentDigitIndex--;
      for (let priorDigitIndex = currentDigitIndex + 1; priorDigitIndex < counterDigits.length; priorDigitIndex++) {
        counterDigits[priorDigitIndex] = 1;
      }
      if (currentDigitIndex < 0) {
        console.log(`------- (no more records expected -- ran out of counter's range)`);
        return foundDbRecords;
      }
      counterDigits[currentDigitIndex] += 1;
    }

    console.log(`next key to try: ${ getKey(counterDigits) }`);

  } while (true);
}

剩下的是一些“辅助”函数，用于从数字数组构造字符串键并访问假数据库。

export function recordExistsFor(digits: Digits): boolean {
  const keyToSearch = getKey(digits);
  const result = Object.getOwnPropertyNames(fakeDb).some(key => key === keyToSearch);
  console.log(`key=${ keyToSearch } => recordExists=${ result }`);
  return result;
}

export function extract(digits: Digits): DbRecord {
  const keyToSearch = getKey(digits);
  const result = fakeDb[keyToSearch];
  console.log(`key=${ keyToSearch } => extractedValue=${ result }`);
  return result;
}

export function getKey(digits: Digits): string {
  return digits.join('');
}

---

现在，如果你像这样运行这个函数:

const dbRecords = readDbRecordsViaCounter();
console.log(`\n\nDb Record List: ${ dbRecords }`);

您应该会看到以下输出，告诉您有关迭代步骤的信息；并在最后报告最终结果。

-------
key=111 => recordExists=true
key=111 => extractedValue=1
next key to try: 112
-------
key=112 => recordExists=true
key=112 => extractedValue=2
next key to try: 113
-------
key=113 => recordExists=true
key=113 => extractedValue=3
next key to try: 114
-------
key=114 => recordExists=false
next key to try: 121
-------
key=121 => recordExists=false
next key to try: 211
-------
key=211 => recordExists=true
key=211 => extractedValue=4
next key to try: 212
-------
key=212 => recordExists=true
key=212 => extractedValue=5
next key to try: 213
-------
key=213 => recordExists=false
next key to try: 221
-------
key=221 => recordExists=true
key=221 => extractedValue=6
next key to try: 222
-------
key=222 => recordExists=false
next key to try: 231
-------
key=231 => recordExists=false
next key to try: 311
-------
key=311 => recordExists=true
key=311 => extractedValue=7
next key to try: 312
-------
key=312 => recordExists=false
next key to try: 321
-------
key=321 => recordExists=false
next key to try: 411
-------
key=411 => recordExists=false
------- (no more records expected -- ran out of counter's range)


Db Record List: 1,2,3,4,5,6,7

---

强烈推荐阅读代码。如果您想让我描述方法或任何具体细节，请告诉我。希望对您有所帮助。