Описание задачи
Дан шаблон ключа keyTpl. Можно менять местами зубчики в любом порядке (перестановка букв).
Количество каждой буквы сохраняется.
Правило генерации
- Производный ключ — любая перестановка букв keyTpl
- Количество каждой буквы должно сохраняться
- Учитывать повторяющиеся буквы!
Для "AAB" перестановки: AAB, ABA, BAA — всего 3 уникальных (не 6).
Формат входных данных
keyTpl: шаблон_ключа
locks: массив замков
minLocks: минимум замков
Пример
Условие
keyTpl: "ABC"
locks: ["A--", "-B-", "--C"]
minLocks: 2
Анализ
Все перестановки ABC: ABC, ACB, BAC, BCA, CAB, CBA Замок "A--": открывают ABC, ACB (начинаются с A) Замок "-B-": открывают ABC, CBA (B в середине) Замок "--C": открывают ABC, BAC (заканчиваются на C) Ключи, открывающие ≥2 замков: ABC: открывает все 3 ✓ ACB: открывает 1 ✗ BAC: открывает 1 ✗ BCA: открывает 0 ✗ CAB: открывает 0 ✗ CBA: открывает 1 ✗
Результат
countKeys → 1
findKeys → ["ABC"]
Ключевые моменты
- Формула уникальных перестановок: n! / (n₁! × n₂! × ... × nₖ!)
- Используйте
std::next_permutationили backtracking - Сортировка строки перед перебором для уникальности