3

我有一个包含五个属性的列表,每个属性都有五个不同的值。我想生成它们的笛卡尔积并过滤所有独特的排列。

一些背景:

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

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...

也许一个简化的例子可以说清楚。

数据:

[['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)]]

也许您可以出于好奇告诉我,这些概念的具体数学名称是什么,我需要哪些?


谜题:

五个朋友(Dana、Ingo、Jessica、Sören、Valerie)在购物中心的收银台前排队等候。他们都是不同的年龄(26、27、30、33、35),想为自己购买不同的上衣(衬衫、Polo 衫、套头衫、运动衫、T 恤)。上衣有不同的颜色(蓝色、黄色、绿色、红色、黑色)和尺寸(XS、S、M、L、XL)

规则:

  1. “Dana”最想买的是“XL”。在她身后(但不是直接在后面)是一个穿着“黑色”上衣的人。
  2. “杰西卡”直接在一个想买“马球衫”的人面前等着。
  3. 排队的第二个人想买一件“黄色”上衣。
  4. “T 恤”不是“红色”。
  5. “Sören”想买一件“运动衫”。直接在他面前等候的人比他身后的人年长。
  6. 'Ingo' 需要一个尺寸为 'L' 的上衣。
  7. 排队的最后一个人是 30 岁。
  8. 最年长的人会购买尺寸最小的上衣。
  9. 直接在“Valerie”后面等候的人想买一件比“S”号大的“红色”上衣。
  10. 最年轻的人想买一件“黄色”上衣。
  11. 杰西卡要买一件“衬衫”。
  12. 第三个排队的人想买一件“M”号的上衣。
  13. “Poloshirt”是“红色”或“黄色”或“绿色”。
4

2 回答 2

2

这会做到,但需要很长时间。我减少了列表大小,因为您要求的选项有 24,883,200,000 个排列:

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')]
于 2019-05-24T01:28:45.873 回答
1

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

为了解决这些问题,我创建了一个名为 Puzzle Solvers 的项目:

这是一个小项目,目前包含一个感兴趣的类:puzzle_solvers.elimination.Solver. 此类实现了解决问题中提出的消除过程类型问题所需的大部分操作。所有逻辑都记录在案,并且本教程是您确切问题的演练。我将在这里解释基础知识,以便您了解我的所作所为,并可能对其进行改进。

第 1 步是识别队列中的位置是一个属性,就像年龄、姓名等一样。这意味着订单不再相关。

第 2 步是认识到这是一个变相的图问题。您有 30 个节点:五个个体中每个个体的所有可能属性(其中六个)。图表开始时几乎是完整的。仅缺少给定类型的属性之间的边,因此您从 375 条而不是完整的 435 条边开始。

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

那么如何去除边缘呢?像“'T 恤'不是'红色'”这样的简单规则非常简单:只需删除那个边缘。像“排队的最后一个人是 30 岁”这样的规则。也很简单,并且在去除边缘方面更有利可图。年龄不是 30 和位置 5 之间的所有边都被删除,以及位置不是 5 和年龄 30 之间的所有边缘。我添加了几个半生不熟的实用程序包装器来检查大于和小于条件和删除代表不可能组合的边。

求解器最重要的方面是,只要删除一条边,它就会完全遵循该操作的所有逻辑含义。想象一下,你有“‘Poloshirt’是‘红色’或‘黄色’或‘绿色’”,并且你在谜题中达到了一个点,这三种颜色都与 30 岁无关。这意味着无论是谁穿马球衫不能30岁。事实上,'Poloshirt' 不能有任何边缘与这三种颜色不共享的端点。如果你递归地遵循这些推论,你就会得到一个完整的解决方案。

我为我的包裹的无耻销售感到抱歉,但出于正当理由,我写它只是为了回答这个问题。

于 2019-05-30T21:09:42.453 回答