我想两对一对地做两对。
一对由两个元素组成,一对由两个元素组成。
以下是约束列表:
在一对中,元素的顺序很重要:(element1,element2)!=(元素2,元素1)
在两对中,对的顺序并不重要:(pair1,pair2)=(pair2,pair1)
我编写了满足上述约束的伪代码,如下所示:
class Pair:
def __init__(self, element1, element2):
assert isinstance(element1, Element)
assert isinstance(element2, Element)
self.element1 = element1
self.element2 = element2
def __eq__(self, other):
if not isinstance(other, Pair):
return False
if self.element1 != other.element1:
return False
if self.element2 != other.element2:
return False
return True
def __ne__(self, other):
return not (self.__eq__(other))
def __hash__(self):
return hash(self.element1) ^ hash(self.element2)
def getFirst(self):
return self.element1
def getSecond(self):
return self.element2
class TwoPair:
def __init__(self, pair1, pair2):
assert isinstance(pair1, Pair)
assert isinstance(pair2, Pair)
self.pair1 = pair1
self.pair2 = pair2
def __eq__(self, other):
if not isinstance(other, TwoPair):
return False
if self.pair1 == other.pair1 and self.pair2 == other.pair2:
return True
if self.pair1 == other.pair2 and self.pair2 == other.pair1:
return True
return False
def __ne__(self, other):
return not (self.__eq__(other))
def __hash__(self):
return hash(self.pair1) ^ hash(self.pair2)
def getFirst(self):
return self.pair1
def getSecond(self):
return self.pair2
def makeTwoPairs(allPairs):
allTwoPairs = set([])
for pair1 in allPairs:
for pair2 in allPairs:
if pair1 == pair2:
continue
twoPair = TwoPair(pair1, pair2)
if twoPair in allTwoPairs:
continue
else:
allTwoPairs.add(twoPair)
return allTwoPairs
在我的代码中,
makeTwoPairs
函数需要很长时间两对有其他的代表吗或者,上面的代码可以改进吗? 最佳答案
您最好坚持使用标准的python数据结构tuple
用于Pair
和set
用于TwoPair
(尽管您可以编写set
子类来添加__hash__
方法)。
例如:
import operator
class TwoPairs(set):
def __hash__(self):
return reduce(operator.xor, map(hash, self))
考虑到
makeTwoPairs
函数需要很长时间才能执行,您可以这样重写它:def make_two_pairs(all_pairs):
all_two_pairs = set()
# uniqify the pairs list
all_pairs = list(set(all_pairs))
for i in range(len(all_pairs)-1):
for j in range(i+1, len(all_pairs)):
all_two_pairs.add(TwoPairs(all_pairs[i], all_pairs[j]))
return all_two_pairs
然后,您将只生成唯一的
TwoPairs
,而不必在向结果集添加新对之前进行组合爆炸或每次测试的开销。