有没有一种方法来生成项目列表的所有唯一排列

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 (superhtml" target="_blank">set)
inputs = list(product(*all_attributes))

# the following code you do that...

也许一个简化的例子就能说清楚。

数据：

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

数据的笛卡尔乘积：

[('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)，想为自己购买不同的上衣（衬衫、Polo恤、套头衫、运动衫、t恤）。顶部有不同的颜色（蓝色，黄色，绿色，红色，黑色）和尺寸（XS，S，M，L，XL）。

1. “达娜”最想买的是“XL”。在她身后（但不是正后方）是一个穿着“黑色”上衣的人

Answer 1

对于你所拥有的逻辑谜题类型，使用排列的方法存在一个基本问题。问题甚至不在于它们太多，以至于你的求解器不太可能在合理的时间内完成。问题是，你没有一种自动化的方法来检查规则和问题：除非你有一种方法来验证它们，否则所有的可能性都摆在你面前是毫无意义的。

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

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

这是一个小项目，目前只包含一个感兴趣的类：puzzle\u解算器。消除解算器。此类实现了解决问题中提出的消除过程类型问题所需的大多数操作。所有的逻辑都有文档记录，本教程是对您的确切问题的演练。我将在这里解释基本知识，以便您了解我所做的工作，并可能对其进行改进。

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

第二步是认识到这是一个伪装的图形问题。您有30个节点：五个个体的所有可能属性（其中六个）。图表开始时几乎是完整的。只有给定类型的属性之间的边丢失，所以您从375条而不是完整的435条边开始。

最终目标是在图中的五个连通分支中的每类属性之间有一条边。最终的边数因此5 * 15 = 75。

那么如何去除边缘呢？像“T恤衫不是红色”这样的简单规则非常简单：只需去除边缘即可。比如“排队的最后一个人是30岁。”也很简单，而且在去除边缘方面更有利可图。将删除年龄不到30岁和位置5之间的所有边，以及年龄不到5岁和位置30之间的所有边。我添加了两个半生不熟的工具包装，以检查大于和小于条件，并删除表示不可能的组合的边。

求解器最重要的方面是，任何时候边缘被移除，它都完全遵循该操作的所有逻辑含义。想象一下，你有“一件‘波洛衫’是‘红色’、‘黄色’或‘绿色’”，你已经到了一个难题的地步，这三种颜色都与30岁无关。这意味着无论是谁穿的polo恤都不可能是30岁。事实上，“波洛衬衫”不能有任何endpoint不被这三种颜色共享的边缘。如果你递归地遵循这些推论，你会得到一个完整的解决方案。

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

Answer 2

这样就可以了，但需要很长时间。我减小了列表大小，因为您请求的选项有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)

输出：

[('Dana', 26, 'Hemd', 'blau', 'XS'), ('Ingo', 27, 'Poloshirt', 'gelb', 'S')]
[('Dana', 26, 'Hemd', 'blau', 'S'), ('Ingo', 27, 'Poloshirt', 'gelb', 'XS')]
[('Dana', 26, 'Hemd', 'gelb', 'XS'), ('Ingo', 27, 'Poloshirt', 'blau', 'S')]
[('Dana', 26, 'Hemd', 'gelb', 'S'), ('Ingo', 27, 'Poloshirt', 'blau', 'XS')]
[('Dana', 26, 'Poloshirt', 'blau', 'XS'), ('Ingo', 27, 'Hemd', 'gelb', 'S')]
[('Dana', 26, 'Poloshirt', 'blau', 'S'), ('Ingo', 27, 'Hemd', 'gelb', 'XS')]
[('Dana', 26, 'Poloshirt', 'gelb', 'XS'), ('Ingo', 27, 'Hemd', 'blau', 'S')]
[('Dana', 26, 'Poloshirt', 'gelb', 'S'), ('Ingo', 27, 'Hemd', 'blau', 'XS')]
[('Dana', 27, 'Hemd', 'blau', 'XS'), ('Ingo', 26, 'Poloshirt', 'gelb', 'S')]
[('Dana', 27, 'Hemd', 'blau', 'S'), ('Ingo', 26, 'Poloshirt', 'gelb', 'XS')]
[('Dana', 27, 'Hemd', 'gelb', 'XS'), ('Ingo', 26, 'Poloshirt', 'blau', 'S')]
[('Dana', 27, 'Hemd', 'gelb', 'S'), ('Ingo', 26, 'Poloshirt', 'blau', 'XS')]
[('Dana', 27, 'Poloshirt', 'blau', 'XS'), ('Ingo', 26, 'Hemd', 'gelb', 'S')]
[('Dana', 27, 'Poloshirt', 'blau', 'S'), ('Ingo', 26, 'Hemd', 'gelb', 'XS')]
[('Dana', 27, 'Poloshirt', 'gelb', 'XS'), ('Ingo', 26, 'Hemd', 'blau', 'S')]
[('Dana', 27, 'Poloshirt', 'gelb', 'S'), ('Ingo', 26, 'Hemd', 'blau', 'XS')]
[('Ingo', 26, 'Hemd', 'blau', 'XS'), ('Dana', 27, 'Poloshirt', 'gelb', 'S')]
[('Ingo', 26, 'Hemd', 'blau', 'S'), ('Dana', 27, 'Poloshirt', 'gelb', 'XS')]
[('Ingo', 26, 'Hemd', 'gelb', 'XS'), ('Dana', 27, 'Poloshirt', 'blau', 'S')]
[('Ingo', 26, 'Hemd', 'gelb', 'S'), ('Dana', 27, 'Poloshirt', 'blau', 'XS')]
[('Ingo', 26, 'Poloshirt', 'blau', 'XS'), ('Dana', 27, 'Hemd', 'gelb', 'S')]
[('Ingo', 26, 'Poloshirt', 'blau', 'S'), ('Dana', 27, 'Hemd', 'gelb', 'XS')]
[('Ingo', 26, 'Poloshirt', 'gelb', 'XS'), ('Dana', 27, 'Hemd', 'blau', 'S')]
[('Ingo', 26, 'Poloshirt', 'gelb', 'S'), ('Dana', 27, 'Hemd', 'blau', 'XS')]
[('Ingo', 27, 'Hemd', 'blau', 'XS'), ('Dana', 26, 'Poloshirt', 'gelb', 'S')]
[('Ingo', 27, 'Hemd', 'blau', 'S'), ('Dana', 26, 'Poloshirt', 'gelb', 'XS')]
[('Ingo', 27, 'Hemd', 'gelb', 'XS'), ('Dana', 26, 'Poloshirt', 'blau', 'S')]
[('Ingo', 27, 'Hemd', 'gelb', 'S'), ('Dana', 26, 'Poloshirt', 'blau', 'XS')]
[('Ingo', 27, 'Poloshirt', 'blau', 'XS'), ('Dana', 26, 'Hemd', 'gelb', 'S')]
[('Ingo', 27, 'Poloshirt', 'blau', 'S'), ('Dana', 26, 'Hemd', 'gelb', 'XS')]
[('Ingo', 27, 'Poloshirt', 'gelb', 'XS'), ('Dana', 26, 'Hemd', 'blau', 'S')]
[('Ingo', 27, 'Poloshirt', 'gelb', 'S'), ('Dana', 26, 'Hemd', 'blau', 'XS')]