Все возможные комбинации в C

Question

Я пытаюсь найти эффективный алгоритм в C, который предоставляет мне все комбинации данной кодировки.

Алгоритм не должен быть рекурсивным. Наконец количество цифр должно быть гибким. Например:

char set[] = "a1";
->
a1
aa
1a
11

Я нашел только решение Perl, но оно использует substr(). Я думаю, что это не было так быстро с точки зрения производительности.

Я обнаружил, что для большинства алгоритмов на С были только перестановки ...

В статье на немецком форуме C ++ утверждается, что решения C ++ - STL работают быстрее, чем «сырые» рекурсивные алгоритмы.

Answer 1

В Википедии есть код C для n-арного кода Грея .Он должен быть преобразован в вашу проблему, используя цифры в качестве смещений во входном массиве.Вам нужно будет сделать некоторое динамическое распределение для обработки произвольной длины вашего ввода.Связанный подход заключается в создании вложенных циклов, где у вас есть массив счетчиков циклов, равный вашему входу, и другой счетчик, для которого из тех, которые вы в данный момент увеличиваете.Например, для печати всех шестизначных шестизначных чисел требуется модификация для динамического распределения, но показан принцип:

int i;
int length = 5;
int max = 6;
int counters[length];
for (i=0; i<length; i++)
    counters[i] = 0;
for(;;) {
    for (i=length-1; i>=0; i--)
        printf("%d", counters[i]);
    printf("\n");
    for(i=0; i<length; i++) {
        counters[i]++;
        if (counters[i] < max)
            break;
        else
            counters[i] = 0;
    }
    if (i >= length)
        break;
}

Answer 2

Python очень близок к псевдокоду.

Вы можете прочитать исходный код Python в itertools.permutations и просто скопировать в C.

Вот пример того, как это работает:

#!/usr/bin/env python
import itertools

s='a1'

print set(itertools.permutations(s*len(s), len(s)))

Выход:

set([('1', '1'), ('a', '1'), ('a', 'a'), ('1', 'a')])

Вот еще более простой способ:

>>> s='a1'
>>> ['{}{}'.format(x,y) for x in s for y in s]
['aa', 'a1', '1a', '11']


>>> s='abc'
>>> ['{}{}{}'.format(x,y,z) for x in s for y in s for z in s]
['aaa', 'aab', 'aac', 'aba', 'abb', 'abc', 'aca', 'acb', 
 'acc', 'baa', 'bab', 'bac', 'bba', 'bbb', 'bbc', 'bca', 
 'bcb', 'bcc', 'caa', 'cab', 'cac', 'cba', 'cbb', 'cbc', 
 'cca', 'ccb', 'ccc']

Чтобы развернуть понимание списка, используйте NESTED LOOPS, например так:

>>> for x in s:
...    for y in s:
...       for z in s:
...          print '{}{}{}'.format(x,y,z)

Answer 3

Если бы установленный размер был фиксированным N, это было бы просто - вы могли бы просто иметь N for циклов, каждый из которых был бы вложен в предыдущий.Так как вы не можете сделать это и не можете использовать рекурсию, вы должны рассчитать общее необходимое количество итераций (кажется, что это N ^ M), использовать один цикл, а затем использовать / и% для вычисления индекса массивакаждого персонажа должно быть.Тебе лучше использовать longs, потому что N ^ M быстро растет.

Answer 4

Напишите функцию, которая преобразует целое число в шестнадцатеричное число в строке, а затем преобразует этот алгоритм в базовое число 36 (az плюс 0-9).Используйте один для цикла для подсчета от 1 до (число раз основывается на числе) и вызывайте вашу функцию каждый раз.

• 1 становится 1
• 10 становится
• 35становится z
• 36 становится 10
• 46 становится 1a

Answer 5

Ну, я бы нумерировал возможные комбинации, перебирал числа и преобразовывал.

Например: чтобы сгенерировать все комбинации размера 3 из 10 символов {'0', '1', ..., '9'}, я зациклился бы от 0 до 999 и вывел «000» в «999» .

Таким же образом (вроде), чтобы сгенерировать все комбинации размера 3 из 5 символов {'a', 'b', ..., 'e'}, я бы сделал цикл от 0 до 5 * 5 * 5- 1 и выведите номер цикла в базе 5, но с предоставленными символами.