Генерация всех чисел длины M (1

Question

спасибо, что нашли время, чтобы прочитать это. Я работаю над большим проектом, которому нужна функция, которая генерирует все числа на основе правил, описанных в заголовке. Если входы M = 3 и N = 5 Выходы должны быть: 111,112,113,114,115,121 .... 555 Для входов M = 4 и N = 2 Выходы должны быть: 1111,1112,1121 ... 2222

I ' Я пытался сделать функцию, которая делает это в течение достаточно долгого времени, но мне это не удалось. Поэтому я прошу о помощи. Мне нужно написать это в C, но если вы знаете, как исправить это в C ++ или C#, я, вероятно, смогу перевести это в C.

Я не У меня есть какой-нибудь код, который нужно показать, потому что до сих пор я в основном пробовал его перебором, но, похоже, он не работает. Заранее спасибо за помощь!

Answer 1

Если я пойму вопрос, я сделаю это с помощью регулярных выражений. Все это написано с учетом C.

Сначала создайте регулярное выражение со всеми разрешенными цифрами. Posix предоставляет библиотеку регулярных выражений (https://www.educative.io/edpresso/how-to-write-regular-expressions-in-c кажется хорошим вступлением), поэтому вам нужно только составить строку, которая будет проанализирована regcomp(), итерируя по числам от 1 до N. An подходящее регулярное выражение будет для N = 20 ^(1|2|3|4|5|6|7|8|9|10|11|12|13|14|15|16|17|18|19|20)+$. Это будет соответствовать строкам, состоящим полностью из любого из этих символов. (Так как 0 должно совпадать только после 1 или 2, в этом случае перечисление опций проще, чем попытка сократить регулярное выражение).

Затем выполните итерацию по числам, начинающимся с 10 ^ M и заканчивающимся при достижении 10^(M+1). Запишите каждое число в виде строки и посмотрите, соответствует ли оно регулярному выражению - если это так, у вас есть один из ваших результатов.

Answer 2

Проблема может быть сведена к запуску M-di git, числа base-N с самым низким значением для начальной итерации, и увеличению его для последующих итераций.

M-di * Число 1018 * может быть представлено в виде массива (с индексом от 0 до M-1) с одним элементом на di git. Один конец массива будет содержать самый низкий порядок («самый правый») di git, а другой конец массива будет содержать самый высокий порядок («самый левый») di git. На самом деле не имеет значения, какой конец выбран для удержания самого высокого порядка di git, поэтому давайте выберем элемент 0 для удержания самого высокого порядка di git. Для общности давайте используем значения di git от 0 до N-1. (На самом деле не имеет значения, что исходная задача имеет цифры, идущие от 1 до N, поскольку легко отобразить значения di git из одной схемы в другую.)

Мы можем определить функцию для установки число M-di git до его наименьшего значения:

void num_init(unsigned int *digits, unsigned int m)
{
    while (m--)
    {
        digits[m] = 0;
    }
}

Мы можем определить другую функцию, чтобы увеличить число M-di git и указать, было ли число обернуто к его наименьшему значению :

int num_inc(unsigned int *digits, unsigned int n, unsigned int m)
{
    while (m--)
    {
        if (digits[m] < n - 1)
        {
            digits[m]++;
            return 0;
        }
        digits[m] = 0; // carry
    }
    return 1;
}

Пример использования:

// Print all M-digit numbers with digits from 1 to N.
void list_nums(unsigned int m, unsigned int n)
{
    unsigned int digits[m];
    int wrapped = 0;

    num_init(digits, m);
    while (!wrapped)
    {
        unsigned int i;

        // output an m-digit number
        for (i = 0; i < m; i++)
        {
            // Note: Add 1 to each digit so digits run from 1 to n instead of 0 to n-1.
            printf("%u", digits[i] + 1);
        }
        // get next number
        wrapped = num_inc(digits, n, m);
        if (!wrapped)
        {
            printf(",");
        }
    }
    printf("\n");
}

Примечание. Вывод list_nums(m, n) будет странным, если n больше 9.