假設只能使用兩種符號來組成字串，譬如 IOIOI 或 OOII，都是由 I 和 O 組成，長度分別是 5 和 4。如果給定一個這樣的字串，同時又告訴你其中只有N個符號是正確的，能否把全部可能的答案都產生出來？例如輸入的字串是 TTTFF，然後又跟你說其中只對了 4 個符號，則可能的答案應該會有下面五種： 
TTTFT
TTTTF
TTFFF
TFTFF
FTTFF
再舉一個例子，如果輸入的字串是 OXOX，而其中只有 2 個符號是對的，則可能的答案會有底下六種：
OXXO
OOOO
OOXX
XXOO
XXXX
XOOX
答案要依照一定順序列出。決定順序的規則如下：盡量讓靠右邊的符號先變，盡量讓靠左邊的符號維持不變。以上面的輸入字串 OXOX (2個符號正確)為例，答案 OXXO 會排 OOOO 前面，因為 OXXO 和原本的輸入字串 OXOX 的最左兩個符號是相同的，但是 OOOO 和原本的輸入字串 OXOX 則是左邊第二個符號就不相同，所以 OXXO 的順位高於 OOOO。同理可以去檢驗其他順序，例如答案OOXX 順位高於 XXOO，因為OOXX 最左邊的符號和原輸入 OXOX 相同，但 XXOO 最左邊的符號就已經和 OXOX 不同。
再看一個範例：假設構成的符號有P 和 Q，輸入的字串是PPP，只對 1 個符號，則答案是
PQQ
QPQ
QQP
註:這一題可以自己寫，也可以直接改程式框架，寫出 void check_bits(int cur_bit, int num_hits)。
 

Hint:

#include 
#include 
#define MAXBITS 16

char bits[3];
char input[MAXBITS+1];
char answer[MAXBITS+1];
int NBITS;

void check_bits(int cur_bit, int num_hits);
char flip(char ch);

int main(void)
{
    int nhits;

    /* Read the two symbols for the binary bits,
    e.g, OI, 01, OX, or -+, etc. */
    scanf("%2s", bits);

    /* Read the input bit string. */
    scanf("%s", input);
    NBITS = strlen(input);

    /* The answers will be stored in the array answer[] */
    answer[NBITS] = '\0';

    /* Read the number of correct bits */
    scanf("%d", &nhits);

    /* Call the recursive function check_bits
    Start from the leftmost bit. */
    check_bits(0, nhits);

    return 0;
}

/*
1.
The value of cur_bit keeps increasing as we
recursively call check_bits().
2.
If input[cur_bit] is correct, the value of num_hits
should decrease; otherwise we should keep num_hits unchanged
and check the next bit.
3.
Copy the bit from input[cur_bit] or flip the bit,
and store the result in the array answer[].
4.
If the recursive call reaches the end of the input,
it is done and we may print the answer using
    printf("%s
", answer);
*/
void check_bits(int cur_bit, int num_hits)
{
    /* YOUR CODE */

}

/*
Flip the bit. For example,
0 <--> 1
O <--> I
...
*/
char flip(char ch)
{
    return ( (ch==bits[0]) ? bits[1] : bits[0] );
}

底下的表示法，方括號 [] 代表 list，圓括弧 () 代表 pair。
譬如第一個 list 是 [1,2,3] 而第二個是 ["a","b","c"]，經過 zip 之後變成
[(1,"a"),(2,"b"),(3,"c")]。
接著如果再用第二個 list 和第一次 zip 之後的結果，再做一次 zip，結果會變成
[("a",(1,"a")),("b",(2,"b")),("c",(3,"c"))]
然後第一次 zip 和第二次 zip 得到的兩個 lists，再做第三次 zip 就變成
[((1,"a"),("a",(1,"a"))),((2,"b"),("b",(2,"b"))),((3,"c"),("c",(3,"c")))]

上述的操作已經寫在範例程式中，只要將 zip 正確寫出，就能產生上述的執行結果。

範例程式:

#include 
#include 
#include 
#include 


/* incomplete struct Atom */
struct Atom;

/* a pair of atom */
typedef struct Pair {
    struct Atom *left;
    struct Atom *right;
} Pair;

/* a list of atoms */
typedef struct List {
    struct Atom *data;
    struct List *next;
} List;

/* an atom can be a string, an int, a pair of atoms, or a list */
typedef struct Atom {
    char str[21];
    int val;
    Pair *pair;
    List *lst;
    int dtype; /* 0 for string, 1 for int, 2 for pair, 3 for list*/
} Atom;



/* functions for creating an atom */
Atom* atom_str(char *str);
Atom* atom_val(int val);

Atom* copy_atom(Atom *aptr);
void print_atom(Atom *aptr);
void free_atom(Atom *atpr);

/* convert an atom to a single-atom list */
List* atom_to_list(Atom *a);

/* this function is important */
/* useful for creating a new copy of an existing list */
List* cons(Atom *a, List *b);

void print_list(List *lptr);
void free_list(List *lptr);
int length(List *lptr);
List* read_list_helper(List *l, int n);
List* read_list(void);

Atom* head(List *lptr);
List* tail(List *lptr);

List* zip(List *lptr1, List *lptr2);
Pair* unzip(List *lptr);

List* take(int n, List *l);
List* drop(int n, List *l);

Pair* pair_list(List *lptr1, List *lptr2);
Pair* split_at(int n, List *l);

void print_pair(Pair* p);
void free_pair(Pair* p);

int main(void)
{
    List *s1, *s2, *s3;
    int N, i;

    s1 = read_list();
    s2 = read_list();
    s3 = NULL;

    scanf("%d", &N);
    for (i=0; istr[0] = 'Θ';
    } else {
        strncpy(aptr->str, str, 20);
    }
    aptr->val = 0;
    aptr->pair = NULL;
    aptr->lst = NULL;
    aptr->dtype = 0;
    return aptr;
}

/* Given a value, create a new atom */
Atom* atom_val(int val)
{
    Atom *aptr = (Atom*) malloc(sizeof(Atom));
    aptr->str[0] = 'Θ';
    aptr->val = val;
    aptr->pair = NULL;
    aptr->lst = NULL;
    aptr->dtype = 1;
    return aptr;
}


Atom* copy_atom(Atom *aptr)
{
    Atom *aptr_new;

    aptr_new = (Atom*) malloc(sizeof(Atom));

    if (aptr_new==NULL) return NULL;
    if (aptr==NULL) return NULL;

    aptr_new->dtype = aptr->dtype;

    if (aptr->dtype == 0) {
        strncpy(aptr_new->str, aptr->str, 20);
    } else if (aptr->dtype == 1) {
        aptr_new->val = aptr->val;
    } else if (aptr->dtype == 2) {
        if (aptr->pair == NULL) {
            aptr_new->pair = NULL;
        } else {
            aptr_new->pair = (Pair *) malloc(sizeof(Pair));
            aptr_new->pair->left = copy_atom(aptr->pair->left);
            aptr_new->pair->right = copy_atom(aptr->pair->right);
        }
    } else if (aptr->dtype == 3) {
        if (aptr->lst==NULL) {
            aptr_new->lst = NULL;
        } else {
            aptr_new->lst = cons(head(aptr->lst), tail(aptr->lst));
        }
    }
    return aptr_new;
}

void print_atom(Atom *aptr)
{
    if (aptr==NULL) {
        printf("Empty");
        return;
    }
    switch (aptr->dtype) {
    case 0:
        printf("\"%s\"", aptr->str);
        break;
    case 1:
        printf("%d", aptr->val);
        break;
    case 2:
        print_pair(aptr->pair);
        break;
    case 3:
        print_list(aptr->lst);
        break;
    default:
        printf("Undefined.");
    }

}
/* Given an atom, create a list containing the atom. */
List* atom_to_list(Atom *a)
{
    List *b;
    b = (List*) malloc(sizeof(List));
    b->next = NULL;
    b->data = copy_atom(a);
    return b;
}

/* create a new list and add the atom to the head */
List* cons(Atom *a, List *b)
{
    List *c;

    c = atom_to_list(a);
    if (b!=NULL) {
        c->next = cons(head(b), tail(b));
    }

    return c;
}

void print_list(List *lptr)
{
    printf("[");
    while (lptr!=NULL) {
        print_atom(lptr->data);
        if (lptr->next != NULL)
            printf(",");
        lptr = lptr->next;
    }
    printf("]");
}

int len_helper(List *lptr, int len)
{
    if (lptr==NULL) return len;
    else return len_helper(lptr->next, len+1);
}
int length(List *lptr)
{
    return len_helper(lptr, 0);
}

void free_atom(Atom *aptr)
{
    if (aptr != NULL) {
        if (aptr->dtype==2) {
            free_pair(aptr->pair);
        } else if (aptr->dtype==3) {
            free_list(aptr->lst);
        }
        free(aptr);
    }
}

void free_list(List *lptr)
{
    List *p;
    if (lptr!=NULL) {
        p = tail(lptr);
        if (head(lptr)!=NULL) {
            free_atom(head(lptr));
        }
        free_list(p);
    }
}

Atom* head(List *lptr)
{
    return lptr->data;
}

List* tail(List *lptr)
{
    return (lptr==NULL) ? NULL : lptr->next;
}

/* create a new list combining a string list and a value list
If the two input lists have different lengths, the new list will be
of the same length as the shorter one.
*/
List* zip(List *lptr1, List *lptr2)
{
    Atom a;
    List *l1, *l2;

    if ( ??? ) { // lptr1 或 lptr2 兩者有一個是 NULL
        return NULL;
    } else {
        a.pair = ???; // malloc 取得一塊 Pair 空間
        a.pair->left = ???; // 利用  copy_atom  複製 lptr1 的開頭第一個 atom
        a.pair->right = ???; // 利用  copy_atom  複製 lptr2 的開頭第一個 atom
        a.dtype = 2;
        l1 = ??? // 利用 zip 處理剩下的 lists  (提示: 用遞迴)
        l2 = cons(&a, l1); // 利用 cons 造出新的 list
        free_pair(a.pair);
        free_list(l1);
        return l2;
    }
}

void print_pair(Pair *p)
{
    printf("(");
    print_atom(p->left);
    printf(",");
    print_atom(p->right);
    printf(")");
}

void free_pair(Pair* p)
{
    if (p!=NULL) {
        free_atom(p->left);
        free_atom(p->right);
        free(p);
    }
}