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

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

Есть ровно 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 символов digit .

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

 #include  #include  #include  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 . Например, если digits="1234" и length=4 , то index=0 даст buffer="1234" , index=1 даст buffer="1243" и т. Д., Пока index=23 не даст buffer="4321" .

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

---

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

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

Выше мы имеем 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 в конце числовой константы просто сообщает компилятору, что константа unsigned (целое число). (Остальные L для long , UL для unsigned long , и если компилятор поддерживает их, LL для long long и ULL для unsigned long long .)

Если бы мы строили строку, мы бы просто поместили digit[i] в следующую позицию в массиве символов и увеличили ее. (Чтобы превратить его в строку, просто не забудьте указать конец строки 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  #include  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 раз здесь.

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

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

Учитывая массив чисел, можно сгенерировать следующую перестановку этих чисел с довольно простой функцией (назовем эту функцию 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 функция 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 функция 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 функция nextPermutation работает для любого массива чисел (цифры не обязательно должны быть последовательными). Так, например, если начальный массив

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

то nextPermutation функция 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
 длина = 3 перм = 6 (свопы = 7 отношение = 1,177) время = 0,000 мсек
 length = 4 perms = 24 (swaps = 34 ratio = 1.417) time = 0.000msec
 длина = 5 перм = 120 (свопы = 182 отношение = 1,517) время = 0,001 мсек
 длина = 6 перм = 720 (свопы = отношение 1107 = 1,538) время = 0,004 мсек
 длина = 7 перм = 5040 (свопы = 7773 отношение = 1,542) время = 0,025 мсек
 длина = 8 перм = 40320 (свопы = 62212 отношение = 1,543) время = 0,198 мсек
 длина = 9 перм = 362880 (свопы = 559948 отношение = 1,543) время = 1,782 мсек
 длина = 10 перм = 3628800 (свопы = 5599525 отношение = 1,543) время = 16,031 мсек
 длина = 11 перм = 39916800 (свопы = 61594835 отношение = 1,543) время = 170,862 мсек
 длина = 12 перм = 479001600 (свопы = 739138086 отношение = 1,543) время = 2036,578 мсек

Процессором для тестирования был процессор 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 

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

Здесь хорошо работает recursion.

 #include  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<