列出符合条件的二进制串

给定n、k、m，列出所有长度为n的满足如下条件的二进制字符串：

字符串中拥有k个1
串中所有1所在的位置之和为m

例：符合n=6，k=3，m=8的串有101100和110010，串长度为6，拥有3个1，并且1所在的位置{1,3,4}和{1,2,5}相加为8。

遍历

思路：遍历所有长度为n的二进制串，依次检查是否符合条件。

第一步：递归生成长度为t的所有二进制串

// 所有全局变量都写在这里，后续不再重复写
int n, k, m
int a[100], total = 0;
int k_a, m_a, subset[100];
void GenBinary(int t) {
    if (t > n) {
      // 生成完毕，二进制串存储在a中。
    }
    else {
        a[t] = 0;
        GenBinary(t + 1); // left branch

        a[t] = 1;
        GenBinary(t + 1); // right branch
    }
}

第二步：检查二进制串是否符合条件

void Process() {
    k_a = 0; // 1的个数
    m_a = 0; // 1所在的位数之和
  	// 计算二进制串的k_a和m_a
    for (int i = 1; i <= n && k_a <= k && m_a <= m; i++) {
        if (a[i] == 1) {
            subset[k_a++] = i;
            m_a += i;
        }
    }
		
  	// 如果符合条件，则输出
    if (k_a == k && m_a == m) {
        for (int i = 1; i <= n; i++) {
            printf("%d", a[i]);
        }
        printf(" is {");
        for (int i = 0; i < k - 1; i++) {
            printf("%d,", subset[i]);
        }
        printf("%d}
", subset[k - 1]);
        total++;
    }
}

第三步：编写main函数，连接起来

int main() {
    printf("Enter n k m: ");
    scanf("%d %d %d", &n, &k, &m);

    clock_t begin,end;
    double cost;
    begin = clock();

    GenBinary(1);
    printf("Total strings = %d
", total);

    end = clock();
    cost = (double) (end - begin) / CLOCKS_PER_SEC;
    printf("program time cost is: %lf secs", cost);
    return 0;
}

三次测试输出：

Enter n k m: 6 3 8
101100 is {1,3,4}
110010 is {1,2,5}
Total strings = 2
program time cost is: 0.000017 secs

Enter n k m: 20 8 80
···
Total strings = 3627
program time cost is: 0.075930 secs

Enter n k m: 30 15 200
···
Total strings = 1059414
program time cost is: 100.832137 secs

时间复杂度O(2^n)。

组合

其实这道题的本质就是计算从1到n一共n个整数中挑选k个整数，使这k个整数之和为m的所有结果。

当n=6，k=3，m=8时可以挑出{1,3,4}和{1,2,5}相加为8，再转换为101100和110010即可。

如此，只需遍历C(n,k)次即可。

第一步：剪枝法选排列组合

// 所有全局变量都写在这里，后续不再重复写
int total = 0, tempSize = 0, n, k, m;
int *temp;
void GenBinary(int cur) {
    if (tempSize + (n - cur + 1) < k) {
        return;
    }
		// 选出一组
    if (tempSize == k) {
      	// 判断是否符合题意
        if (arraySum(temp, k) == m) {
            printResult(temp, k); // 打印出结果
            total++;
        }
        return;
    }

    temp[tempSize++] = cur;
    GenBinary(cur + 1);
    tempSize--;

    GenBinary(cur + 1);
}

int arraySum(const int *array, int arraySize) {
    int sum = 0;
    for (int i = 0; i < arraySize; i++) {
        sum += array[i];
    }
    return sum;
}

第二步：打印结果

void printBinaryArray(const int *array, int arraySize) {
    int cur = 0;
    for (int i = 1; i <= n; i++) {
        if (cur <= arraySize && i == array[cur]) {
            printf("1");
            cur++;
        } else {
            printf("0");
        }
    }
}

void printArray(const int *array, int arraySize) {
    printf("{");
    for (int i = 0; i < arraySize - 1; i++) {
        printf("%d,", array[i]);
    }
    printf("%d}", array[arraySize - 1]);
}

void printResult(const int *array, int arraySize) {
    printBinaryArray(array, arraySize);
    printf(" is ");
    printArray(array, arraySize);
    printf("
");
}

第三步：编写main函数，连接起来

int main() {
    temp = malloc(sizeof(int) * 100);
    printf("Enter n k m: ");
    scanf("%d %d %d", &n, &k, &m);

    clock_t begin, end;
    double cost;
    begin = clock();

    GenBinary(1);
    printf("Total strings = %d
", total);

    end = clock();
    cost = (double) (end - begin) / CLOCKS_PER_SEC;
    printf("Program time cost is: %lf secs", cost);
    return 0;
}

三次测试输出：

Enter n k m: 6 3 8
101100 is {1,3,4}
110010 is {1,2,5}
Total strings = 2
program time cost is: 0.000013 secs

Enter n k m: 20 8 80
···
Total strings = 3627
program time cost is: 0.013682 secs

Enter n k m: 30 15 200
···
Total strings = 1059414
program time cost is: 9.465019 secs

时间复杂度O(C(n,k))。

效率要比遍历高5-10倍。

列出符合条件的二进制串 ​

遍历 ​

组合 ​

列出符合条件的二进制串

遍历

组合