使用 for 循环时检查值是否重复的最有效方法是什么？

Question

我试图得到所有唯一的排列为下面的列表。收集所有元素，然后找到唯一元素是不可能的，因为这会导致电脑崩溃(我需要18个元素的组合)。为了解决这个问题，我试图在将值添加到列表或集合之前检查它是否唯一。仅仅对6或7的排列进行这样的处理已经证明需要很长时间，所以我现在设置的方法不适用于18。有没有更有效的方法?

pos = ['QB', 'QB', 'QB',
'RB', 'RB', 'RB', 'RB', 'RB', 'RB', 'RB', 'RB', 'RB', 'RB', 'RB',
'WR', 'WR', 'WR', 'WR', 'WR', 'WR', 'WR', 'WR', 'WR', 'WR', 'WR',
'TE', 'TE', 'TE', 'TE', 'TE']
combos = set()
for combo in itertools.permutations(pos, 18):
if combo not in combos:
combos.add(combo)

对于大小为6的排列，上面的运行大约需要40秒。18码不行

Answer 1

我找到了很多更好的算法，但仍然不确定它是最好的。我们可以使用树形结构，我们可以把所有不同的项目看作不同的树节点。我们将从一个空根开始，如果有的话，添加所有不同的树节点，直到它达到所需的长度。在这种情况下，我们有4个不同的树节点("QB", "RB", "WR", "TE")，所以我们的树将大致增长4**n，我们将存储路径信息，如果我们达到所需的长度，我们将添加路径。下面是我的解决方案:

from time import time
# We will store all paths as a list in this global variable list
all_paths = []

class TreeNode:
max_length_of_permutation = 6
def __init__(self,remaining_tree_dict,length,path):
self.remaining_tree_dict = remaining_tree_dict
self.length = length # Lentgh of root to this tree
self.path = path # Path of root to this tree
self.create_childs() 
def create_childs(self):
# We check if we reached the max length
if self.length < self.max_length_of_permutation:
#We will create all possible child trees
for tree in self.remaining_tree_dict:
# We will copy because wo don't want to change original remaining_tree_dict
new_remaining_tree_dict = self.remaining_tree_dict.copy()
# We update new_remaining_tree_dict by subtracting the tree we will create
new_remaining_tree_dict[tree] -= 1
# If we don't have this tree in new_remaining_tree_dict anymore, we will delete
if new_remaining_tree_dict[tree] == 0:
del new_remaining_tree_dict[tree]
# We are creating new tree node with updated remaining trees, length and path, No need to assign
TreeNode(new_remaining_tree_dict,self.length + 1,self.path + [tree])
# if we reach to max_length we add path to our global path variable
else:
all_paths.append(self.path)



initial_remaining_trees = {
'QB':3,
'RB':11,
'WR':11,
'TE':5,
}
cur_time = time()
# We create root tree with initial values
root = TreeNode(remaining_tree_dict = initial_remaining_trees, length = 0, path = [])
print(time() - cur_time)
print(all_paths)

所以如果我们设置max_length_of_permutation = 6，它真的很快。我尝试了稍微大一点的不同长度也用数学方法计算了排列的数量这是结果:

# 11 -> 2853248     num, 3.5 sec
# 12 -> 10048638    num, 11 sec
# 13 -> 34615984    num, 40 sec
# 14 -> 116607556   num, 242 sec
# 15 -> 384175688   num, ?
# 16 -> 1238482830  num, ?
# 17 -> 3908904792  num, ?
# 18 -> 12083761976 num, ?

所以我们可以估计需要几个小时来完成。我还计算出由于18的排列数是12083761976，在最佳算法中假设我们计算每个排列O(1)时间，将这些排列添加到列表中存储大约需要10分钟。所以不要期望非常快的算法

我希望这是有帮助的