Поиск числа перестановок для трехбуквенной строки с ABC и 123

Question

Я знаю из класса Algebra, что с ABC и 123 мы можем сделать 216 разных перестановок для трехбуквенной строки, верно? (6 x 6 x 6) Я хотел бы создать консольную программу на C++, которая отображает любую возможную перестановку для приведенного выше примера. Дело в том, как бы я даже начал пытаться их вычислить. Возможно:

AAA BAA CAA 1BA 2BA 3СА 1AB 2BC 3СА

и т.д.

Это действительно трудно спросить, но что я должен сделать, чтобы гарантировать, что Я включаю каждую перестановку? Я знаю, что есть 216, но я не знаю, как на самом деле пройти через все из них.

Любые предложения были бы весьма благодарны !!!

Answer 1

Если вам нужны строки с фиксированным номером, вы можете использовать вложенные петли N (три в вашем случае).

string parts = "ABC123"; 
for (int i = 0 ; i != parts.size() ; i++) 
    for (int j = 0 ; j != parts.size() ; j++) 
     for (int k = 0 ; k != parts.size() ; k++) 
      cout << parts[i] << parts[j] << parts[k] << endl; 

Если N не фиксирован, вам потребуется более общерекурсивное решение.

Answer 2

С тремя вложенными циклами (по одному на позицию символа), итерирующими по каждому из 6 допустимых символов, сложно не, чтобы увидеть, что каждая возможная комбинация имеет соответствующий набор индексов цикла и что каждый набор индексов левого цикла имеет соответствующую трехбуквенную строку. Я понимаю, что соответствие 1-1 между индексами цикла и строками является тем, что вы ищете.

Answer 3

Это очень просто сделать, используя рекурсию. Если у вас есть массив из всех шести элементов, вот вам java-код. Я уверен, что вы можете легко перевести его на C++.

void getAllCombinations(List<String> output, char[] chrs, String prefix, int length) { 
    if (prefix.length() == length) { 
     output.add(prefix); 
    } else { 
     for (int i = 0;i < chrs.length;i++) { 
      getAllCombinations(output, chrs, prefix + chrs[i], length); 
     } 
    } 
    return; 
} 

Это не идеально, но это должно дать вам общую идею. Запустите его с параметрами: пустой список, массив доступных символов, пустую строку и длину требуемых строк.