如何实现吉他（n弦乐器）指定和弦的所有指型生成算法？

需求说明 #

我需要实现一个函数/算法，输入和弦音符列表（如C大调的C E G），以及6弦吉他（或n弦乐器）的特定tuning（每根琴弦每个品对应的音符），生成指板上所有符合要求的和弦指型。指型的弦数最少为3（满足和弦定义），最多为乐器的总弦数（如吉他的6弦），且需按弦数分组返回，示例格式如下：

[
  {
    chordSize: 3,
    chords: [
      [
        // 0索引琴弦，1索引品丝（空弦为品丝0）
        { string: 1, fret: 3, note: "C" },
        { string: 2, fret: 2, note: "E" },
        { string: 3, fret: 0, note: "G" },
      ],
      [
        { string: 2, fret: 2, note: "E" },
        { string: 3, fret: 0, note: "G" },
        { string: 4, fret: 1, note: "C" },
      ],
      [
        { string: 3, fret: 0, note: "G" },
        { string: 4, fret: 1, note: "C" },
        { string: 5, fret: 0, note: "E" },
      ],
      // ...
    ],
  },
  {
    chordSize: 4,
    chords: [
      [
        { string: 1, fret: 3, note: "C" },
        { string: 2, fret: 2, note: "E" },
        { string: 3, fret: 0, note: "G" },
        { string: 4, fret: 1, note: "C" },
      ],
      // ...
    ],
  },
  {
    chordSize: 5,
    chords: [
      [
        { string: 1, fret: 3, note: "C" },
        { string: 2, fret: 2, note: "E" },
        { string: 3, fret: 0, note: "G" },
        { string: 4, fret: 1, note: "C" },
        { string: 5, fret: 0, note: "E" },
      ],
    ],
    // ...
  },
  // ...
]

对应的吉他和弦指型如下：
{:width="180"}

现有代码与问题 #

我初步编写了部分代码，但在递归逻辑部分遇到困难：

function getPossibleStringedInstrumentChords({
  numStrings = 6, notes, tuning, maxFretDistance = 6
}) {
  // tuning是二维数组，每一项对应一根弦的所有品丝音符
  // tuning = [ [ 'E', 'F', 'F#', 'G', ... ], ['A', 'A#', 'B', 'C', ...] ]
  
  // notes是目标和弦音符数组，如['C', 'E', 'G' ]

  let i = 3 // 和弦最少需要3个音符
  while (i <= numStrings) {
    let stringIndex = 0
    let fretIndex = 0
    let string = tuning[stringIndex]

    while (fretIndex < string.length) {
      const note = string[fretIndex++]
      if (notes.includes(note)) {
        // 这里不知道怎么加入集合...
      } else {
        // 感觉需要递归处理多分支，脑子直接卡壳了！
      }
    }
    i++
  }
}

可用的音符集合：

const POSSIBLE_NOTES = ['A', 'A#', 'B', 'C', 'C#', 'D', 'D#', 'E', 'F', 'F#', 'G', 'G#']

吉他标准调弦示例：

const GUITAR_TUNING = [
  ["E", "F", "F#", "G", "G#", "A", "A#", "B", "C", "C#", "D", "D#"],
  ["A", "A#", "B", "C", "C#", "D", "D#", "E", "F", "F#", "G", "G#"],
  ["D", "D#", "E", "F", "F#", "G", "G#", "A", "A#", "B", "C", "C#"],
  ["G", "G#", "A", "A#", "B", "C", "C#", "D", "D#", "E", "F", "F#"],
  ["B", "C", "C#", "D", "D#", "E", "F", "F#", "G", "G#", "A", "A#"],
  ["E", "F", "F#", "G", "G#", "A", "A#", "B", "C", "C#", "D", "D#"],
]

补充说明 #

• 3弦指型可使用任意3根琴弦，无需连续；
• 同一组琴弦上，同一和弦可存在多个不同八度的指型。

解决方案 #

实现思路 #

1. 预处理有效品丝：为每根琴弦筛选出所有属于目标和弦音符的品丝位置，记录对应的string（弦索引）、fret（品丝数，0表示空弦）、note（音符）。
2. 生成琴弦组合：对每个目标弦数k（从3到numStrings），生成所有k根不同琴弦的组合（比如6弦吉他的3弦组合有C(6,3)=20种）。
3. 回溯生成合法指型：对每个琴弦组合，遍历每根弦的有效品丝，组合出满足以下条件的指型：
   • 所有品丝的间距不超过maxFretDistance；
   • 指型覆盖所有目标和弦音符（比如C和弦必须包含C、E、G至少各一个）。
4. 分组去重：将生成的指型按弦数分组，返回要求的格式。

完整代码实现 #

// 生成数组中k个元素的所有组合
function generateCombinations(arr, k) {
  const result = [];
  const backtrack = (start, path) => {
    if (path.length === k) {
      result.push([...path]);
      return;
    }
    for (let i = start; i < arr.length; i++) {
      path.push(arr[i]);
      backtrack(i + 1, path);
      path.pop();
    }
  };
  backtrack(0, []);
  return result;
}

function getPossibleStringedInstrumentChords({
  numStrings = 6, notes, tuning, maxFretDistance = 6
}) {
  // 1. 预处理每根弦的有效品丝
  const stringValidFrets = [];
  for (let stringIdx = 0; stringIdx < numStrings; stringIdx++) {
    const frets = tuning[stringIdx];
    const valid = [];
    for (let fretIdx = 0; fretIdx < frets.length; fretIdx++) {
      const note = frets[fretIdx];
      if (notes.includes(note)) {
        valid.push({
          string: stringIdx,
          fret: fretIdx,
          note: note
        });
      }
    }
    stringValidFrets.push(valid);
  }

  const result = [];

  // 2. 遍历每个和弦大小k（3到numStrings）
  for (let k = 3; k <= numStrings; k++) {
    const chordGroup = { chordSize: k, chords: [] };
    // 生成所有k根弦的组合
    const stringCombinations = generateCombinations(Array.from({ length: numStrings }, (_, i) => i), k);

    // 处理每个琴弦组合
    for (const stringCombo of stringCombinations) {
      // 获取每个选中琴弦的有效品丝列表
      const validFretLists = stringCombo.map(stringIdx => stringValidFrets[stringIdx]);
      // 回溯生成所有可能的指型组合
      const currentChords = [];
      const backtrack = (index, currentNotes, currentFrets) => {
        if (index === k) {
          // 检查是否覆盖所有目标音符
          const coveredNotes = new Set(currentNotes);
          if (notes.every(n => coveredNotes.has(n))) {
            // 检查品距是否符合要求
            const fretValues = currentFrets.map(f => f.fret);
            const minFret = Math.min(...fretValues);
            const maxFret = Math.max(...fretValues);
            if (maxFret - minFret <= maxFretDistance) {
              currentChords.push([...currentFrets]);
            }
          }
          return;
        }
        // 遍历当前琴弦的所有有效品丝
        for (const fretOption of validFretLists[index]) {
          currentNotes.push(fretOption.note);
          currentFrets.push(fretOption);
          backtrack(index + 1, currentNotes, currentFrets);
          currentNotes.pop();
          currentFrets.pop();
        }
      };
      backtrack(0, [], []);
      chordGroup.chords.push(...currentChords);
    }

    // 去重：相同指型（按弦、品丝完全一致）只保留一个
    const uniqueChords = Array.from(new Set(chordGroup.chords.map(c => JSON.stringify(c.sort((a,b) => a.string - b.string))))).map(str => JSON.parse(str));
    chordGroup.chords = uniqueChords;

    if (chordGroup.chords.length > 0) {
      result.push(chordGroup);
    }
  }

  return result;
}

// 使用示例
const testChords = getPossibleStringedInstrumentChords({
  notes: ['C', 'E', 'G'],
  tuning: GUITAR_TUNING,
  maxFretDistance: 6
});
console.log(testChords);

代码说明 #

• generateCombinations函数用于生成不重复的琴弦组合，确保选中的琴弦不会重复；
• 预处理阶段提前筛选有效品丝，减少后续不必要的计算；
• 回溯过程中同时检查音符覆盖和品距限制，确保生成的指型符合和弦定义和演奏合理性；
• 最后对每组指型进行去重，避免重复的指型（比如不同顺序存储的同指型）。

内容的提问来源于stack exchange，提问作者Lance Pollard