01 May 2018

遍历子集


0
1
0 1
2
0 2
1 2
0 1 2
int main(void) {
    int n = 3;

    for (int i = 0; i < (1<<n); i++) {
        for (int j = 0; j < n; j++) {
            if ((i & (1 << j)) != 0) {
                printf("%d ", j);
            }
        }
        printf("\n");
    }

    return 0;
}

dfs1

012
021
102
120
201
210
int map[] = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9};
int res[100];
int v[100];

void dfs(int n, int step) {
    // n 走完 step 步了,现在步数是 step+1 了,不能继续往下走
    if (n == step + 1) {
        for (int i = 1; i <= step; i++) {
            cout << res[i];
        }
        cout << endl;
        return;
    }

    // n 还没走到 step 步
    for (int i = 0; i < step; i++) {
        if (!v[i]) {
            v[i] = 1;
            res[n] = map[i];
            dfs(n+1, step);
            v[i] = 0;
        }
    }
}

int main(void) {
    dfs(1, 3);

    return 0;
}

dfs2

012
013
014
015
021
023
024
025
031
032
034
035
041
042
043
045
051
052
053
054
102
103
int map[] = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9};
int res[100];
int v[100];

void dfs(int n, int step) {
    // n 走完 step 步了,现在步数是 step+1 了,不能继续往下走
    if (n == step + 1) {
        for (int i = 1; i <= step; i++) {
            cout << res[i];
        }
        cout << endl;
        return;
    }

    // n 还没走到 step 步
    for (int i = 0; i <= 5; i++) {  // 可选的集合有 0~5
        if (!v[i]) {
            v[i] = 1;
            res[n] = map[i];
            dfs(n+1, step);
            v[i] = 0;
        }
    }
}

int main(void) {
    dfs(1, 3);

    return 0;
}

dfs3

000
001
002
010
011
012
020
int map[] = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9};
int res[100];
int v[100];

void dfs(int n, int step) {
    // n 走完 step 步了,现在步数是 step+1 了,不能继续往下走
    if (n == step + 1) {
        for (int i = 1; i <= step; i++) {
            cout << res[i];
        }
        cout << endl;
        return;
    }

    // n 还没走到 step 步
    for (int i = 0; i <= 2; i++) {
        res[n] = map[i];
        dfs(n+1, step);
    }
}

int main(void) {
    dfs(1, 3);

    return 0;
}

遍历区间1

0
0 1
0 1 2
0 1 2 3
0 1 2 3 4
0 1 2 3 4 5
0 1 2 3 4 5 6
0 1 2 3 4 5 6 7
0 1 2 3 4 5 6 7 8
0 1 2 3 4 5 6 7 8 9
int n = 10;
for (int i = 1; i <= n; i++) {
    for (int j = 0; j < i; j++) {
        printf("%d ", j);
    }
    printf("\n");
}

遍历区间2

0
1
2
3
4

...

0 1
1 2
2 3
3 4

...

0 1 2
1 2 3
int main(void) {
    int n = 10;
    for (int i = 1; i <= n; i++) {         // 每次遍历的长度
        for (int j = 0; j <= n-i; j++) {   // 长度为 i 的时候,由 j 开始遍历
            for (int k = j; k < i+j; k++) {  // 输出 (j, j+i)
                printf("%d ", k);
            }
            printf("\n");
        }
        printf("\n");
    }

    return 0;
}