Я пытаюсь найти эффективный алгоритм в C, который предоставляет мне все комбинации данной кодировки.
Алгоритм не должен быть рекурсивным. Наконец, число цифр должно быть гибким. Например:
char set[] = "a1"; -> a1 aa 1a 11 Я нашел решение Perl, но использует substr() . Я думаю, что это было не так быстро.
Для большинства алгоритмов в C я нашел только перестановки …
Статья на немецком форуме C ++ утверждает, что решения C ++ – STL быстрее, чем «исходные» рекурсивные алгоритмы.
Если заданный размер был фиксированным N, это было бы просто – вы могли бы просто иметь N for циклов, каждый из которых вложен в предыдущий. Поскольку вы не можете этого сделать, и вы не можете использовать рекурсию, вам нужно вычислить общее количество итераций (похоже, это N ^ M), используйте один единственный цикл, а затем используйте / и% для вычисления того, что индекс массива каждого персонажа. Вам также лучше использовать длинные, потому что N ^ M становится очень быстрым.
В Википедии есть код C для n-арного кода Grey . Он должен быть преобразован в вашу проблему, используя цифры в качестве смещений в вашем массиве ввода. Вам нужно будет сделать динамическое распределение для обработки произвольной длины ввода. Связанный подход состоит в том, чтобы делать вложенные циклы, где у вас есть массив счетчиков циклов, пока ваш вход, и другой счетчик, для которого из тех, которые вы в настоящее время увеличиваете. Например, распечатывая все шестизначные номера базы-шесть, необходимо изменить для динамического распределения, но показывает принцип:
int i; int length = 5; int max = 6; int counters[length]; for (i=0; i=0; i--) printf("%d", counters[i]); printf("\n"); for(i=0; i= length) break; }
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)
Ну, я бы подсчитал возможные комбинации, пропустил числа и конвертировал.
Например: чтобы сгенерировать все комбинации из 3-х символов из 10 символов {‘0’, ‘1’, …, ‘9’}, я бы сделал цикл от 0 до 999 и вывел «000» в «999».
Точно так же (kinda), чтобы сгенерировать все комбинации 3-го размера из 5 символов {‘a’, ‘b’, …, ‘e’}, я бы сделал цикл от 0 до 5 * 5 * 5-1 и вывод номер цикла в базе 5, но с предоставленными символами.
Напишите функцию, которая преобразует целое число в шестнадцатеричное число строки, а затем преобразует этот алгоритм в базу 36 (az плюс 0-9). Используйте один для цикла для подсчета от 1 до (цифра счетчика времени базы) и каждый раз вызывайте свою функцию.