有没有一种方法可以生成一系列项目的所有唯一排列

Question

我有五个属性的列表，每个属性有五个不同的值。我要生成它们的笛卡尔积并过滤所有唯一的置换。在

一些背景：

我需要它们作为我的输入值来解决一个逻辑难题。在那里我会检查规则以找到正确的解决方案。在

from itertools import product

# input
names = ['Dana', 'Ingo', 'Jessica', 'Sören', 'Valerie']
ages = [26, 27, 30, 33, 35]
tops = ['Blouse', 'Poloshirt', 'Pullover', 'Sweatshirt', 'T-Shirt']
colors = ['blue', 'yellow', 'green', 'red', 'black']
sizes = ['XS', 'S', 'M', 'L', 'XL']

all_attributes = [names, ages, tops, colors, sizes]

# cartesian product (superset)
inputs = list(product(*all_attributes))

# the following code you do that...

也许一个简单的例子就能说明问题。在

数据：

^{pr2}$

数据的笛卡尔积：

[('Dana', 26), ('Dana', 27), ('Ingo', 26), ('Ingo', 27)]

我想要的：

[[('Dana', 26), ('Ingo', 27)],
 [('Dana', 27), ('Ingo', 26)],
 [('Ingo', 26), ('Dana', 27)],
 [('Ingo', 27), ('Dana', 26)]]

我不想要的是：

[[('Dana', 26), ('Ingo', 26)], ...

我不想要相同值的多次出现。位置很重要，所以它应该具有置换特性，对于一个包含五个元素的列表来说，它应该具有置换特性。我想输出的大小将是巨大的，也许这是不可能计算的，所以最好指定一些固定的位值。例如，我想将“Dana”设置为第一个元素名。在

输出：

[[('Dana', 26), ('Ingo', 27),
 [('Dana', 27), ('Ingo', 26)]]

也许出于好奇，你可以告诉我，这些概念的具体数学名称是什么，我需要这些名称？在

---

谜题：

在购物中心有五个朋友在排队。他们都是不同年龄段的人（26、27、30、33、35），想为自己购买不同的上衣（衬衫、马球衫、套头衫、运动衫、T恤）。顶部有不同的颜色（蓝色、黄色、绿色、红色、黑色）和尺寸（XS、S、M、L、XL）。在

规则：

1. “达娜”最想买的是“XL”。在她身后（但不是正后方）是一个戴着“黑色”上衣的人。在
2. “杰西卡”就在一个想买“马球衫”的人面前等着。在
3. 第二个排队的人想买一件黄色的上衣。在
4. “T恤”不是“红色”。在
5. “Sören”想买一件“运动衫”。直接在他前面等的人比他后面的人年长。在
6. “Ingo”需要一个L码的上衣。在
7. 最后一个排队的人是30岁。在
8. 年纪最大的人要买最小尺寸的上衣。在
9. 坐在“瓦莱丽”后面的人想买一件比尺码大的“红色”上衣。在
10. 最年轻的人想买一件黄色的上衣。在
11. 杰西卡要买件“衬衫”。在
12. 排队的第三个人想买一件M码的上衣。在
13. “马球衫”是“红”或“黄”或“绿”。在

Answer 1

这可以，但需要很长时间。我缩小了列表的大小，因为您所要求的选项有2488320000个排列：

from itertools import permutations, product

names = ['Dana', 'Ingo']
ages = [26, 27]
tops = ['Hemd', 'Poloshirt']
colors = ['blau', 'gelb']
sizes = ['XS', 'S']

options = []

# Generate the Cartesian product of all permutations of the options.
for name,age,top,color,size in product(*map(permutations,[names,ages,tops,colors,sizes])):
    # Build the option list. zip() transposes the individual lists.
    option = list(zip(name,age,top,color,size))
    options.append(option)
    print(option)

输出：

^{pr2}$

Answer 2

对于你所遇到的逻辑难题，使用置换的方法有一个基本问题。问题不在于它们太多，以至于你的解算器不可能在合理的时间内完成。问题是你没有一种自动的方法来检查规则是否存在问题：除非你有一种方法来验证它们，否则把所有的可能性摆在面前是毫无意义的。在

为了解决这些问题，我创建了一个名为谜题求解器的项目：

• https://github.com/madphysicist/puzzle-solvers
• https://pypi.org/project/puzzle-solvers/
• https://puzzle-solvers.readthedocs.io/en/latest/

这是一个小项目，目前只包含一个感兴趣的类：^{}。这个类实现了解决问题中出现的消除型问题所需的大多数操作。所有的逻辑都是documented，而tutorial则是您确切问题的演练。我将在这里解释基础知识，这样你就可以理解我做了什么，也许还能改进它。在

步骤1是识别队列中的位置是一个属性，就像年龄、姓名等一样，这意味着顺序不再相关。在

第二步是认识到这是一个伪装的图形问题。你有30个节点：5个个体的所有可能属性（其中6个）。这张图一开始几乎完成了。只缺少给定类型属性之间的边，因此从375个边开始，而不是435个完整的边。在

最终目标是在图中五个连接的组件中的每个属性类之间有一条边。因此，最终的边数为5*15=75。在

那么如何去除边缘呢？简单的规则，比如“T恤衫”不是“red”，很简单：只要去掉那个边。像“最后一个排队的人是30岁”这样的规则也很简单，而且从边缘去除的角度来看更有利可图。将删除年龄不在30岁和位置5之间的所有边，以及不在5岁和30岁之间的所有边。我添加了两个半生不熟的实用程序包装器来检查大于和小于条件，并删除表示不可能组合的边。在

解算器最重要的方面是，任何时候移除一条边，它都会完全遵循该操作的逻辑含义。想象一下你有“马球衫是红色、黄色或绿色”，并且你已经在你的谜题中找到了一个与30岁年龄无关的点。这意味着穿马球衫的人不可能是30岁。事实上，这三种颜色都不能与任何颜色的衬衫共享。如果你递归地遵循这些推论，你会得到一个完整的解决方案。在

我为无耻地出售我的包裹感到抱歉，但为了辩护，我写这封信只是为了回答这个问题。在