UVA 729 - The Hamming Distance Problem：next_permutation 生成固定漢明距離二進制串

題目大意

給定 N（位數）和 H（漢明距離，即 1 的個數），輸出所有長度為 N、恰含 H 個 1 的二進制串，按字典序遞增。多組測資間空一行。

範例：N=4, H=2 → 0011, 0101, 0110, 1001, 1010, 1100。

解法：STL next_permutation

1. 構造初始串：前 N-H 個 0，後 H 個 1（已是最小字典序）。
2. 用 do { 輸出 } while (next_permutation(...)) 枚舉所有排列。
3. next_permutation 自動按字典序生成下一排列，恰好符合題目要求。

完整代碼 (C++)

#include <cstdio>
#include <algorithm>
using namespace std;

int haming[20];

int main() {
    int T; scanf("%d", &T);
    while (T--) {
        int N, H; scanf("%d%d", &N, &H);
        fill(haming, haming + N - H, 0);
        fill(haming + N - H, haming + N, 1);
        do {
            for (int i = 0; i < N; ++i) printf("%d", haming[i]);
            puts("");
        } while (next_permutation(haming, haming + N));
        if (T) puts(""); // 非最後一組輸出空行
    }
    return 0;
}

複雜度

• 時間：O(C(N,H) * N)，輸出敏感，最優。
• 空間：O(N)。

注意事項

• 初始陣列必須已排序（全 0 在前，全 1 在後），否則會漏解。
• N ≤ 16 題目隱含，int haming[20] 足夠。
• 測資間空行處理：if (T) puts(""); 避免末尾多餘空行導致 PE。