c - ユニークな価値を生み出す

Question

C0 から 999999 までの数値を生成するプログラムを作成したいと考えています。生成される数値には、反復する数字が含まれてはならないことに注意してください。たとえば、"123"は許容値ですが"121"、'1'が繰り返されるためではありません。整数に数字が繰り返されているかどうかを確認する他のプログラムコードを入手しました。

整数に繰り返し数字があるかどうかを確認します。文字列メソッドまたは配列なし

数字の重複桁をチェックする最速の方法は何ですか?

しかし、これらは私の問題を実際に解決するものではなく、1,000,000 の異なる値のチェックを実行する場合、非常に非効率的なソリューションです。さらに、提供されているソリューションは for intand not char[]and not でありchar *、プログラムで使用しています。以下はこれまでの私のコードです。ご覧のとおり、 までの値を処理するのに問題はありませんが"012"、3 桁以上の値の可能性はリストするには多すぎて、コーディングするには非効率的です。助けていただければ幸いです。

int i, j;
char genNext[7] = "0";
printf("%s\n", genNext);

// loop through to return next pass in sequence
while (1) {
    for (i = 0; i < sizeof(genNext) / sizeof(char); i++) {
        if (genNext[i] == '9') {
            char * thisPass = strndup(genNext, sizeof(genNext));
            int countDigit = (int) strlen(thisPass);
            switch (countDigit) {
                case 1:
                genNext = "01";
                break;
                case 2:
                if (strcmp(genNext, "98")) {
                    if (i == 0) {
                        genNext[1] += 1;
                    } else {
                        genNext[0] += 1;
                        genNext[1] == '0';
                    }
                } else {
                    genNext = "012";
                }
                break;
                case 3:
                if (strcmp(genNext, "987")) {
                    // code to handle all cases
                } else {
                    genNext = "0123";
                }
                break;
                case 4:
                case 5:
                case 6:
                    // insert code here
            }
            break;
        } else if (genNext[i] == '\0') {
            break;
        } else if (genNext[i+1] == '\0') {
            genNext[i] += 1;
            for (j = 0; j < i; j++) {
                if (genNext[i] == genNext[j]) {
                    genNext[i] += 1;
                }
            }
        } else {
            continue;
        }
    }
    printf("%s\n", genNext);
    if (strcmp(genNext, "987654") == 0) {
        break;
    }
}

私が直面している主な問題は、'9'テストされている値の一部である場合です。たとえば、シーケンス内の"897"is"901"および afterの次の値は、非反復性のルールと結果のシーケンシャル リターン"067895"に"067912"基づいています。

望ましい出力は次のようになります。

0
1
2
3
...
8
9
01
02
03
...
09
10
12
13
...
97
98
012
013
014
...
098
102
103
...
985
986
987
0123
0124
...
etc etc.

私の質問の一部が不明な場合は、お気軽に明確にしてください。ありがとう！

編集:数値のリストのすべての順列を生成するにはどうすればよいですか? シーケンス内の次の「正当な」値としてから"120398"までの増分として私の質問を解決しません。"120435"

EDIT 2：望ましい出力を含むように質問を更新しました

Answer 1

以下に 3 つのバリアント アルゴリズムがあります。バリアント 3 を要件に合わせて調整します。

バリアント 1

これは 1 つの方法です。これは、10 桁カウントのテーブルを 0 に初期化するマイナー バリアントを実装します。数字をスキャンし、遭遇した数字ごとにカウントを増やしてから、数字カウントのいずれかがコメントで提案した複数のアルゴリズムであるかどうかを確認します。テスト関数は、重複する数字が見つかるとすぐに戻ります。

#include <stdio.h>
#include <stdbool.h>

enum { MAX_ITERATION = 1000000 };

static bool duplicate_digits_1(int value)
{
    char buffer[12];
    snprintf(buffer, sizeof(buffer), "%d", value);
    char digits[10] = { 0 };
    char *ptr = buffer;
    char c;
    while ((c = *ptr++) != '\0')
    {
        if (++digits[c - '0'] > 1)
            return true;
    }
    return false;
}

int main(void)
{
    int count = 0;
    for (int i = 0; i < MAX_ITERATION; i++)
    {
        if (!duplicate_digits_1(i))
        {
            count += printf(" %d", i);
            if (count > 72)
            {
                putchar('\n');
                count = 0;
            }
        }
    }
    putchar('\n');
    return 0;
}

実行すると、0 から 1,000,000 までの 168,571 個の値が生成されます。

 0 1 2 3 4 5 6 7 8 9 10 12 13 14 15 16 17 18 19 20 21 23 24 25 26 27 28 29
 30 31 32 34 35 36 37 38 39 40 41 42 43 45 46 47 48 49 50 51 52 53 54 56 57
 58 59 60 61 62 63 64 65 67 68 69 70 71 72 73 74 75 76 78 79 80 81 82 83 84
 85 86 87 89 90 91 92 93 94 95 96 97 98 102 103 104 105 106 107 108 109 120
 123 124 125 126 127 128 129 130 132 134 135 136 137 138 139 140 142 143 145
 146 147 148 149 150 152 153 154 156 157 158 159 160 162 163 164 165 167 168
 169 170 172 173 174 175 176 178 179 180 182 183 184 185 186 187 189 190 192
 193 194 195 196 197 198 201 203 204 205 206 207 208 209 210 213 214 215 216
 217 218 219 230 231 234 235 236 237 238 239 240 241 243 245 246 247 248 249
 250 251 253 254 256 257 258 259 260 261 263 264 265 267 268 269 270 271 273
…
 987340 987341 987342 987345 987346 987350 987351 987352 987354 987356 987360
 987361 987362 987364 987365 987401 987402 987403 987405 987406 987410 987412
 987413 987415 987416 987420 987421 987423 987425 987426 987430 987431 987432
 987435 987436 987450 987451 987452 987453 987456 987460 987461 987462 987463
 987465 987501 987502 987503 987504 987506 987510 987512 987513 987514 987516
 987520 987521 987523 987524 987526 987530 987531 987532 987534 987536 987540
 987541 987542 987543 987546 987560 987561 987562 987563 987564 987601 987602
 987603 987604 987605 987610 987612 987613 987614 987615 987620 987621 987623
 987624 987625 987630 987631 987632 987634 987635 987640 987641 987642 987643
 987645 987650 987651 987652 987653 987654

これが「効率的ではない」と判断する前に、測定してください。パフォーマンスが実際に問題になるほど頻繁に運動していますか?

バリアント 2

コメントで提案した代替バージョンの作成: strchr() を繰り返し使用し、最初の数字が末尾に表示されるかどうかを確認し、そうでない場合は 2 番目の数字が末尾に表示されるかどうかを確認します。最初の答え：

static bool duplicate_digits_2(int value)
{
    char buffer[12];
    snprintf(buffer, sizeof(buffer), "%d", value);
    char *ptr = buffer;
    char c;
    while ((c = *ptr++) != '\0')
    {
        if (strchr(ptr, c) != NULL)
            return true;
    }
    return false;
}

時間を比較すると、これらの結果が得られました ( ng41usesduplicate_digits_1()とng43uses duplicate_digits_2().

$ time ng41 > /dev/null
real    0m0.175s
user    0m0.169s
sys     0m0.002s
$ time ng43 > /dev/null
real    0m0.201s
user    0m0.193s
sys     0m0.003s
$

繰り返しのタイミングは一般的に同様の結果を示しましたが、時々私はng43より速く走りng41ました.

バリアント 3

この手法を使用することもできます。これは「桁数を数える」に似ていますが、最初に文字列に変換する必要はありません (したがって、より高速になるはずです)。

#include <stdio.h>
#include <stdbool.h>
#include <string.h>

enum { MAX_ITERATION = 1000000 };

static bool duplicate_digits_3(int value)
{
    char digits[10] = { 0 };
    while (value > 0)
    {
        if (++digits[value % 10] > 1)
            return true;
        value /= 10;
    }
    return false;
}

int main(void)
{
    int count = 0;
    const char *pad = "";
    for (int i = 0; i < MAX_ITERATION; i++)
    {
        if (!duplicate_digits_3(i))
        {
            count += printf("%s%d", pad, i);
            pad = " ";
            if (count > 72)
            {
                putchar('\n');
                count = 0;
                pad = "";
            }
        }
    }
    putchar('\n');
    return 0;
}

文字列への変換を回避するため、はるかに高速です。一連の 3 回の実行で得られた最も遅いタイミングは次のとおりです。

real    0m0.063s
user    0m0.060s
sys     0m0.001s

これは、他の 2 つよりも約 3 倍高速です。

余分なタイミング

また、MAX_ITERATION の値を 10,000,000 に変更し、タイミングを実行しました。もちろん、拒否された出力は他にもたくさんあります。

$ time ng41 >/dev/null

real    0m1.721s
user    0m1.707s
sys     0m0.006s
$ time ng43 >/dev/null

real    0m1.958s
user    0m1.942s
sys     0m0.008s
$ time ng47 >/dev/null

real    0m0.463s
user    0m0.454s
sys     0m0.004s
$ ng41 | wc
   69237  712891 5495951
$ ng43 | wc
   69237  712891 5495951
$ ng47 | wc
   69237  712891 5495951
$ cmp <(ng41) <(ng43)
$ cmp <(ng41) <(ng47)
$ cmp <(ng43) <(ng47)
$ 

これらのタイミングはより安定していました。バリアント 1 ( ng41) は常にバリアント 2 ( ng43) よりも高速でしたが、バリアント 3 ( ng47) は両方を大幅に上回っています。

JFTR: テストは、古い 17 インチ MacBook Pro (2011 年初頭、16 GB 1333 MHz DDR3 RAM を搭載した 2.3 GHz Intel Core i7) 上の GCC 6.2.0 を搭載した macOS Sierra 10.12.1 で行われました。このコードではメモリが問題になるわけではありません。ご参考までに、プログラム番号は連続した 2 桁の素数です。

---

先行ゼロも

このコードは、必要な数のシーケンスを生成します (ただし、100,000 まで実行するように構成されています — 1,000,000 の変更は簡単です)。マゾヒスティックな意味で面白い。

#include <assert.h>
#include <stdbool.h>
#include <stdio.h>
#include <string.h>

enum { MAX_ITERATIONS = 100000 };

/* lz = 1 or 0 - consider that the number has a leading zero or not */
static bool has_duplicate_digits(int value, int lz)
{
    assert(value >= 0 && value < MAX_ITERATIONS + 1);
    assert(lz == 0 || lz == 1);
    char digits[10] = { [0] = lz };
    while (value > 0)
    {
        if (++digits[value % 10] > 1)
            return true;
        value /= 10;
    }
    return false;
}

int main(void)
{
    int lz = 0;
    int p10 = 1;
    int log_p10 = 0;    /* log10(0) is -infinity - but 0 works better */
    int linelen = 0;
    const char *pad = "";

    /* The + 1 allows the cycle to reset for the leading zero pass */
    for (int i = 0; i < MAX_ITERATIONS + 1; i++)
    {
        if (i >= 10 * p10 && lz == 0)
        {
            /* Passed through range p10 .. (10*p10-1) once without leading zeros */
            /* Repeat, adding leading zeros this time */
            lz = 1;
            i = p10;
        }
        else if (i >= 10 * p10)
        {
            /* Passed through range p10 .. (10*p10-1) without and with leading zeros */
            /* Continue through next range, without leading zeros to start with */
            p10 *= 10;
            log_p10++;
            lz = 0;
        }

        if (!has_duplicate_digits(i, lz))
        {
            /* Adds a leading zero if lz == 1; otherwise, it doesn't */
            linelen += printf("%s%.*d", pad, log_p10 + lz + 1, i);
            pad = " ";
            if (linelen > 72)
            {
                putchar('\n');
                pad = "";
                linelen = 0;
            }
        }
    }
    putchar('\n');
    return 0;
}

出力例 (100,000 まで):

0 1 2 3 4 5 6 7 8 9 01 02 03 04 05 06 07 08 09 10 12 13 14 15 16 17 18 19
20 21 23 24 25 26 27 28 29 30 31 32 34 35 36 37 38 39 40 41 42 43 45 46 47
48 49 50 51 52 53 54 56 57 58 59 60 61 62 63 64 65 67 68 69 70 71 72 73 74
75 76 78 79 80 81 82 83 84 85 86 87 89 90 91 92 93 94 95 96 97 98 012 013
014 015 016 017 018 019 021 023 024 025 026 027 028 029 031 032 034 035 036
037 038 039 041 042 043 045 046 047 048 049 051 052 053 054 056 057 058 059
061 062 063 064 065 067 068 069 071 072 073 074 075 076 078 079 081 082 083
084 085 086 087 089 091 092 093 094 095 096 097 098 102 103 104 105 106 107
108 109 120 123 124 125 126 127 128 129 130 132 134 135 136 137 138 139 140
…
901 902 903 904 905 906 907 908 910 912 913 914 915 916 917 918 920 921 923
924 925 926 927 928 930 931 932 934 935 936 937 938 940 941 942 943 945 946
947 948 950 951 952 953 954 956 957 958 960 961 962 963 964 965 967 968 970
971 972 973 974 975 976 978 980 981 982 983 984 985 986 987 0123 0124 0125
0126 0127 0128 0129 0132 0134 0135 0136 0137 0138 0139 0142 0143 0145 0146
0147 0148 0149 0152 0153 0154 0156 0157 0158 0159 0162 0163 0164 0165 0167
…
0917 0918 0921 0923 0924 0925 0926 0927 0928 0931 0932 0934 0935 0936 0937
0938 0941 0942 0943 0945 0946 0947 0948 0951 0952 0953 0954 0956 0957 0958
0961 0962 0963 0964 0965 0967 0968 0971 0972 0973 0974 0975 0976 0978 0981
0982 0983 0984 0985 0986 0987 1023 1024 1025 1026 1027 1028 1029 1032 1034
1035 1036 1037 1038 1039 1042 1043 1045 1046 1047 1048 1049 1052 1053 1054
1056 1057 1058 1059 1062 1063 1064 1065 1067 1068 1069 1072 1073 1074 1075
…
9820 9821 9823 9824 9825 9826 9827 9830 9831 9832 9834 9835 9836 9837 9840
9841 9842 9843 9845 9846 9847 9850 9851 9852 9853 9854 9856 9857 9860 9861
9862 9863 9864 9865 9867 9870 9871 9872 9873 9874 9875 9876 01234 01235 01236
01237 01238 01239 01243 01245 01246 01247 01248 01249 01253 01254 01256 01257
01258 01259 01263 01264 01265 01267 01268 01269 01273 01274 01275 01276 01278
01279 01283 01284 01285 01286 01287 01289 01293 01294 01295 01296 01297 01298
…
09827 09831 09832 09834 09835 09836 09837 09841 09842 09843 09845 09846 09847
09851 09852 09853 09854 09856 09857 09861 09862 09863 09864 09865 09867 09871
09872 09873 09874 09875 09876 10234 10235 10236 10237 10238 10239 10243 10245
10246 10247 10248 10249 10253 10254 10256 10257 10258 10259 10263 10264 10265
…
98705 98706 98710 98712 98713 98714 98715 98716 98720 98721 98723 98724 98725
98726 98730 98731 98732 98734 98735 98736 98740 98741 98742 98743 98745 98746
98750 98751 98752 98753 98754 98756 98760 98761 98762 98763 98764 98765 012345
012346 012347 012348 012349 012354 012356 012357 012358 012359 012364 012365
012367 012368 012369 012374 012375 012376 012378 012379 012384 012385 012386
…
098653 098654 098657 098671 098672 098673 098674 098675 098712 098713 098714
098715 098716 098721 098723 098724 098725 098726 098731 098732 098734 098735
098736 098741 098742 098743 098745 098746 098751 098752 098753 098754 098756
098761 098762 098763 098764 098765

Answer 2

ループ (0 から 999,999 まで) を使用し、数字の繰り返しで値を拒否することは、私にとって最も簡単な実装のように思えます。

reject-if-duplicate-digits 関数は、かなり高速にすることができます。たとえば、

int has_duplicate_digits(unsigned int value)
{
    unsigned int  digit_mask = 0U;

    do {
        /* (value % 10U) is the value of the rightmost
           decimal digit of (value).
           1U << (value % 10U) refers to the value of
           the corresponding bit -- bit 0 to bit 9. */
        const unsigned int  mask = 1U << (value % 10U);

        /* If the bit is already set in digit_mask,
           we have a duplicate digit in value. */
        if (mask & digit_mask)
            return 1;

        /* Mark this digit as seen in the digit_mask. */
        digit_mask |= mask;

        /* Drop the rightmost digit off value.
           Note that this is integer division. */
        value /= 10U;

        /* If we have additional digits, repeat loop. */
    } while (value);

    /* No duplicate digits found. */
    return 0;
}

Answer 3

これは実際には古典的な組み合わせ問題です。以下は、TAOCP 7.2.1.2 のアルゴリズム L と TAOCP 7.2.1.3 のアルゴリズム T を使用した概念実装の証明です。多少の誤差がある場合がございます。詳細については、アルゴリズムを参照してください。

ここに少し説明があります。を桁t数とする。の場合t == 10、問題はすべての t! を生成することです。セット {0,1,2,...,9} の順列を辞書順で並べ替えます (アルゴリズム L)。

t > 0 および t < 10 の場合、これは次のように分解されます。1) 可能な 10 桁から t 桁のすべての組み合わせを生成します。2)。組み合わせごとに、すべての t! を生成します。順列。

最後に、10 個すべてを並べ替えることができます。+10！/ 2 + 10! / 3！+ .. + 10 件の結果。並べ替えは、最初はコストがかかるように見えるかもしれません。しかし、最初に、組み合わせの生成はすでに字句順になっています。第 2 に、順列の生成も字句順です。したがって、シーケンスは実際には非常に規則的です。ここでは、QSort はそれほど悪くはありません。

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

static inline int compare_str(const void *a, const void *b)
{
    return strcmp(a, b);
}

static inline int compare_char(const void *a, const void *b)
{
    char ca = *((char *) a);
    char cb = *((char *) b);

    if (ca < cb)
        return -1;
    if (ca > cb)
        return 1;
    return 0;
}


// Algorithm L in TAOCP 7.2.1.2
static inline char *algorithm_l(int n, const char *c, char *r)
{
    char a[n + 1];
    memcpy(a, c, n);
    a[n] = '\0';
    qsort(a, n, 1, compare_char);
    while (1) {
        // L1. [Visit]
        memcpy(r, a, n + 1);
        r += n + 1;

        // L2. [Find j]
        int j = n - 1;
        while (j > 0 && a[j - 1] >= a[j])
            --j;
        if (j == 0)
            break;

        // L3. [Increase a[j - 1]]
        int l = n;
        while (l >= 0 && a[j - 1] >= a[l - 1])
            --l;
        char tmp = a[j - 1];
        a[j - 1] = a[l - 1];
        a[l - 1] = tmp;

        // L4. [Reverse a[j]...a[n-1]]
        int k = j + 1;
        l = n;
        while (k < l) {
            char tmp = a[k - 1];
            a[k - 1] = a[l - 1];
            a[l - 1] = tmp;
            ++k;
            --l;
        }
    }

    return r;
}

// Algorithm T in TAOCP 7.2.1.2
static inline void algorithm_t(int t, char *r)
{
    assert(t > 0);
    assert(t < 10);

    // Algorithm T in TAOCP 7.2.1.3
    // T1. [Initialize]
    char c[12]; // the digits
    for (int i = 0; i < t; ++i)
        c[i] = '0' + i;
    c[t] = '9' + 1;
    c[t + 1] = '0';
    char j = t;
    char x = '0';

    while (1) {
        // T2. [Visit]
        r = algorithm_l(t, c, r);

        if (j > 0) {
            x = '0' + j;
        } else {
            // T3. [Easy case?]
            if (c[0] + 1 < c[1]) {
                ++c[0];
                continue;
            }
            j = 2;

            // T4. [Find j]
            while (1) {
                c[j - 2] = '0' + j - 2;
                x = c[j - 1] + 1;
                if (x != c[j])
                    break;
                ++j;
            }

            // T5. [Done?]
            if (j > t)
                break;
        }

        // T6. [Increase c[j - 1]]
        c[j - 1] = x;
        --j;
    }
}

static inline void generate(int t)
{
    assert(t >= 0 && t <= 10);

    if (t == 0)
        return;

    int n = 1;
    int k = 10;
    for (int i = 1; i <= t; ++i, --k)
        n *= k;
    char *r = (char *) malloc((t + 1) * n);
    if (t == 10) {
        algorithm_l(10, "0123456789", r);
    } else {
        algorithm_t(t, r);
    }
    qsort(r, n, t + 1, strcmpv);
    for (int i = 0; i < n; ++i, r += t + 1)
        printf("%s\n", r);
}

int main()
{
    for (int t = 1; t <= 10; ++t)
        generate(t);
}

効率: これは実装があまり効率的ではないことです。理解しやすいように、アルゴリズムからの直訳です。ただし、10^10 の数値を反復処理するよりもはるかに効率的です。0 から 9876543210 までのすべての数値を生成するには、約 2.5 秒かかります。これには、1 行に 1 つの数値を含む 94 MB の出力ファイルであるファイルにそれらを書き込む時間が含まれます。6 桁までの場合、約 0.05 秒かかります。

これらの番号をプログラムで必要な順序に並べたい場合は、上記のように番号を生成して表を作成し、後でその表を使用する方がよい場合があります。0 から 9876543210 までのテーブルでさえ、数は 1,000 万未満であり、今日のコンピューターではそれほど大きな数ではありません。あなたの場合、6桁まで、100万未満の数字しかありません。