[C_MM45-中] 分禮物

成績: 0 / 倒扣: 0.8

問題描述 ：
每年的耶誕節，都會有交換禮物的活動。現在有一群人，要交換彼此的禮物，但是每個人都不能拿到自己準備的禮物，且每個人都只有會拿到一件禮物，請問共有幾種情形，並把所有可能情形印出來。

輸入說明 ：
第一列輸入一個正整數n ( n ≤ 6 ) 。其後有n列，每一列代表每個人，每一列之資料依序為人名、禮物名。請注意人名與禮物名為英文字母。
輸出說明 ：
第一列顯示出可以有k種資料，其後顯示k組解列，其資料按照原本人名輸入的順序排列，即人名和禮物名視為同一組，一列中會有很多組，組與組間用逗號區分，用人名與禮物名用空白分隔。
範例 ：

Sample Input:	Sample Output:
3 A1 GIFT1 B1 GIFT2 C1 GIFT3	2 A1 GIFT2,B1 GIFT3,C1 GIFT1 A1 GIFT3,B1 GIFT1,C1 GIFT2

while True:
    try:
        def rot(data, n):           # 將第n個搬到最後
            val = data.pop(n)
            data.append(val)
            return data

        def rot_n_chk(data, n):     # 檢查第n個要不要搬
            for i in range(n-1):
                if data[i] == i:
                    rot(data, i+1)
                else:
                    break
            return data

        def chk_stop(data, n):      # 檢查所有的位置是否都歸位
            res = 1
            for i in range(n):      # 只要第i位置對 chk=1, 位置不對 chk=0
                chk=1 if data[i] == i else 0
                res *= chk          # 每位的乘積
            return res              # res乘積為1表示全歸位都輪完了
        
        n = int(input())
        Name, Gift, r = [], [], []
        for i in range(n):
            name, gift = map(str,input().split())
            Name.append(name)
            Gift.append(gift)
        
        data = [i for i in range(n)] # 預備產生個種排列 [0, 1, 2]
        while True:
            rot(data, 0)
            rot_n_chk(data, n)
            b = data[:]
            chr = 0 # 當有新排列時，檢查篩選出不在自已位置上的排列例如[1, 2, 0] 
            for i in range(n):
                if b[i] != i:chr += 1 # 位置不在位置上就 +1
            if chr == n:r.append(b) # chr = 排列的長度表示各個位置都錯開了再加入結果 r[]
            if chk_stop(data, n):break
        x = sorted(r)
        print(len(x))
        for i in range(len(x)):
            ws = ''
            for j in range(len(Name)):
                ws += Name[j] + ' '+Gift[x[i][j]]+','
            print(ws.rstrip(','))    
    except(EOFError):
        break