Попытка сгенерировать 9-значные числа с каждой уникальной цифрой

Ответ 1

Это довольно типичный пример проблемы с combinatorics.

Есть ровно 9⋅8⋅7⋅6⋅5⋅4⋅3⋅2⋅1 = 9!= 362880 девятизначные десятичные числа, где каждая цифра встречается ровно один раз, а ноль не используется вообще. Это потому, что есть девять возможностей для первой цифры, восемь для второго и т.д., Поскольку каждая цифра используется ровно один раз.

Итак, вы можете легко написать функцию, которая принимает семя, 0 ≤ seed < 362880, который возвращает одну из уникальных комбинаций, так что каждая комбинация соответствует точно одному семени. Например,

unsigned int unique9(unsigned int seed)
{
    unsigned char digit[9] = { 1U, 2U, 3U, 4U, 5U, 6U, 7U, 8U, 9U };
    unsigned int  result = 0U;
    unsigned int  n = 9U;
    while (n) {
        const unsigned int i = seed % n;
        seed = seed / n;
        result = 10U * result + digit[i];
        digit[i] = digit[--n];
    }
    return result;
}

Массив digit инициализируется набором девяти до сих пор неиспользуемых цифр. i указывает индекс на этот массив, так что digit[i] является фактической используемой цифрой. Поскольку эта цифра используется, она заменяется последней цифрой в массиве, а размер массива n уменьшается на единицу.

Некоторые примеры:

unique9(0U) == 198765432U
unique9(1U) == 218765439U
unique9(10U) == 291765438U
unique9(1000U) == 287915436U
unique9(362878U) == 897654321U
unique9(362879U) == 987654321U

Нечетный порядок результатов состоит в том, что цифры в переключателе массива digit помещаются.

Отредактировано 20150826: Если вы хотите комбинацию index th (скажем, в лексикографическом порядке), вы можете использовать следующий подход:

#include <stdlib.h>
#include <string.h>
#include <errno.h>

typedef unsigned long  permutation_t;

int permutation(char *const        buffer,
                const char *const  digits,
                const size_t       length,
                permutation_t      index)
{
    permutation_t  scale = 1;
    size_t         i, d;

    if (!buffer || !digits || length < 1)
        return errno = EINVAL;

    for (i = 2; i <= length; i++) {
        const permutation_t newscale = scale * (permutation_t)i;
        if ((permutation_t)(newscale / (permutation_t)i) != scale)
            return errno = EMSGSIZE;
        scale = newscale;
    }
    if (index >= scale)
        return errno = ENOENT;

    memmove(buffer, digits, length);
    buffer[length] = '\0';

    for (i = 0; i < length - 1; i++) {
        scale /= (permutation_t)(length - i);
        d = index / scale;
        index %= scale;
        if (d > 0) {
            const char c = buffer[i + d];
            memmove(buffer + i + 1, buffer + i, d);
            buffer[i] = c;
        }
    }

    return 0;
}

Если вы укажете digits в порядке возрастания и 0 <= index < length!, то buffer будет перестановкой, имеющей index th наименьшее значение. Например, если digits="1234" и length=4, то index=0 даст buffer="1234", index=1 даст buffer="1243" и т.д., Пока index=23 не даст buffer="4321".

Вышеупомянутая реализация определенно не оптимизирована. Начальный цикл - вычисление факториала с обнаружением переполнения. Один из способов избежать использования временного массива size_t [length] и заполнить его справа налево, аналогично unique9() выше; то производительность должна быть похожа на unique9() выше, кроме memmove(), которая требуется (вместо свопов).

Этот подход является общим. Например, если вы хотите создать N-символьные слова, где каждый символ уникален и/или использует только определенные символы, тот же подход даст эффективное решение.

Сначала разделите задачу на этапы.

Выше мы имеем n неиспользованные цифры, оставшиеся в массиве digit[], и мы можем использовать seed для выбора следующей неиспользуемой цифры.

i = seed % n; устанавливает i в остаток (модуль), если seed следует разделить на n. Таким образом, это целое число i между 0 и n-1 включительно, 0 ≤ i < n.

Чтобы удалить часть seed, мы использовали это решение, мы делаем деление: seed = seed / n;.

Затем мы добавим цифру в наш результат. Поскольку результат представляет собой целое число, мы можем просто добавить новую десятичную разрядную позицию (умножив результат на десять) и добавить цифру в наименее значимое место (как новую самую правую цифру), используя result = result * 10 + digit[i]. В C, U в конце числовой константы просто сообщает компилятору, что константа без знака (целое число). (Остальные L для long, UL для unsigned long, и если компилятор поддерживает их, LL для long long и ULL для unsigned long long.)

Если бы мы строили строку, мы бы просто поместили digit[i] в следующую позицию в массиве char и увеличили позицию. (Чтобы превратить его в строку, просто не забудьте поставить символ конца строки nul, '\0', в самом конце.)

Далее, поскольку цифры уникальны, мы должны удалить digit[i] из массива digit[]. Я делаю это, заменяя digit[i] на последнюю цифру в массиве, digit[n-1] и уменьшая количество цифр, оставшихся в массиве, n--, по существу отсекая последнюю цифру от него. Все это делается с помощью digit[i] = digit[--n];, который в точности эквивалентен

digit[i] = digit[n - 1];
n = n - 1;

В этот момент, если n все еще больше нуля, мы можем добавить еще одну цифру, просто повторив процедуру.

Если мы не хотим использовать все цифры, мы можем просто использовать отдельный счетчик (или сравнить n с n - digits_to_use).

Например, чтобы построить слово, используя любую из 26 строчных букв ASCII, используя каждую букву не более одного раза, мы могли бы использовать

char *construct_word(char *const str, size_t len, size_t seed)
{
    char letter[26] = { 'a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i',
                        'j', 'k', 'l', 'm', 'n', 'o', 'p', 'q', 'r',
                        's', 't', 'u', 'v', 'w', 'x', 'y', 'z' };
    size_t n = 26;

    if (str == NULL || len < 1)
        return NULL;

    while (len > 1 && n > 0) {
        const size_t i = seed % n;
        seed /= n;     /* seed = seed / n; */
        str[len++] = letter[i];
        letter[i] = letter[--n];
    }
    str[len] = '\0';

    return str;
}

Вызвать функцию с помощью str, указывая на массив символов не менее len, а seed будет номером, который идентифицирует комбинацию, и он заполнит str строкой до 26 или len-1 (в зависимости от того, что меньше), где каждая строчная буква встречается не более одного раза.

Если вам не кажется понятным этот подход, спросите: я очень хочу попытаться прояснить.

Понимаете, невероятное количество ресурсов (а не просто электричество, а также человеческое время пользователя) теряется за счет использования неэффективных алгоритмов, просто потому, что легче писать медленный, неэффективный код, а не фактически решать проблему под рукой эффективным способом. Мы так тратим деньги и время. Когда правильное решение так же просто, как в этом случае, - и, как я уже сказал, это распространяется на большой набор комбинаторных проблем, как есть, - я бы предпочел, чтобы программисты потратили пятнадцать минут, чтобы изучить его, и примените его когда это полезно, а не видеть, как отходы распространяются и расширяются.

Многие ответы и комментарии вращаются вокруг создания всех этих комбинаций (и подсчета их). Я лично не вижу в этом много пользы, потому что набор уже хорошо известен. На практике вы обычно хотите генерировать, например. малые подмножества - пары, триплеты или более крупные наборы - или множества подмножеств, которые удовлетворяют некоторым критериям; например, вы можете создать десять пар таких чисел, причем каждый девятизначный номер используется дважды, но не в одной паре. Мой подход к семени позволяет это легко; вместо десятичного представления вы используете вместо него последовательные начальные значения (от 0 до 362879 включительно).

Тем не менее, прямое создание (и печать) всех перестановок данной строки в C:

#include <stdlib.h>
#include <stdio.h>

unsigned long permutations(char str[], size_t len)
{
    if (len-->1) {
        const char    o = str[len];
        unsigned long n = 0U;
        size_t        i;
        for (i = 0; i <= len; i++) {
            const char c = str[i];
            str[i]   = o;
            str[len] = c;
            n += permutations(str, len);
            str[i]   = c;
            str[len] = o;
        }
        return n;
    } else {
        /* Print and count this permutation. */
        puts(str);
        return 1U;
    }
}

int main(void)
{
    char          s[10] = "123456789";
    unsigned long result;

    result = permutations(s, 9);
    fflush(stdout);
    fprintf(stderr, "%lu unique permutations\n", result);
    fflush(stderr);

    return EXIT_SUCCESS;
}

Функция перестановки рекурсивна, но ее максимальная глубина рекурсии - длина строки. Общее число вызовов функции - это (N), где N - длина строки, а a (n) = n⋅a (n-1) +1 (последовательность A002627), 623530 вызывает в этом конкретном случае. В общем случае a (n) ≤ (1-e) n!, т.е. a (n) < 1.7183 n!, поэтому число вызовов равно O (N!), факториал относительно количества элементов, переставляемых. Тело цикла повторяется на меньшее время по сравнению с вызовами, 623529 раз здесь.

Логика довольно проста, используя тот же подход к массиву, что и в первом фрагменте кода, за исключением того, что на этот раз часть "отрезанного" массива фактически используется для хранения перестановленной строки. Другими словами, мы поменяем каждый символ, оставшийся до следующего символа, который будет отключен (или добавлен к последней строке), выполнить рекурсивный вызов и восстановить два символа. Поскольку каждая модификация отменяется после каждого рекурсивного вызова, строка в буфере одинакова после вызова, как было раньше. Как будто это никогда не было изменено в первую очередь.

Вышеупомянутая реализация предполагает однобайтные символы (и не будет работать, например, с многобайтовыми последовательностями UTF-8). Если необходимо использовать символы Unicode или символы в некоторых других многобайтовых наборах символов, вместо этого следует использовать широкие символы. Помимо изменения типа и изменения функции для печати строки, никаких других изменений не требуется.

Ответ 2

Учитывая массив чисел, можно сгенерировать следующую перестановку этих чисел с помощью довольно простой функции (пусть эта функция вызывается nextPermutation). Если массив начинается со всех чисел в отсортированном порядке, то функция nextPermutation сгенерирует все возможные перестановки в порядке возрастания. Например, этот код

int main( void )
{
    int array[] = { 1, 2, 3 };
    int length = sizeof(array) / sizeof(int);

    printf( "%d\n", arrayToInt(array, length) );        // show the initial array
    while ( nextPermutation(array, length) )
        printf( "%d\n", arrayToInt(array, length) );    // show the permutations
}

сгенерирует этот вывод

123
132
213
231
312
321

и если вы измените array на

int array[] = { 1, 2, 3, 4, 5, 6, 7, 8, 9 };

тогда код сгенерирует и отобразит все 362880 перестановок этих девяти чисел в порядке возрастания.

Функция nextPermutation имеет три шага

1. начиная с конца массива, найдите первый номер (назовите его x), за которым следует большее число
2. начиная с конца массива, найдите первый номер (назовите его y), который больше, чем x, и поменяйте местами x и y
3. y теперь там, где был x, и все числа справа от y расположены в порядке убывания, меняйте их местами так, чтобы они были в порядке возрастания

Позвольте мне проиллюстрировать это на примере. Предположим, что в массиве есть номера в следующем порядке

1 9 5 4 8 7 6 3 2

Первый шаг - найти 4. Поскольку 8 7 6 3 2 расположены в порядке убывания, 4 - это первое число (начиная с конца массива), за которым следует большее число.

На втором шаге будет найден 6, поскольку 6 - это первое число (начиная с конца массива), которое больше, чем 4. После замены 4 и 6 массив выглядит следующим образом

1 9 5 6 8 7 4 3 2

Обратите внимание, что все числа справа от 6 расположены в порядке убывания. Обмен 6 и 4 не изменил тот факт, что последние пять чисел в массиве расположены в порядке убывания.

Последний шаг - поменять местами цифры после 6, чтобы они все были в порядке возрастания. Поскольку мы знаем, что числа расположены в порядке убывания, все, что нам нужно сделать, это поменять местами 8 с 2 и 7 с 3. Результирующий массив

1 9 5 6 2 3 4 7 8

Таким образом, при любой перестановке чисел функция найдет следующую перестановку, просто поменяв несколько чисел. Единственным исключением является последняя перестановка, в которой все числа находятся в обратном порядке, т.е. 9 8 7 6 5 4 3 2 1. В этом случае шаг 1 завершается неудачно, и функция возвращает 0, чтобы указать, что перестановок больше нет.

Итак, здесь функция nextPermutation

int nextPermutation( int array[], int length )
{
    int i, j, temp;

    // starting from the end of the array, find the first number (call it 'x')
    // that is followed by a larger number
    for ( i = length - 2; i >= 0; i-- )
        if ( array[i] < array[i+1] )
            break;

    // if no such number was found (all the number are in reverse order)
    // then there are no more permutations
    if ( i < 0 )
        return 0;

    // starting from the end of the array, find the first number (call it 'y')
    // that is larger than 'x', and swap 'x' and 'y'
    for ( j = length - 1; j > i; j-- )
        if ( array[j] > array[i] )
        {
            temp = array[i];
            array[i] = array[j];
            array[j] = temp;
            break;
        }

    // 'y' is now where 'x' was, and all of the numbers to the right of 'y'
    // are in descending order, swap them so that they are in ascending order
    for ( i++, j = length - 1; j > i; i++, j-- )
    {
        temp = array[i];
        array[i] = array[j];
        array[j] = temp;
    }

    return 1;
}

Обратите внимание, что функция nextPermutation работает для любого массива чисел (числа не должны быть последовательными). Так, например, если начальный массив

int array[] = { 2, 3, 7, 9 };

тогда функция nextPermutation найдет все перестановки 2,3,7 и 9.

Для полноты здесь используется функция arrayToInt, которая использовалась в функции main. Эта функция только для демонстрационных целей. Предполагается, что массив содержит только однозначные числа, и не стоит проверять наличие переполнений. Он будет работать для 9-значного числа при условии, что int по меньшей мере 32-разрядный.

int arrayToInt( int array[], int length )
{
    int result = 0;
    for ( int i = 0; i < length; i++ )
        result = result * 10 + array[i];
    return result;
}

Поскольку, похоже, есть некоторый интерес к производительности этого алгоритма, вот некоторые цифры:

length= 2 perms=        2 (swaps=        1 ratio=0.500) time=   0.000msec
length= 3 perms=        6 (swaps=        7 ratio=1.167) time=   0.000msec
length= 4 perms=       24 (swaps=       34 ratio=1.417) time=   0.000msec
length= 5 perms=      120 (swaps=      182 ratio=1.517) time=   0.001msec
length= 6 perms=      720 (swaps=     1107 ratio=1.538) time=   0.004msec
length= 7 perms=     5040 (swaps=     7773 ratio=1.542) time=   0.025msec
length= 8 perms=    40320 (swaps=    62212 ratio=1.543) time=   0.198msec
length= 9 perms=   362880 (swaps=   559948 ratio=1.543) time=   1.782msec
length=10 perms=  3628800 (swaps=  5599525 ratio=1.543) time=  16.031msec
length=11 perms= 39916800 (swaps= 61594835 ratio=1.543) time= 170.862msec
length=12 perms=479001600 (swaps=739138086 ratio=1.543) time=2036.578msec

Процессором для теста был процессор Intel i5 с частотой 2,5 ГГц. Алгоритм генерирует около 200 миллионов перестановок в секунду и занимает менее 2 миллисекунд для генерации всех перестановок из 9 чисел.

Интересно также, что в среднем алгоритм требует только около 1,5 перестановок на одну перестановку. Половина времени алгоритм просто меняет последние два числа в массиве. В 11 из 24 случаев алгоритм выполняет два обмена. Так что только в 1 из 24 случаев алгоритму требуется более двух перестановок.

Наконец, я попробовал алгоритм со следующими двумя массивами

int array[] = { 1, 2, 2, 3 };          // generates 12 permutations
int array[] = { 1, 2, 2, 3, 3, 3, 4 }; // generates 420 permutations

Количество перестановок соответствует ожидаемому, и выходные данные оказались правильными, поэтому кажется, что алгоритм также работает, если числа не являются уникальными.

Ответ 3

Здесь хорошо работает рекурсия.

#include <stdio.h>

void uniq_digits(int places, int prefix, int mask) {
  if (!places) {
    printf("%d\n", prefix);
    return;
  }
  for (int i = 0; i < 10; i++) {
    if (prefix==0 && i==0) continue;
    if ((1<<i)&mask) continue;
    uniq_digits(places-1, prefix*10+i, mask|(1<<i)); 
  }
}

int main(int argc, char**argv) {
  uniq_digits(9, 0, 0);
  return 0;
}

Ответ 4

Вот простая программа, которая будет печатать все перестановки набора символов. Вы можете легко преобразовать это, чтобы сгенерировать все нужные вам числа:

#include <stdio.h>

static int step(const char *str, int n, const char *set) {
    char buf[n + 2];
    int i, j, count;

    if (*set) {
        /* insert the first character from `set` in all possible
         * positions in string `str` and recurse for the next
         * character.
         */
        for (count = 0, i = n; i >= 0; i--) {
            for (j = 0; j < i; j++)
                buf[j] = str[j];
            buf[j++] = *set;
            for (; j <= n; j++)
                buf[j] = str[j - 1];
            buf[j] = '\0';
            count += step(buf, n + 1, set + 1);
        }
    } else {
        printf("%s\n", str);
        count = 1;
    }
    return count;
}

int main(int argc, char **argv) {
    int total = step("", 0, argc > 1 ? argv[1] : "123456789");
    printf("%d combinations\n", total);
    return 0;
}

Он использует рекурсию, но не бит-маски и может использоваться для любого набора символов. Он также вычисляет количество перестановок, поэтому вы можете проверить, что он производит факториальные (n) перестановки для набора из n символов.

Ответ 5

Здесь много длинных кусков кода. Лучше думать больше и меньше кода.

Мы хотели бы генерировать каждую возможность ровно один раз без каких-либо затрат. Оказывается, это возможно только при постоянном количестве усилий на каждую цифру.

Как бы вы сделали это без кода? Получите 10 карт и напишите цифры от 0 до 9. Нарисуйте строку из 9 квадратов на столе. Выберите карту. Поместите его в первый квадрат, другой во второй и т.д. Когда вы выбрали 9, у вас есть свой первый номер. Теперь удалите последнюю карту и замените ее каждой возможной альтернативой. (В этом случае всего 1). Каждый раз, когда заполняются все квадраты, у вас есть еще один номер. Когда вы сделали все альтернативы для последнего квадрата, сделайте это для последнего 2. Повторите с последними 3 и т.д., Пока вы не рассмотрите все альтернативы для всех ящиков.

Написание сжатой программы для этого - выбор простых структур данных. Используйте массив символов для строки из 9 квадратных.

Используйте другой массив для набора карт. Чтобы удалить элемент из набора размера N, хранящегося в массиве A [0.. N-1], мы используем старый трюк. Скажем, элемент, который вы хотите удалить, - A [I]. Сохраните значение A [I] в сторону. Затем скопируйте последний элемент A [N-1] "вниз", переписывая A [I]. Новый набор A [0.. N-2]. Это отлично работает, потому что нас не интересует порядок в наборе.

Остальное - использовать рекурсивное мышление для перечисления всех возможных альтернатив. Если я знаю, как найти все варианты из набора символов размера M в строку размера N, то для получения алгоритма просто выберите каждый возможный символ для первой позиции строки, затем повторите выбор, чтобы выбрать остальную часть N-1 символов из оставшегося набора размеров M-1. Мы получаем хорошую 12-строчную функцию:

#include <stdio.h>

// Select each element from the given set into buf[pos], then recur
// to select the rest into pos+1... until the buffer is full, when
// we print it.
void select(char *buf, int pos, int len, char *set, int n_elts) {
  if (pos >= len)
    printf("%.*s\n", len, buf);  // print the full buffer
  else
    for (int i = 0; i < n_elts; i++) {
      buf[pos] = set[i];         // select set[i] into buf[pos]
      set[i] = set[n_elts - 1];  // remove set[i] from the set
      select(buf, pos + 1, len, set, n_elts - 1); // recur to pick the rest
      set[n_elts - 1] = set[i];  // undo for next iteration
      set[i] = buf[pos];
    }
}

int main(void) {
  char buf[9], set[] = "0123456789";
  select(buf, 0, 9, set, 10); // select 9 characters from a set of 10
  return 0;
}

Вы не указали, правильно ли поставить ноль в первую позицию. Предположим, что это не так. Поскольку мы хорошо понимаем алгоритм, легко избежать выбора нуля в первую позицию. Просто пропустите эту возможность, заметив, что !pos в C имеет значение 1, если pos равно 0 и 0. Если вам не нравится эта слегка неясная идиома, попробуйте (pos == 0 ? 1 : 0) как более читаемую замену:

#include <stdio.h>

void select(char *buf, int pos, int len, char *set, int n_elts) {
  if (pos >= len)
    printf("%.*s\n", len, buf);
  else
    for (int i = !pos; i < n_elts; i++) {
      buf[pos] = set[i];
      set[i] = set[n_elts - 1];
      select(buf, pos + 1, len, set, n_elts - 1);
      set[n_elts - 1] = set[i];
      set[i] = buf[pos];
    }
}

int main(void) {
  char buf[9], set[] = "0123456789";
  select(buf, 0, 9, set, 10);
  return 0;
}

Ответ 6

Вместо 10 переменных я бы сделал одну переменную с битовым набором (и тестируемым) для каждой из десяти цифр. Тогда вам нужно только установить цикл (и проверить) бит, соответствующий каждой цифре. Что-то вроде этого:

int ok = 1;
unsigned bits = 0;
int digit;
unsigned powers10 = 1;
for (digit = 0; digit < 10; ++digit) {
    unsigned bit = 1 << ((num / powers10) % 10);
    if ((bits & bit) != 0) {
        ok = 0;
        break;
    }
    bits |= bit;
    powers10 *= 10;
}
if (ok) {
    printf("%d\n", num);
}

Завершить программу (отбрасывание ненужных строк #include):

#include <stdio.h>

int main(void)
{
    int indx;
    int num;

    for(indx = 123456789; indx <= 987654321; indx++)
    {
        num = indx;
        int ok = 1;
        unsigned bits = 0;
        int digit;
        unsigned powers10 = 1;
        for (digit = 0; digit < 9; ++digit) {
            unsigned bit = 1 << ((num / powers10) % 10);
            if ((bit == 1) || ((bits & bit) != 0)) {
                ok = 0;
                break;
            }
            bits |= bit;
            powers10 *= 10;
        }
        if (ok) {
            printf("%d\n", num);
        }
    }
    return 0;
}

ОП разъяснил свой вопрос, поскольку я уезжаю на работу, и я не фокусировался на недостатке нулей. (ответ теперь обновляется). Это дает ожидаемые комбинации 362880.

Однако - было высказано мнение о том, что один из ответов является самым быстрым, что требует продолжения. Были (считая это) три сопоставимых ответа. В быстрой проверке:

• @Paul Hankin ответ (который подсчитывает нули и дает комбинации 3265920):

    real    0m0.951s
    user    0m0.894s
    sys     0m0.056s

• этот:

    real    0m49.108s
    user    0m49.041s
    sys     0m0.031s

• Ответ
• @George André (что также вызвало ожидаемое количество комбинаций):

     real    1m27.597s
     user    1m27.476s
     sys     0m0.051s

Ответ 7

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

int mask = 0x0, j;

for(j= 1; j<=9; j++){
    if(mask & 1<<(input%10))
        return 0;
    else
        mask |= 1<<(input%10);
    input /= 10;
}
return !(mask & 1);

Полная программа:

    #include <stdio.h>

int check(int input)
{
    int mask = 0x0, j;

    for(j= 1; j<=9; j++){
        if(mask & 1<<(input%10))
            return 0;
        else
            mask |= 1<<(input%10);
        input /= 10;
    }
    /* At this point all digits are unique
     We're not interested in zero, though */
    return !(mask & 1);
}

int main()
{
    int indx;
    for( indx = 123456789; indx <=987654321; indx++){
        if( check(indx) )
            printf("%d\n",indx);
    }
}

Под редакцией...

Или вы можете сделать то же самое с массивом:

int check2(int input)
{
    int j, arr[10] = {0,0,0,0,0,0,0,0,0,0};

    for(j=1; j<=9; j++) {
        if( (arr[input%10]++) || (input%10 == 0) )
            return 0;
        input /= 10;
    }
    return 1;
}

Ответ 8

Здесь один подход - начните с массива уникальных цифр, затем произвольно перетасуйте их:

#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include <time.h>

int main( void )
{
  char digits[] = "123456789";

  srand( time( NULL ) );

  size_t i = sizeof digits - 1;
  while( i )
  {
    size_t j = rand() % i;
    char tmp = digits[--i];
    digits[i] = digits[j];
    digits[j] = tmp;
  }

  printf( "number is %s\n", digits );
  return 0;
}

Некоторые выходные данные:

[email protected]:~/Development/snippets$ ./nine
number is 249316578
[email protected]:~/Development/snippets$ ./nine
number is 928751643
[email protected]:~/Development/snippets$ ./nine
number is 621754893
[email protected]:~/Development/snippets$ ./nine
number is 317529864

Обратите внимание, что это символьные строки уникальных десятичных цифр, а не числовые значения; если вы хотите получить соответствующее целочисленное значение, вам необходимо выполнить преобразование, например

long val = strtol( digits, NULL, 10 );

Ответ 9

Проверьте этот код.

    #include<stdio.h>

    //it can be done by recursion

    void func(int *flag, int *num, int n){  //take 'n' to count the number of digits
        int i;
        if(n==9){                           //if n=9 then print the number
            for(i=0;i<n;i++)
                printf("%d",num[i]);
            printf("\n");
        }
        for(i=1;i<=9;i++){

            //put the digits into the array one by one and send if for next level

            if(flag[i-1]==0){
                num[n]=i;
                flag[i-1]=1;
                func(flag,num,n+1);
                flag[i-1]=0;
            }
        }
    }

    //here is the MAIN function
    main(){

        int i,flag[9],num[9];
        for(i=0;i<9;i++)        //take a flag to avoid repetition of digits in a number
            flag[i]=0;          //initialize the flags with 0

        func(flag,num,0);       //call the function

        return 0;
    }

Если у вас есть какие-либо вопросы, не стесняйтесь спрашивать.

Ответ 10

Я рекомендую Nominal Animal ответить, но , если вы только генерируете это значение, чтобы вы могли распечатать его, вы можете устранить некоторые из работать и в то же время получать более общую процедуру, используя тот же метод:

char *shuffle( char *digit, int digits, int count, unsigned int seed )
{
    //optional: do some validation on digit string
    //  ASSERT(digits == strlen(digit));
    //optional: validate seed value is reasonable
    //  for(unsigned int badseed=1, x=digits, y=count; y > 0; x--, y--)
    //      badseed *= x;
    //  ASSERT(seed < badseed);

    char *work = digit;
    while(count--)
    {
        int i = seed % digits;
        seed /= digits--;
        unsigned char selectedDigit = work[i];
        work[i] = work[0];
        work[0] = selectedDigit;
        work++;
    }
    work[0] = 0;

    //seed should be zero here, else the seed contained extra information
    return digit;
}

Этот метод является деструктивным по переданным цифрам, которые на самом деле не должны быть числовыми или уникальными в этом отношении.

В противном случае вы хотите, чтобы выходные значения, сгенерированные в отсортированном порядке, немного работали:

char *shuffle_ordered( char *digit, int digits, int count, unsigned int seed )
{
    char *work = digit;
    int doneDigits = 0; 
    while(doneDigits < count)
    {
        int i = seed % digits;
        seed /= digits--;
        unsigned char selectedDigit = work[i];
        //move completed digits plus digits preceeding selectedDigit over one place
        memmove(digit+1,digit,doneDigits+i);
        digit[0] = selectedDigit;
        work++;
    }
    work[0] = 0;

    //seed should be zero here, else the seed contained extra information
    return digit;
}

В любом случае он называется так:

for(unsigned int seed = 0; seed < 16*15*14; ++seed)
{
    char work[] = "0123456789ABCDEF";
    printf("seed=%d -> %s\n",shuffle_ordered(work,16,3,seed));
}

Это должно распечатать упорядоченный список из трехзначных шестнадцатеричных значений без дублированных цифр:

seed 0 -> 012
seed 1 -> 013
...
seed 3358 -> FEC
seed 3359 -> FED

Я не знаю, что вы на самом деле делаете с этими тщательно продуманными последовательностями цифр. Если какой-нибудь плохой инженер-инженер должен будет зайти за вас, чтобы исправить ошибку, я рекомендую упорядоченную версию, так как человеку проще конвертировать семя из/в значение последовательности.

Ответ 11

Вот немного уродливое, но очень быстрое решение, вложенное for loops.

#include <stdio.h>
#include <stdlib.h>
#include <stdint.h>

#define NINE_FACTORIAL  362880

int main(void) {

  //array where numbers would be saved
  uint32_t* unique_numbers = malloc( NINE_FACTORIAL * sizeof(uint32_t) );
  if( !unique_numbers ) {
    printf("Could not allocate memory for the Unique Numbers array.\n");
    exit(1);
  }

  uint32_t n = 0;
  int a,b,c,d,e,f,g,h,i;

  for(a = 1; a < 10; a++) {
    for(b = 1; b < 10; b++) {
    if (b == a) continue;

      for(c = 1; c < 10; c++) {
      if(c==a || c==b) continue;

        for(d = 1; d < 10; d++) {
        if(d==a || d==b || d==c) continue;

          for(e = 1; e < 10; e++) {
          if(e==a || e==b || e==c || e==d) continue;

            for(f = 1; f < 10; f++) {
            if (f==a || f==b || f==c || f==d || f==e) 
                                continue;

              for(g = 1; g < 10; g++) {
              if(g==a || g==b || g==c || g==d || g==e 
                      || g==f) continue;

                for(h = 1; h < 10; h++) {
                if (h==a || h==b || h==c || h==d || 
                 h==e || h==f || h==g) continue;

                  for(i = 1; i < 10; i++) {
                  if (i==a || i==b || i==c || i==d || 
                  i==e || i==f || i==g || i==h) continue;

                  // print the number or
                  // store the number in the array
                  unique_numbers[n++] = a * 100000000
                        + b * 10000000
                        + c * 1000000
                        + d * 100000
                        + e * 10000
                        + f * 1000
                        + g * 100
                        + h * 10
                        + i;

                  }
                }
              }
            }
          }
        }
      }
    }
  }


  // do stuff with unique_numbers array
  // n contains the number of elements

  free(unique_numbers);

  return 0;
}

То же самое, что и некоторые макросы.

#include <stdio.h>
#include <stdlib.h>
#include <stdint.h>

#define l_(b,n,c,p,f) { int i; for(i = 1; i < 10; i++) {            \
      int j,r=0; for(j=0;j<p;j++){if(i == c[j]){r=1;break;}}        \
      if(r) continue; c[p] = i; f   } }

#define l_8(b,n,c,p) {                                              \
    int i; for(i=1; i< 10; i++) {int j, r=0;                        \
      for(j=0; j<p; j++) {if(i == c[j]) {r = 1; break;}}            \
      if(r)continue; b[n++] = c[0] * 100000000  + c[1] * 10000000   \
            + c[2] * 1000000 + c[3] * 100000 + c[4] * 10000         \
            + c[5] * 1000 + c[6] * 100 + c[7] * 10 + i; } }

#define l_7(b,n,c,p) l_(b,n,c,p, l_8(b,n,c,8))
#define l_6(b,n,c,p) l_(b,n,c,p, l_7(b,n,c,7))
#define l_5(b,n,c,p) l_(b,n,c,p, l_6(b,n,c,6))
#define l_4(b,n,c,p) l_(b,n,c,p, l_5(b,n,c,5))
#define l_3(b,n,c,p) l_(b,n,c,p, l_4(b,n,c,4))
#define l_2(b,n,c,p) l_(b,n,c,p, l_3(b,n,c,3))
#define l_1(b,n,c,p) l_(b,n,c,p, l_2(b,n,c,2))

#define get_unique_numbers(b,n,c) do {int i; for(i=1; i<10; i++) { \
      c[0] = i; l_1(b,n,c,1) } } while(0)


#define NINE_FACTORIAL  362880

int main(void) {

  //array where numbers would be saved
  uint32_t* unique_numbers = malloc( NINE_FACTORIAL * sizeof(uint32_t) );
  if( !unique_numbers ) {
    printf("Could not allocate memory for the Unique Numbers array.\n");
    exit(1);
  }

  int n = 0;
  int current_number[8] = {0};

  get_unique_numbers(unique_numbers, n, current_number);


  // do stuff with unique_numbers array
  // NINE_FACTORIAL is the number of elements


  free(unique_numbers);

  return 0;
}

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

Ответ 12

РЕДАКТИРОВАТЬ:. После дальнейшего анализа более развернутая рекурсия и только повторение битов с установленными битами привели к значительному улучшению, при тестировании примерно в пять раз быстрее. Это было проверено с помощью OUTPUT UNSET, чтобы сравнить скорость алгоритма, а не консольный вывод, начальная точка uniq_digits9:

int counter=0;
int reps=0;

void show(int x)
{
#ifdef OUTPUT
    printf("%d\n", x);
#else
    counter+=x;
    ++reps;
#endif
}

int bit_val(unsigned int v)
{
  static const int MultiplyDeBruijnBitPosition2[32] =
  {
    0, 1, 28, 2, 29, 14, 24, 3, 30, 22, 20, 15, 25, 17, 4, 8,
    31, 27, 13, 23, 21, 19, 16, 7, 26, 12, 18, 6, 11, 5, 10, 9
  };
  return MultiplyDeBruijnBitPosition2[(unsigned int)(v * 0x077CB531U) >> 27];
}

void uniq_digits1(int prefix, unsigned int used) {
  show(prefix*10+bit_val(~used));
}

void uniq_digits2(int prefix, unsigned int used) {
  int base=prefix*10;
  unsigned int unused=~used;
  while (unused) {
    unsigned int diff=unused & (unused-1);
    unsigned int bit=unused-diff;
    unused=diff;
    uniq_digits1(base+bit_val(bit), used|bit);
  }
}

void uniq_digits3(int prefix, unsigned int used) {
  int base=prefix*10;
  unsigned int unused=~used;
  while (unused) {
    unsigned int diff=unused & (unused-1);
    unsigned int bit=unused-diff;
    unused=diff;
    uniq_digits2(base+bit_val(bit), used|bit);
  }
}

void uniq_digits4(int prefix, unsigned int used) {
  int base=prefix*10;
  unsigned int unused=~used;
  while (unused) {
    unsigned int diff=unused & (unused-1);
    unsigned int bit=unused-diff;
    unused=diff;
    uniq_digits3(base+bit_val(bit), used|bit);
  }
}

void uniq_digits5(int prefix, unsigned int used) {
  int base=prefix*10;
  unsigned int unused=~used;
  while (unused) {
    unsigned int diff=unused & (unused-1);
    unsigned int bit=unused-diff;
    unused=diff;
    uniq_digits4(base+bit_val(bit), used|bit);
  }
}

void uniq_digits6(int prefix, unsigned int used) {
  int base=prefix*10;
  unsigned int unused=~used;
  while (unused) {
    unsigned int diff=unused & (unused-1);
    unsigned int bit=unused-diff;
    unused=diff;
    uniq_digits5(base+bit_val(bit), used|bit);
  }
}

void uniq_digits7(int prefix, unsigned int used) {
  int base=prefix*10;
  unsigned int unused=~used;
  while (unused) {
    unsigned int diff=unused & (unused-1);
    unsigned int bit=unused-diff;
    unused=diff;
    uniq_digits6(base+bit_val(bit), used|bit);
  }
}

void uniq_digits8(int prefix, unsigned int used) {
  int base=prefix*10;
  unsigned int unused=~used;
  while (unused) {
    unsigned int diff=unused & (unused-1);
    unsigned int bit=unused-diff;
    unused=diff;
    uniq_digits7(base+bit_val(bit), used|bit);
  }
}

void uniq_digits9() {
  unsigned int used=~((1<<10)-1); // set all bits except 0-9
#ifndef INCLUDE_ZEROS
  used |= 1;
#endif
  for (int i = 1; i < 10; i++) {
    unsigned int bit=1<<i;
    uniq_digits8(i,used|bit);
  }
}

Краткое описание:

Есть 9 цифр, и первая не может начинаться с нуля, поэтому первая цифра может быть от 1 до 9, остальное может быть от 0 до 9

Если мы возьмем число, X и умножим его на 10, оно сдвинется на одно место. Итак, 5 становится 50. Добавьте число, скажем 3, чтобы сделать 53, а затем умножьте на 10, чтобы получить 520, а затем добавьте 2 и т.д. Для всех 9 цифр.

Теперь требуется некоторое хранилище, чтобы отслеживать, какие цифры использовались, чтобы они не повторялись. Можно использовать 10 истинных/ложных переменных: used_0_p, used_1_P,.... Но это неэффективно, поэтому их можно поместить в массив: used_p[10]. Но тогда его нужно будет копировать каждый раз перед тем, как сделать звонок в следующем месте, чтобы он мог reset его для следующей цифры, иначе, как только все места будут заполнены, первый раз массив будет истинным, и никакие другие комбинации не могут быть вычислено.

Но есть лучший способ. Используйте биты int в качестве массива. X & 1 для первого, X & 2, X & 4, X & 8 и т.д. Эта последовательность может быть представлена ​​как (1<<X) или взять первый бит и сдвинуть его на X раз.

& используется для тестирования бит, | используется для их установки. В каждом цикле мы проверяем, использовался ли бит (1<<i)&used и пропустите, если это было. На следующем месте мы смещаем цифры для каждой цифры prefix*10+i и устанавливаем эту цифру как используемую used|(1<<i)

Объяснение цикла в EDIT

Цикл вычисляет Y & (Y-1), который обнуляет минимальный бит. Принимая оригинал и вычитая результат, разница является младшим битом. Это будет цикл только столько раз, сколько бит: 3,265,920 раз вместо 900 000 000 раз. Переход от используемого к неиспользованному - это просто оператор ~, и поскольку настройка более эффективна, чем отключение, имеет смысл перевернуть

Переход от мощности двух к log2 был взят из: https://graphics.stanford.edu/~seander/bithacks.html#IntegerLog. Этот сайт также описывает механизм цикла: https://graphics.stanford.edu/~seander/bithacks.html#DetermineIfPowerOf2

Перемещение оригинала снизу:

Это слишком длинный комментарий, но Этот ответ может быть сделан несколько быстрее, удалив ненулевую обработку из функции: (См. edit для быстрого ответа)

void uniq_digits(int places, int prefix, int used) {
  if (!places) {
    printf("%d\n", prefix);
    return;
  }
  --places;
  int base=prefix*10;
  for (int i = 0; i < 10; i++)
  {
    if ((1<<i)&used) continue;
    uniq_digits(places, base+i, used|(1<<i));
  }
}

int main(int argc, char**argv) {
  const int num_digits=9;

  // unroll top level to avoid if for every iteration
  for (int i = 1; i < 10; i++)
  {
    uniq_digits(num_digits-1, i, 1 << i);
  }

  return 0;
}

Ответ 13

Простым способом является создание массива с девятью различными значениями, перетасовка и печать перетасованного массива. Повторяйте столько раз, сколько необходимо. Например, используя стандартную функцию rand() в качестве основы для перетасовки...

#include <stdlib.h>     /*  for srand() and rand */
#include <time.h>       /*  for time() */
#include <stdio.h>      

#define SIZE 10     /*   size of working array.  There are 10 numeric digits, so ....   */
#define LENGTH 9    /*  number of digits we want to output.  Must not exceed SIZE */
#define NUMBER 12   /*  number of LENGTH digit values we want to output */

void shuffle(char *buffer, int size)
{
     int i;
     char temp;
     for (i=size-1; i>0; --i)
     {
          /*  not best way to get a random value of j in [0, size-1] but
               sufficient for illustrative purposes
          */
          int j = rand()%size;
          /* swap buffer[i] and buffer[j] */
          temp = buffer[i];    
          buffer[i] = buffer[j];
          buffer[j] = temp;
     }
}

void printout(char *buffer, int length)
{
      /*  this assumes SIZE <= 10 and length <= SIZE */

      int i;
      for (i = 0; i < length; ++i)
          printf("%d", (int)buffer[i]);
      printf("\n");
}

int main()
{
     char buffer[SIZE];
     int i;
     srand((unsigned)time(NULL));   /*  seed for rand(), once and only once */

     for (i = 0; i < SIZE; ++i)  buffer[i] = (char)i;  /*  initialise buffer */

     for (i = 0; i < NUMBER; ++i)
     {
         /*  keep shuffling until first value in buffer is non-zero */

         do shuffle(buffer, SIZE); while (buffer[0] == 0);
         printout(buffer, LENGTH);
     }
     return 0;
}

Отправляет несколько строк в stdout, каждый из которых содержит 9 уникальных цифр. Обратите внимание, что это не предотвращает дублирование.

Ответ 14

итеративная версия, которая использует биты экстенсивно

обратите внимание, что array можно изменить на любой тип и установить в любом порядке это "подсчет" цифр в заданном порядке

Для более подробного объяснения посмотрите мой первый ответ (который менее гибкий, но намного быстрее) fooobar.com/questions/161314/...

Чтобы сделать его итеративным, необходимы массивы для сохранения состояния на каждом уровне

Это также пошло на довольно небольшую оптимизацию для мест, которые оптимизатор не мог понять.

int bit_val(unsigned int v) {
  static const int MultiplyDeBruijnBitPosition2[32] = {
    0, 1, 28, 2, 29, 14, 24, 3, 30, 22, 20, 15, 25, 17, 4, 8,
    31, 27, 13, 23, 21, 19, 16, 7, 26, 12, 18, 6, 11, 5, 10, 9
  };
  return MultiplyDeBruijnBitPosition2[(unsigned int)(v * 0x077CB531U) >> 27];
}

void uniq_digits(const int array[], const int length) {
  unsigned int unused[length-1];                    // unused prior
  unsigned int combos[length-1];                    // digits untried
  int digit[length];                                // printable digit
  int mult[length];                                 // faster calcs
  mult[length-1]=1;                                 // start at 1
  for (int i = length-2; i >= 0; --i)
     mult[i]=mult[i+1]*10;                          // store multiplier
  unused[0]=combos[0]=((1<<(length))-1);            // set all bits 0-length
  int depth=0;                                      // start at top
  digit[0]=0;                                       // start at 0
  while(1) {
    if (combos[depth]) {                            // if bits left
      unsigned int avail=combos[depth];             // save old
      combos[depth]=avail & (avail-1);              // remove lowest bit
      unsigned int bit=avail-combos[depth];         // get lowest bit
      digit[depth+1]=digit[depth]+mult[depth]*array[bit_val(bit)]; // get associated digit
      unsigned int rest=unused[depth]&(~bit);       // all remaining
      depth++;                                      // go to next digit
      if (depth!=length-1) {                        // not at bottom
        unused[depth]=combos[depth]=rest;           // try remaining
      } else {
        show(digit[depth]+array[bit_val(rest)]);    // print it
        depth--;                                    // stay on same level
      }
    } else {
      depth--;                                      // go back up a level
      if (depth < 0)
        break;                                      // all done
    }
  }
}

Некоторые тайминги с использованием только 1-9 с 1000 повторений:

• 15.00s Рекурсивный (измененный для подсчета от 1 до 9) из fooobar.com/questions/161314/...
• 3.53s рекурсия swap из fooobar.com/questions/161314/...
• 2.74s nextPermutation version (fooobar.com/questions/161314/...)
• 2.34s Это решение
• 1.66s развернутая рекурсивная версия в EDIT от fooobar.com/questions/161314/...

Ответ 15

Немного поздно для вечеринки, но очень быстро (здесь 30 мс)...

#include <stdio.h>
#define COUNT 9

   /* this buffer is global. intentionally.
   ** It occupies (part of) one cache slot,
   ** and any reference to it is a constant
   */
char ten[COUNT+1] ;

unsigned rec(unsigned pos, unsigned mask);
int main(void)
{
unsigned res;

ten[COUNT] = 0;

res = rec(0, (1u << COUNT)-1);
fprintf(stderr, "Res=%u\n", res);

return 0;
}

/* recursive function: consume the mask of available numbers
** until none is left.
** return value is the number of generated permutations.
*/
unsigned rec(unsigned pos, unsigned mask)
{
unsigned bit, res = 0;

if (!mask) { puts(ten); return 1; }

for (bit=0; bit < COUNT; bit++) {
        if (! (mask & (1u <<bit)) ) continue;
        ten[pos] = '1' + bit;
        res += rec(pos+1, mask & ~(1u <<bit));
        }
return res;
}

Ответ 16

Составьте список из 10 элементов со значениями 0-9. Вытащите случайные элементы с помощью rand()/w текущей длины списка, пока у вас не будет нужного количества цифр.