Problem 729 The Hamming Distance Problem

此題題目我看的沒有很清楚，但是一看它的輸出入就知道它輸入兩個整數 N 和 H 後，N 為字串長度，H 為 1 的數量，例如：N = 3, H = 2，所以一開始就是 011 為初始字串。要請你求出這字串的所有不重複的排列組合。

一開始要先將初始字串設定好：

scanf("%d %d", &m, &h);
for (j = 0; j < m; j ++)
{
    if (j < m - h) str[j] = '0';
    else str[j] = '1';
}
str[m] = '\0';

再用與 Problem 146 的 next_permutation 函式或 C ++ 中的 next_permutation 的方法，持續找尋下一組的排列組合並且印出，直到找不到為止。C 語言程式碼如下：

void swap(int i, int j)
{
     char tmp;
     tmp = str[i];
     str[i] = str[j];
     str[j] = tmp;
} 

int next_permutation()
{
     int i, j, k;
     int length;
     length = strlen(str);
     for(i = length - 1;i > 0 ; --i)
      if(str[i - 1] < str[i]) break;
     j = i;
     if(j == 0) return 0;
     for(i = length - 1;i > 0; --i)
      if(str[j - 1] < str[i]) break;
     k = i;
     swap(j - 1, k);
     for(i = j, j = length - 1;i < j; ++ i, -- j)
      swap(i, j);
   return 1;
}

最後只需要在主程是內如此呼叫：

printf("%s\n", str);
while (next_permutation())
{
    printf("%s\n", str);
}

By David.K

p729題目連結
回ACM題庫目錄
回首頁