python - 不重复映射算法问题

问题描述

问 题

新手，在写python100例的时候遇到这样一个问题：两个乒乓球队进行比赛，各出三人。甲队为a,b,c三人，乙队为x,y,z三人。已抽签决定比赛名单。有人向队员打听比赛的名单。a说他不和x比，c说他不和x,z比，请编程序找出三队赛手的名单。

题目本身不复杂，但是我想能不能写出一个通用的解决办法，也就是能不能构造成所有符合条件的映射，然后筛选，
所以，这个问题可以简化为A=[1,2,3,..],B=[1,2,3..],len(A)<=len(B),能否找到一个映射集合，使得里面A里面每个元素都对应B中一个元素，且每组中的元素互相不重复。
例如A=[1,2] B=[3,4],那么输出的答案为[[1,3],[2,4]],[[1,4],[2,3]]。

这个问题一开始觉得很简单，但是写起来却异常麻烦，也许因为我水平的原因，总而言之，没有太好的解法。

我想了两个解决办法，第一种办法用随机数来解决穷举的问题，然后把这个过程重复n次，然后去掉重复的组合，输出唯一解，这个方法我自己非常不满意，因为n的次数必须足够大才能保证答案的准确率，效率太低，这里就不放代码了，不太好意思。

第二种办法能解决问题，但是只限于len(A)=n，n比较小的情形，因为n每多一个就要定义一个数组，然后再套一层循环。代码如下：

#coding: UTF-8
#两个乒乓球队进行比赛，各出三人。甲队为a,b,c三人，乙队为x,y,z三人。已抽签决定比赛名单。
#有人向队员打听比赛的名单。a说他不和x比，c说他不和x,z比，请编程序找出三队赛手的名单

#下面的解法仍然无法扩充到A->B,len(A)=n的情形

f={1:"a",2:"b",3:"c"}
g={4:"x",5:"y",6:"z"}
s=[1,2,3]
t=[4,5,6]
p=[]
q1=[]
q2=[]
q3=[]

#穷尽所有的组合，然后筛选
for i in t:
    for j in s:
        p.append([i,j])
        if i==t[0]:
            q1.append([i,j])
        if i==t[1]:
            q2.append([i,j])
        if i==t[2]:
            q3.append([i,j])
print u"所有参与组合的list："
print p
print u"list分组："
print q1,q2,q3

w=[]
x=[]

for i1 in q1:
    for i2 in q2:
        for i3 in q3:
            w.append([i1,i2,i3])
#print w

'''用于观察w内部的数组
for i in w:
    for j in range(len(i)):
        print i[j]
    print"------------------------"
'''

for i in w:
    #print i
    u=[]
    v=[]
    for j in range(len(i)):
        u.append(i[j][1])
    if len(u)==len(s) and len(list(set(u)))==len(u):
        #print i
        x.append(i)
        #筛选题目要的结果
        if i[0][0]==1 and i[0][1]!=4 and i[2][0]==3 and i[2][1]!=4 and i[2][0]==3 and i[2][1]!=6:
            print u"题目答案："
            print i
   
print u"所有可能的结果："
print x


raw_input("Stop!")

大概问题就是这样，不知道这里能不能帮到我，有个思路就行，我可以自己研究写法

解决方案

# python 3
>>> from itertools import permutations
>>> a = ['a1', 'a2']
>>> b = ['b1', 'b2', 'b3']
>>> for c in (list(zip(a, p)) for p in permutations(b, len(a))):
...     print(c)
[('a1', 'b1'), ('a2', 'b2')]
[('a1', 'b1'), ('a2', 'b3')]
[('a1', 'b2'), ('a2', 'b1')]
[('a1', 'b2'), ('a2', 'b3')]
[('a1', 'b3'), ('a2', 'b1')]
[('a1', 'b3'), ('a2', 'b2')]

itertools 惠我良多!

---

我回答過的問題: Python-QA

这篇关于python - 不重复映射算法问题的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！