すべての桁が区別できる4桁の整数を生成しようとすると奇妙なパターンが発生する

Question

C言語で、すべての桁が異なる0以外の4桁の整数を生成するための小さなプログラムを作成しようとすると返される値は常に1abcのようなパターンになります。最初の数字は常に1と思われますが、戻り値は56127254のように4桁以上になることがあります。事前にどうもありがとうございました。

基本的に、プログラムには2つの機能、int isvalid(int n)とint choose_N(void)が含まれています。

isValid整数が正確に4桁の10進数字で構成されていて、これらの数字はすべて0ではない、別の数字である場合は0、それ以外の場合は0です。

int choose_N(void)は、4桁の整数を生成し、すべての桁は別個で非ゼロです。ここで

が私のコードです：srand(time(0));については

#define N_DIGITS 4 

.... 
....//the main function 

int isvalid(int n){ 
    int i, x; int check[N_DIGITS]={0}; 
    for(i=1;i<=N_DIGITS;i++){ //check whether all digits are nonzero 
    if((check[i-1]=n%10)==0){ 
     return 0; 
    } 
    n /= 10; 
    } 
    for(i=0;i<N_DIGITS-1;i++){ // check whether all digits are distinct 
    for(x=i+1;x<N_DIGITS;x++){ 
     if(check[i]==check[x]) 
     return 0; 
    } 
    } 
    return 1; 
} 

int choose_N(void){ 
    int i; int number=0; 
    while(!isvalid(number)){ 
    for(i=0;i<N_DIGITS;i++){ 
     srand(time(0)); 
     number += ((10^i)*(rand()%10)); 
    } 
    } 
    return number; 
} 

、私はsrand(time(0)+i);のような様々な選択肢を試してみましたかwhileループの外にこの文を置くが、これらの試みは、一見、まだchoose_Nの戻り値を仕事とはまだしませんでしたしています私が記述した厄介なパターンを示しました。

Answer 1

あなたchoose_N方法は、いくつかの問題ました：番号が有効でない場合、あなたは0にそれを

• まずリセットしていないので、それだけで成長し、成長します。
• 第二には、srand(time(0))は、ループ内で必要ありません（といくつかの繰り返しのために同じ結果をもたらす可能性が）、単にプログラム開始（srand() — why call it only once?）
• サードと最大の過ちでそれを実行します。10^iは10 XOR私、ない10**iです。 aux値を使用し、ループで10を掛けることができます。数字の桁数が少ないため、オーバーフローのリスクはありません。
• マイナー発言：ループを少なくとも1回は渡す必要があるため、最初にwhileテストを強制する必要はありません。do/while構文を使用してください。

私はあなたのコードを修正しようとしている：

int choose_N(void){ 
    int i, number; 
    do 
    { 
    number = 0; 
    int p = 1; 
    for(i=0;i<N_DIGITS;i++) 
    {  
     number += p*(rand()%10); 
     p *= 10; 
    } 
    } while(!isvalid(number)); 

    return number; 
} 

Answer 2

ジャンフランソワ・ファーブルの答えは正しいものである@、それは最適なアルゴリズムではありませんが。そのような場合の最適なアルゴリズムは、FIsher-Yates-Knuth shuffleとDurstenfeldの実装を使用しています。

シャッフリング右配列は自動的に有効な数値を生成しますが、基本的にはisvalid(n)はもう必要ありません。

コード

// Swap selected by index digit and last one. Return last one 
int 
swap_array(int digits[], int idx, int last) { 
    if (idx != last) { // do actual swap 
     int tmp = digits[last]; 
     digits[last] = digits[idx]; 
     digits[idx] = tmp; 
    } 

    return digits[last]; 
} 

int 
choose_N_Fisher_Yates_Knuth() { 
    int digits[] = { 1, 2, 3, 4, 5, 6, 7, 8, 9 }; 

    int r = 0; 
    for (int k = 0; k != N_DIGITS; ++k) { 
     int idx = rand() % (9 - k); 

     int n = swap_array(digits, idx, (9 - k) - 1); 
     r = r * 10 + n; 
    } 
    return r; 
} 

int 
main() { 
    srand(12345); 

    int r, v; 

    r = choose_N_Fisher_Yates_Knuth(); 
    v = isvalid(r); 
    printf("%d %d\n", r, v); 

    r = choose_N_Fisher_Yates_Knuth(); 
    v = isvalid(r); 
    printf("%d %d\n", r, v); 

    r = choose_N_Fisher_Yates_Knuth(); 
    v = isvalid(r); 
    printf("%d %d\n", r, v); 

    r = choose_N_Fisher_Yates_Knuth(); 
    v = isvalid(r); 
    printf("%d %d\n", r, v); 

    return 0; 
} 

出力

7514 1 
6932 1 
3518 1 
5917 1