我有一个列表[1,2,3,4,5,6,7,8,9]
,我想获取由于将其元素成对分组和一个单独的列表而出现的所有列表,而不管成对的顺序如何。也就是说,我期望类似:
[[1,2],[3,4],[5,6],[7,8],[9]],
[[1,2],[3,4],[5,6],[7,9],[8]],
[[1,2],[3,4],[5,6],[8,9],[7]],
[[1,2],[3,4],[5,7],[6,8],[9]],
[[1,2],[3,4],[5,7],[6,9],[8]],
...
正如@abulafia 所指出的,在 9 个元素的情况下,列表的总数将是:
C(9,2) * C(7,2) * C(5,2) * C(3,2)
其中 C(n,m) 是从 m 到 m 取的 n 个元素的组合。结果有 22680 种可能性,与它所指示的 36 种相去甚远。
提前致以问候和感谢
组合比36多很多。
其实我得到22680。(更新这一切都是不正确的。确定的答案在“更新2”下。但是,我保留了原始答案,以便您可以看到它的过程得到了很好的答案)我花了很多钱才找到一个生成它们的算法,我不得不求助于递归。该算法仍然很难理解。现在,我给出了没有解释的代码和一个仅包含 5 个数字的列表的执行结果示例,该列表已经产生了 30 个案例。稍后解释。
代码
执行示例:
讨论结果
如您所见,如果您应用“5 个元素的组合 2 乘 2”的公式,出现的 30 个案例并不是您所期望的 10 个。也就是 2 in 2 的 5 个元素的组合确实是 10,这 10 个:
但这10个并不是全部。它们只是开始每个(30)个结果案例的 10 种可能方式。一旦我们选择了其中一个组合,例如 (1,2),列表的其余部分 (3,4,5) 我们可以再次从中获取 2 中的 2 组合(另外 3 种情况:(3 .4)、(3.5) 和 (4.5))。在这个列表有 5 个元素的示例中,这就是事情结束的地方,因为一旦选择了第二种情况之一,就只有一个可能的元素可供选择。
这就是这 30 个案例的来源。我们有 10 种可能的开始方式,每一种都有另外 3 种可能的继续方式。
在有 9 个数字的情况下,公式基本上变成:
作为 C(n,m) 从 m 到 m 取的 n 个元素的组合数。如果你做的数字出来:
这是我上面的代码实际产生的。
代码说明
该代码使用递归,基本上可以转换为:
该代码执行以下操作:
如果接收到的列表包含两个或更少元素,它只返回一个列表列表,其中包含一对元素(或单个元素)。例如,如果它接收到一个带有 [2,3] 作为参数的列表,它将返回
[[[2,3]]]
. 如果它接收到一个以 9 作为参数的列表,它将返回[[[9]]]
.如果你看,这个答案是正确的。它包含对作为参数接收的列表进行成对分组的所有方法。
否则,我们必须建立一个包含所有可能情况的列表。为了它:
itertools.combinations()
)开始我们的案例的所有可能方式(这是给定列表的所有组合,两个两个取其元素)只剩下编写知道如何解决子列表问题的“魔术”函数了。但是,多亏了递归的奇迹,我们已经有了那个函数,就是我们刚刚写的那个!
尽管它看起来不可思议(递归在我看来总是如此),但它确实有效。该函数只是调用自身。
更新
上面的代码生成的案例仅在连接顺序上有所不同。例如,上述输出包括:
为避免这种情况,您必须稍微修改代码。我不会把每一对都做成一个列表,而是把它做成一个元组。我们案例的不同之处在于元组可以放入集合中,而列表不能。因此,每个“案例”都可以简化为一个集合,并且在它们中顺序无关紧要,因此仅顺序不同的两个案例将产生相同的集合。如果这些集合不存在,我会将它们添加到结果中。
集合的一个问题是在显示它们时它们没有内部顺序,因此最终结果可能会显示类似 的情况
[(1,), (3,4), (2,5)]
,也就是说,“单独”元素不一定会出现在最后。为了避免这种“审美”细节,我保留了两个列表。一个正常结果(与初始解决方案相同)和另一个集合。我使用第二个只是为了避免将重复的案例放在第一个中。
这是新代码:
现在
[1,2,3,4,5]
只执行 15 个案例时:对于 9 位数字,事情已减少到 2235 例。但我无法告诉你这个数字的一般公式是什么(另一个挑战!该死!)
更新 2
前面的代码有一个错误(令我惊讶的是,9 个数字的最终组合数是 2235,因为它是 3x5x149,一个奇怪的素数三重奏,看起来一点也不好看,所以这不是很好的因素)。
如果我们为 case 生成组合列表
[4,5,6,7,8]
,而不是[1,2,3,4,5]
. 显然应该出现相同数量的组合(15),但是出现了 27 个。检查结果我发现出现“重复”的情况不应该是:这里的问题是 pair
(8,6)
被认为与 pair 不同(6,8)
,因此不同组合的集合实际上被认为是两个不同的有效组合。当我们将其用作输入时,该案例并未出现,
[1,2,3,4,5]
因为巧合的是,对于该案例,所有生成的元组都是按递增顺序排列的。也就是说,在每个生成的元组(x,y)
中,x<y
. 因此,(y,x)
同一个元组的版本从未出现过。这种行为可以被认为是意外。实际上,我们无法保证元组出现的顺序,因为当我们递归调用函数时,我们不再传递一个列表,而是一个集合(
set(elementos)-set(pareja)
)。itertools.combinations()
将遍历该集合的元素以生成对,但是集合不能保证它返回其元素的顺序,因此它可以将两者都作为第一(3,4)
对返回(4,3)
。[1,2,3,4,5]
按顺序随机生成元组的列表的意外行为也出现在其他列表中。但相反,它消失在[4,5,6,7,8]
开始看到无序元组的列表中,因此不被识别为重复。错误修复
为了让 tuple
(x,y)
被认为与 tuple 相同(y,x)
,最好停止使用 tuple 来表示组合,而使用集合。因此,显然,将所有出现的单词更改为 就足够
tuple()
了set()
。然而,这并不容易。问题:
set()
不能。并非所有 python 数据类型都可以是集合的成员。只有那些是可散列的(特别是不可变的)。这就是为什么我首先将列表更改为元组,这样我就可以将它们放入集合中。如果我把它改回set()
我不能再把它放在一个集合中,我需要识别重复的情况。set()
了frozenset()
。这是一种特殊类型的集合,无法添加或删除。也就是说,一个不可变的集合,因此是可散列的并且可以是其他集合的一部分。唯一的问题
frozenset()
是它使程序的输出非常脏,因为现在打印时可能会显示如下组合:而不是这样:
幸运的是,很容易定义您希望自己的类如何打印。在下面的代码中,我定义了我的类
MySet
,它继承自frozenset()
,但重新定义了方法__repr__()
,以便屏幕上的输出更加紧凑和可读。我在使用tuple()
.执行示例:
现在可以在输入为 的情况下正常工作
[4,5,6,7,8]
,产生 15 个组合而不是 27 个。而对于输入是
[1,2,3,4,5,6,7,8,9]
生成的组合数量的情况,只有 945 个(而不是 2235 个)。奖金
我找到了组合总数的公式。只需将最初计算的数字 (22680) 除以 4 (24) 的阶乘即可得到 945。这是因为在每种情况下都有 4 对,它们的顺序无关紧要,因此我们除以这 4 的排列数元素。
通用公式是除以每种情况下形成的对数的阶乘。即:
(有必要实现函数
C(n,m)
和factorial(n)
)我添加了另一个答案,因为在我看来,再次扩展前一个答案除了使它太长之外,还会使它更加混乱。
支持输入中的重复元素
在对上一个答案的评论中,用户(@Bugzilla)提到了输入列表可能有重复元素的可能性。这使情况变得相当复杂,因为虽然输入允许重复元素,但输出不应该允许重复组合,但这可能意味着的确切语义并不完全清楚。
例如,假设输入列表是出现在输入中的
[1,1,2,3]
那两个1
被认为是相等的吗?或者它们1
在某种意义上是“不同的”。如果它们不同,例如让我们用下标来区分它们,输入序列将是[1₁, 1₂, 2, 3]
,可能的组合将是:但由于实际上这两个表示相同,即 ,
1
输出将是:其中最后两个组合似乎相同。
如果上面的输出是有效的(有“明显”重复但“确实”不重复的组合,因为它们的某些元素“确实”不同,即使它们具有相同的表示),可以通过将数据保存在列表中来实现并使用该数据的索引来获取另一个列表。一旦获得索引对,它们将用于访问第一个列表中的“真实”数据。
但是,如果由于最后两个案例被认为是相同的,因此之前的输出不可接受,那么唯一有效的组合将是:
那么它仍然可以完成,但是用另一种方法。
另一种方法
该方法不是使用集合来保存每一对,而是返回使用元组的解决方案,并且也不使用集合递归地下降以“组合”列表的其余部分。特别是,我指的是这一行:
该行的想法是,一旦我们从原始列表中提取了一对,我们就递归地调用该函数,以便它为我们提供列表剩余内容的所有重组。由于考虑的对不必对应于 list 的前两个元素
elementos
,我们不能做类似elementos[2:]
获得“其余”的事情。所以我求助于集合算术,将原始列表变成一个集合,然后用提取的对减去子集。自然,只有当列表中没有重复元素时,该方法才能正确工作。否则,强制转换为 set 将使重复的元素消失。
但是我们仍然可以简单地通过复制原始副本并从副本中删除 (with
.remove()
) 考虑的对中的元素来构建子列表。代码有点长,但没有我担心的那么复杂。我们仍然可以使用集合来检测重复的情况,因为该集合的元素不再是原始列表的数字,而是我们一直在删除的元组。
Por otro lado, ya que no hacemos conversiones a conjuntos de la lista de entrada, tenemos garantizado el orden en que se recorrerán los elementos, de modo que si en un momento aparece la tupla
(x,y)
sabemos que no saldrá ya nunca la tupla(y,x)
, por lo que ese problema (que nos obligó a usar conjuntos en vez de tuplas) también desaparece.Solución
En resumen, creo que esta implementación hace por fin lo que se espera, incluso en el caso de que haya elementos repetidos en la lista de entrada:
Ejemplos de ejecución: