각각의 고유한 숫자로 9자리 숫자를 생성하려고 합니다.
모두 고유한 숫자를 가진 9자리 숫자를 구하려고 합니다.저의 첫 번째 접근 방식은 너무 복잡해 보이고 쓰기에 지루할 것 같습니다.
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
int main()
{
int indx;
int num;
int d1, d2, d3, d4, d5, d6, d7, d8, d9;
for(indx = 123456789; indx <= 987654321; indx++)
{
num = indx;
d1 = num % 10;
d2 = ( num / 10 ) % 10;
d3 = ( num / 100 ) % 10;
d4 = ( num / 1000 ) % 10;
d5 = ( num / 10000 ) % 10;
d6 = ( num / 100000 ) % 10;
d7 = ( num / 1000000 ) % 10;
d8 = ( num / 10000000 ) % 10;
d9 = ( num / 100000000 ) % 10;
if( d1 != d2 && d1 != d3 && d1 != d3 && d1 != d4 && d1 != d5
&& d1 != d6 && d1 != d7 && d1 != d8 && d1 != d9 )
{
printf("%d\n", num);
}
}
}
그것은 단지 첫 번째 숫자와 나머지 숫자를 비교하는 것입니다.다른 숫자들을 비교하기 위해서는 그만큼 더 해야 할 것 같습니다.더 좋은 방법이 없을까요?
이것은 조합론과 관련된 문제의 전형적인 예입니다.
정확히 9개의 ⋅8 ⋅7 ⋅6 ⋅5 ⋅4 ⋅2 ⋅1 = 9! = 362880 9자리의 십진 숫자로 각 숫자는 정확히 한 번씩 발생하며 0은 전혀 사용되지 않습니다.각 숫자는 한 번씩만 사용하기 때문에 첫 번째 숫자는 9개, 두 번째 숫자는 8개 등의 가능성이 있기 때문입니다.
따라서, 각 조합이 정확히 하나의 시드에 대응하도록 고유한 조합 중 하나를 반환하는 시드 0 ≤ 시드 < 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배열은 지금까지 사용되지 않은 9자리 집합으로 초기화됩니다.i는 해당 다.digit[i]는 실제 사용된 숫자입니다.됩니다.n1이 줄어듭니다.
몇 가지 예제 결과:
unique9(0U) == 198765432U
unique9(1U) == 218765439U
unique9(10U) == 291765438U
unique9(1000U) == 287915436U
unique9(362878U) == 897654321U
unique9(362879U) == 987654321U
는 의 입니다.digit배열 전환 위치.
편집: 20150826:면을 .index를 들어(대로), 방식을 할 수
#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 더 대로, d0 <= index < length!,그리고나서buffer입니다를 갖는 이 될 입니다.index가장 작은 값예를 들어, 만약digits="1234"그리고.length=4,그리고나서index=0buffer="1234",index=1buffer="1243".index=23buffer="4321".
위의 구현은 어떤 방식으로든 최적화되어 있지 않습니다.초기 루프는 오버플로 탐지를 사용하여 요인을 계산하는 것입니다.그것을 피하는 한가지 방법은 임시방편을 사용하는 것입니다.size_t [length].unique9()에서 더;더;면,다와 .unique9()더 memmove()s 필요(대신 교환).
이 방법은 일반적입니다.예를 들어, 각 문자가 고유하거나 특정 문자만 사용하는 N 문자 단어를 생성하고자 했다면 동일한 접근 방식이 효율적인 해결책을 제공할 것입니다.
먼저 작업을 단계별로 나눕니다.
가가 .n사용되지 않은 숫자가 남아 있습니다.digit[]배열, 그리고 우리는 사용할 수 있습니다.seed사용하지 않은 다음 숫자를 선택합니다.
i = seed % n;si의 경우 나머지(modulus)까지seed이었습니다에 의해 .n 는 입니다. , 는입니다.i과 0n-1,0 ≤ i < n.
하려면 다음과 같이 하십시오.seed다라는 . 우리는 분할을 합니다.seed = seed / n;.
다음으로 결과에 숫자를 추가합니다. 새 에에 10여)하고를하여 가장 에할 수 .result = result * 10 + digit[i] C .U숫자 상수의 끝에는 단지 상수가 부호가 없음을 컴파일러에게 알려줍니다(integer).은 ()L위해서long,UL위해서unsigned long , , LL위해서long long,그리고.ULL위해서unsigned long long.)
가 끈을 을 digit[i]문자 배열의 다음 위치로 이동하고 위치를 늘립니다.(줄로 만들기 위해서는 줄 끝 글자를 넣는 것만 기억하면 됩니다.'\0'에),
으로, 에, 를 .digit[i]digit[] array를 . 나는 이것을 대체함으로써 합니다.digit[i]의 맨 ,digit[n-1] , , , .n-- 이 은 됩니다를 하여 수행됩니다.digit[i] = digit[--n];입니다와 정확히
digit[i] = digit[n - 1];
n = n - 1;
만약 에서,n여전히 0보다 크므로 절차를 반복하는 것만으로 다른 숫자를 추가할 수 있습니다.
를 할 수 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;
}
에서의 함수 strlen자 ,seed할 수 입니다를 그리고 그것은 채워질 것입니다.str대 26의 len-1각 소문자가 최대 한 번 발생하는 문자(whichever가 작음).
접근 방식이 명확하지 않은 경우 다음 사항을 문의하십시오.저는 분명히 해두고 싶습니다.
비효율적인 알고리즘을 사용함으로써 엄청난 양의 자원(전기뿐만 아니라 인간의 사용시간)이 손실됩니다. 단지 당면한 문제를 효율적인 방법으로 해결하는 것보다 느리고 비효율적인 코드를 작성하는 것이 더 쉽기 때문입니다.우리는 그런 식으로 돈과 시간을 낭비합니다.올바른 해결책이 이 경우처럼 간단할 때, 그리고 앞서 말했듯이, 이것이 여러 조합 문제로 확장될 때, 저는 프로그래머들이 그것을 배우는 데 15분이 걸리고, 폐기물이 확산되고 확장되는 것을 보는 것보다, 유용할 때마다 적용하는 것을 보고 싶습니다.
많은 답변과 코멘트는 이러한 모든 조합을 생성하는 것을 중심으로 이루어집니다.저는 개인적으로 그 세트가 이미 잘 알려져 있기 때문에 별로 쓸모가 없다고 봅니다.실제로는 일반적으로 작은 부분 집합(예: 쌍, 세 쌍둥이 또는 큰 부분 집합)을 생성하거나 일부 기준을 충족하는 부분 집합을 생성하려고 합니다. 예를 들어 각 9자리 숫자가 한 쌍이 아니라 두 번 사용되는 그러한 숫자의 쌍을 10개 생성하려고 할 수 있습니다.제 시드 접근 방식은 이를 쉽게 허용합니다. 십진법 대신 연속 시드 값으로 작업합니다(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;
}
순열 함수는 재귀 함수이지만 최대 재귀 깊이는 문자열 길이입니다.함수에 대한 총 호출 수는 a(N)이고, 여기서 N은 문자열의 길이이며, 이 경우 a(n)=n ⋅a(n-1)+1(시퀀스 A002627), 623530 호출입니다.일반적으로 a(n)≤(1-e)n!, 즉 a(n)<1.7183n!이므로 호출 횟수는 O(N!), 즉 순열된 항목 수에 대한 요인입니다.루프 본체는 호출에 비해 한 번 더 적게 반복됩니다. 여기서 623529번입니다.
논리는 첫 번째 코드 스니펫과 동일한 배열 접근 방식을 사용하여 매우 간단합니다. 다만, 이번에는 배열의 "트림 오프" 부분이 실제로 치환 문자열을 저장하는 데 사용된다는 점을 제외하고는 말입니다.즉, 아직 남아 있는 각 문자를 트리메드 오프(또는 마지막 문자열 앞에 붙임)할 다음 문자와 교환하고 재귀 호출을 수행한 다음 두 문자를 복원합니다.재귀적 호출이 있을 때마다 각 수정이 실행 취소되므로 버퍼의 문자열은 호출 후 이전과 동일합니다.애당초 수정된 적이 없는 것처럼 말입니다.
위의 구현은 1바이트 문자를 가정합니다(예: 멀티바이트 UTF-8 시퀀스와 올바르게 작동하지 않음).유니코드 문자 또는 다른 멀티바이트 문자 집합에 있는 문자를 사용하려면 대신 넓은 문자를 사용해야 합니다.종류 변경, 문자열 출력 기능 변경 외에 다른 변경은 필요 없습니다.
때, 함수로 그 숫자들의 다음 (함수 , 합니다라고 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 };
그런 다음 코드는 이 9개 숫자의 모든 362880 순열을 오름차순으로 생성하여 표시합니다.
nextPermutation에는 3다가 .
- 하여 첫 을 (call it)).
x에 큰 ) 됩니다가 나타납니다. - 하여 첫 을 (call it)).
y보다 큰x, 교환과 스왑x그리고.y 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배열의 마지막 5개 숫자가 내림차순이라는 사실은 바꾸지 않았습니다.
는 입니다 입니다.6그들이 모두 오름차순으로 되게 하십니다.으로 되어 을 알고 있기 에, 에,입니다,입니다를 입니다.82, .73은. 결과 배열은
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기능. 이 됩니다.이 기능은 시연용으로만 사용됩니다.배열이 한 자리 숫자만 포함한다고 가정하고 오버플로를 확인할 필요가 없습니다.입니다.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;
}
이 알고리즘의 성능에 약간의 관심이 있는 것 같기 때문에 다음과 같은 숫자가 있습니다.
길이= 2 perms= 2 (swaps= 1 ratio= 0.500) 시간= 0.000msec길이= 3 perms= 6 (swaps= 7 ratio= 1.167) 시간= 0.000msec길이= 4 perms= 24 (swaps= 34 ratio= 1.417) 시간= 0.000msec길이=5 perms=120 (swaps=182 ratio=1.517) 시간=0.001msec길이=6 perms=720 (swaps=1107 ratio=1.538) 시간=0.004msec길이=7 perms=5040 (swaps=7773 비율=1.542) time= 0.025msec길이=8 perms=40320 (swaps=62212 ratio=1.543) 시간=0.198msec길이 = 9 perms = 362880 (swaps = 559948 비율 = 1.543) 시간 = 1.782 msec길이=10 perms=3628800 (swaps=5599525 비율=1.543) 시간=16.031msec길이=11 perms=39916800 (swaps=61594835 비율=1.543) 시간=170.862 msec길이=12펌=479001600 (swaps=739138086비=1.543)시간=2036.578msec
테스트용 CPU는 2.5Ghz 인텔 i5 프로세서였습니다.이 알고리즘은 초당 약 2억 개의 순열을 생성하며, 9개 숫자의 모든 순열을 생성하는 데는 2밀리초도 걸리지 않습니다.
또한 흥미로운 점은 이 알고리즘이 평균적으로 순열당 약 1.5개의 스왑만 필요하다는 것입니다.절반의 시간 동안 알고리즘은 배열의 마지막 두 숫자만 맞춥니다.알고리즘은 24건 중 11건에서 2건의 스왑을 수행합니다.따라서 알고리즘에 두 번 이상의 교환이 필요한 경우는 24건 중 1건에 불과합니다.
최종적으로 다음 두 개의 배열로 알고리즘을 시도했습니다.
int array[] = { 1, 2, 2, 3 }; // generates 12 permutations
int array[] = { 1, 2, 2, 3, 3, 3, 4 }; // generates 420 permutations
순열의 수는 예상대로이고 출력도 정확한 것으로 보여, 숫자가 유일하지 않으면 알고리즘도 작동하는 것 같습니다.
재귀는 여기서 잘 작동합니다.
#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;
}
문자 집합의 모든 순열을 인쇄하는 간단한 프로그램이 있습니다.이를 쉽게 변환하여 필요한 모든 숫자를 생성할 수 있습니다.
#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) 순열을 생성하는지 확인할 수 있습니다.
여기에는 긴 코드 덩어리가 많이 있습니다.더 많이 생각하고 코드를 덜 쓰는 것이 좋습니다.
우리는 낭비 없이 각 가능성을 정확히 한 번만 만들어 보고 싶습니다.이것은 방출되는 숫자당 일정한 양의 노력만으로 가능한 것으로 나타났습니다.
코드 없이 어떻게 할 수 있습니까?카드 10장을 받아서 0부터 9까지의 숫자를 써주세요.테이블 상판에 정사각형 9개 행을 그립니다.카드를 고르세요.첫 번째 칸에 넣고, 두 번째 칸에 넣어주세요.9를 뽑으면 첫 번째 번호가 나옵니다.이제 마지막 카드를 제거하고 가능한 각 대안으로 교체합니다. (이 경우에는 1장만 있습니다.)모든 제곱이 채워질 때마다 다른 숫자가 나타납니다.마지막 제곱에 대한 모든 대안을 완료했으면 마지막 2를 수행합니다.모든 상자에 대한 모든 대안을 고려할 때까지 마지막 3개 등을 반복합니다.
이를 위해 간단한 프로그램을 작성하는 것은 간단한 데이터 구조를 선택하는 것입니다.9제곱 행에 문자 배열을 사용합니다.
카드 집합에 다른 배열을 사용합니다.배열 A에 저장된 크기 N 집합에서 요소를 제거하려면[0..N-1], 우리는 오래된 속임수를 사용합니다.제거하고 싶은 원소를 A[I]라고 합니다.A[I] 값을 옆으로 빼놓습니다.그런 다음 마지막 요소 A[N-1]를 "아래"로 복사하고 A[I]를 덮어씁니다.새 세트는 A[0..N-2] 세트로 주문해도 상관없기 때문에 잘 됩니다.
나머지는 모든 가능한 대안을 열거하기 위해 재귀적 사고를 사용하는 것입니다.M 크기의 문자 집합에서 N 크기의 문자열로 모든 선택 항목을 찾는 방법을 알고 있다면 알고리즘을 얻으려면 첫 번째 문자열 위치에서 가능한 각 문자를 선택한 다음 M-1 크기의 나머지 집합에서 나머지 N-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;
}
첫 번째 포지션에 0을 넣어도 되는지에 대해서는 언급을 안 하셨잖아요.그렇지 않다고 가정합니다.알고리즘을 잘 이해하고 있기 때문에 첫 번째 위치에 0을 선택하는 것을 피하기 쉽습니다.라를 그 지나쳐라,하면요.!pospos가 0면 0에 C서다 1고이면 입니다.에 들지 면,요를 시도해 .(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;
}
숫자에 이미 숫자가 표시되었는지 여부에 관계없이 마스크를 사용하여 플래그를 설정할 수 있습니다.다음과 같은 경우:
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;
}
한 가지 접근법이 있습니다. 고유한 숫자 배열로 시작한 다음 임의로 섞습니다.
#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;
}
일부 샘플 출력:
john@marvin:~/Development/snippets$ ./nine
number is 249316578
john@marvin:~/Development/snippets$ ./nine
number is 928751643
john@marvin:~/Development/snippets$ ./nine
number is 621754893
john@marvin:~/Development/snippets$ ./nine
number is 317529864
숫자 값이 아닌 고유한 10진수 문자열이므로 해당 정수 값을 사용하려면 다음과 같은 변환을 수행해야 합니다.
long val = strtol( digits, NULL, 10 );
10개의 변수보다는 각 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;
}
OP는 제가 출근하면서 질문을 분명히 했고, 저는 요청받은 0이 부족하다는 것에 집중하지 않았습니다.(지금 응답이 업데이트됨).이렇게 하면 예상되는 362880 조합이 생성됩니다.
그러나 - 답변이 가장 빠르다는 의견이 있어 후속 조치가 필요합니다.(이것을 세어 보면) 세 가지의 답이 세 개 있었습니다.빠른 확인 중:
- @Paul Hankin의 대답(0을 세고 3265920 조합을 제공):
리얼 0m0.951s사용자 0m0.894ssys0m0.056s
- 이것은:
리얼 0m49.108s사용자 0m49.041ssys0m0.031s
- @George André의 답변(예상되는 조합의 수를 산출하기도 함):
리얼 1m27.597s사용자 1m27.476ssys0m0.051s
이 코드를 확인합니다.
#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;
}
질문이 있으시면 언제든지 물어보세요.
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));
}
이렇게 하면 중복된 숫자가 없는 3자리 16진수 값의 순서 목록이 출력됩니다.
seed 0 -> 012
seed 1 -> 013
...
seed 3358 -> FEC
seed 3359 -> FED
저는 당신이 이 세심하게 만들어진 숫자열을 가지고 실제로 무엇을 하고 있는지 모릅니다.만약 어떤 가난한 유지 엔지니어가 버그를 고치기 위해 당신 뒤에 와야 한다면, 사람이 씨앗을 염기서열 값으로 변환하는 것이 훨씬 더 쉽기 때문에, 나는 주문된 버전을 추천합니다.
에 중첩된 를 .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;
}
나는 그 매크로들을 쓰는 더 좋은 방법들이 있다고 확신하지만, 그것은 내가 생각할 수 있는 것입니다.
9개의 서로 다른 값을 가진 배열을 만들어 섞고 셔플된 배열을 인쇄하는 것이 간단한 방법입니다.필요한 만큼 반복합니다.를 들어어를 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개의 고유한 숫자가 있습니다.이것이 중복을 방지하는 것은 아닙니다.
편집: 추가 분석 후, 재귀 실행을 더 많이 실행하고 세트 비트에서만 반복하면 테스트 속도가 약 5배 빠르게 향상됩니다.이것은 다음과 같이 테스트되었습니다.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개이고 첫 번째 숫자는 0으로 시작할 수 없으므로 첫 번째 숫자는 1부터 9까지이고 나머지 숫자는 0부터 9까지입니다.
만약 우리가 숫자 X를 취하고 그것에 10을 곱하면, 그것은 한 자리 이동합니다.그래서 5는 50이 됩니다.숫자를 더해서 3이라고 하면 53이 되고 10을 곱하면 520이 되고, 9자리 모두에 2를 더하면 됩니다.
이제 사용된 숫자를 반복하지 않도록 추적하기 위해 스토리지가 필요합니다.참/false 변수 10개를 사용할 수 있습니다.used_0_p,used_1_P 하지만 이므로 배열로할 수 : , ...... 하지만 이는 비효율적이므로 배열로 배치할 수 있습니다.used_p[10]그러나 할 수 그렇지 할 수 그러나 다음 자리로 전화를 걸기 전에 매번 복사해야 다음 자리로 재설정할 수 있습니다. 그렇지 않으면 처음 배열이 모두 참이고 다른 조합을 계산할 수 없게 됩니다.
하지만, 더 좋은 방법이 있습니다.의 비트를 사용합니다.intX & 1으로입니다.X & 2,X & 4,X & 8 이 은 , . 수 있습니다.(1<<X)첫 번째 비트를 가져다가 X번에 걸쳐 이동합니다.
&비트를 테스트하는 데 사용됩니다.|설정하는 데 사용됩니다.각 루프에서 비트가 사용되었는지 여부를 테스트합니다.(1<<i)&used만약 그랬다면 건너뛸 겁니다다음 장소에서는 각 숫자에 대한 숫자를 이동합니다.prefix*10+i그리고 그 숫자를 사용된 것처럼 설정합니다.used|(1<<i)
EDIT의 루프에 대한 설명
는 합니다를 합니다.Y & (Y-1)가장 낮은 설정 비트를 영점화합니다.원본을 취하고 결과를 빼면 차이가 가장 낮은 비트가 됩니다.이것은 비트 수만큼만 루프합니다: 900,000,000번이 아닌 3,265,920번.사용된 것에서 사용되지 않은 것으로 전환하는 것은 단지~보다 더 ,했습니다를 이 타당했습니다.
https://graphics.stanford.edu/ ~seander/bithacks.html#IntegerLog에서 2의 power에서 log2로 이동했습니다.또한 이 사이트에서는 루프 메커니즘에 대해 자세히 설명합니다. https://graphics.stanford.edu/ ~seander/bithacks.html #DeterminateIfPowerOf2
원본을 아래쪽으로 이동:
주석을 달기에는 너무 길지만, 함수에서 제로 핸들링을 제거하면 이 답변을 다소 빠르게 만들 수 있습니다. (빠른 답변은 편집 참조)
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;
}
파티에 좀 늦었지만, 매우 빠른 속도(여기서 30ms)...
#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;
}
비트를 광범위하게 사용하는 반복 버전
라는 점에 주목합니다.array할 수 된 순서며의 트"다를를합니다.
자세한 설명은 첫 번째 답변(유연하지만 훨씬 빠른 답변)을 보십시오. https://stackoverflow.com/a/31928246/2963099
반복적으로 구현하기 위해서는 각 레벨에서 상태를 유지하기 위한 어레이가 필요했습니다.
이 작업은 옵티마이저가 찾을 수 없는 곳에 대한 상당한 최적화 작업을 거치기도 했습니다.
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,000개의 표현으로 1~9개만 사용하는 타이밍도 있습니다.
- https://stackoverflow.com/a/31828305/2963099 에서 15.00s 재귀적(카운트 1에서 9로 수정됨)
- https://stackoverflow.com/a/31830671/2963099 에서 3.53초만에 재귀
- 2.74초 다음 퍼뮤테이션 버전 (https://stackoverflow.com/a/31885811/2963099)
- 2.34s 이 솔루션
- https://stackoverflow.com/a/31928246/2963099 에서 EDIT의 1.66s 재귀적 버전을 언롤드했습니다.
값이 0~9인 원소 10개로 목록을 작성합니다.원하는 자릿수가 될 때까지 rand() /w 현재 목록 길이로 임의 요소를 꺼냅니다.
언급URL : https://stackoverflow.com/questions/31826746/trying-to-generate-9-digit-numbers-with-each-unique-digits
'programing' 카테고리의 다른 글
| C의 텍스트 파일에서 int 값 읽기 (0) | 2023.09.24 |
|---|---|
| Wocommerce Add To Cart 전체 재고를 카트에 추가하기 (0) | 2023.09.24 |
| 헤더 전용 프로젝트를 생성하도록 CMake를 설정하려면 어떻게 해야 합니까? (0) | 2023.09.24 |
| Oracle 객체가 얼마나 널리 사용됩니까? (0) | 2023.09.24 |
| querySelector 사용방법특정 속성 집합을 가진 요소에 대해서만 모두? (0) | 2023.09.24 |