Распечатать комбинацию строки

Question

В C как мне распечатать все комбинации строки?

Например: если строка «ABC», то возможной комбинацией является A, B, C, AB, AC, BC, ABC.

Мне нужно распечатать все возможные комбинации "ABC" в консоли.

Answer 1

Вот подсказка. Думайте о комбинациях как о битовых кодировках. Э.Г.

пусто = 000 = 0

C = 001 = 1

B = 010 = 2

BC = 011 = 3

A = 100 = 4

AC = 101 = 5

AB = 110 = 6

ABC = 111 = 7

Answer 2

То, что вы ищете, это алгоритм возврата.

Поскольку это домашнее задание, это то место, с которого вы должны начать. Общая идея заключается в том, чтобы закодировать буквы как целые числа и сгенерировать все возможные комбинации длины 1, используя 3 буквы, затем все возможные комбинации длины 2, а затем все комбинации длины 3.

Answer 3

Используйте рекурсию, идея такова:

Для каждого рекурсивного вызова ввод строки уменьшается на 1 символ, результирующая строка сохраняется в строковом массиве tmp. Например:

вызов 1: abc

вызов 2: ab, последний символ: c

вызов 3: a, последний символ: b

затем возьмите последний символ и вставьте его в список строк в tmp во всех возможных положениях, например:

tmp содержит: a, последний символ: b

вставьте b в позиции 0 и 1, получив "ab" и "ba"

результат - возврат к списку вывода, и процесс продолжается.

псевдокод примерно такой:

get_perm (input):
    string[] tmp, out
    if input lengh == 1     //base case
        add input to tmp
        return tmp;

    tmp = get_permu (input[0 to input.length -1])
    char last_char = input[input.length - 1]
    //loop thru the string in tmp
    for string str in tmp:
        string tmp_str = str    //create a tmp copy
        int len = tmp_str.lengh //get the len
        //insert last_char to all possible position
        for j=0 to len:
            new_str = (add last_char to tmp_str in j position)
            out.add(new_str)

    return out