时间戳

首页 > 解决方案 > 为在它们之间交换的每个索引生成列表组合的算法

algorithm - 为在它们之间交换的每个索引生成列表组合的算法

问题描述

我有两个列表，N每个列表都有元素。

让N = 9：

[a1, b1, c1, d1, e1, f1, g1, h1, i1]
[a2, b2, c2, d2, e2, f2, g2, h2, i2]

让我们交换每个列表的第一个元素。有两种可能：

[a1, b1, c1, d1, e1, f1, g1, h1, i1]
[a2, b2, c2, d2, e2, f2, g2, h2, i2]

[a2, b1, c1, d1, e1, f1, g1, h1, i1]
[a1, b2, c2, d2, e2, f2, g2, h2, i2]

对于每种可能性，让我们交换每个列表的第二个元素。有四种可能：

[a1, b1, c1, d1, e1, f1, g1, h1, i1]
[a2, b2, c2, d2, e2, f2, g2, h2, i2]

[a2, b1, c1, d1, e1, f1, g1, h1, i1]
[a1, b2, c2, d2, e2, f2, g2, h2, i2]

[a1, b2, c1, d1, e1, f1, g1, h1, i1]
[a2, b1, c2, d2, e2, f2, g2, h2, i2]

[a2, b2, c1, d1, e1, f1, g1, h1, i1]
[a1, b1, c2, d2, e2, f2, g2, h2, i2]

等等。

为 2 个列表和列表生成所有组合的最快算法是什么M？
这个特定过程的名称是什么？
给出的组合总数是多少M, N？

标签： algorithmlistmathcombinations

解决方案

由于对于新形成的列表 L1 的每个位置，可以从第一个或第二个列表中选择一个元素，因此每个位置都有两个选项。对应的第二个列表 L2 将通过获取未选择的元素来形成，这只能以一种方式完成。因此，存在2^N组合，其中N是原始列表的长度。

使用这种思想，很容易使用2^N二进制掩码编写生成器 - 对于每个ifrom0到，2^N - 1我们将生成一个由该数字的二进制表示确定的列表。这是一个python代码：

a = ['a1', 'b1', 'c1']
b = ['a2', 'b2', 'c2']
for i in range(2 ** len(a)):
  l1, l2 = [], []
  mask = i
  for j in range(len(a)):
    l1.append(a[j] if mask % 2 == 0 else b[j])
    l2.append(b[j] if mask % 2 == 0 else a[j])
    mask /= 2
  print(l1, l2)

印刷

(['a1', 'b1', 'c1'], ['a2', 'b2', 'c2'])
(['a2', 'b1', 'c1'], ['a1', 'b2', 'c2'])
(['a1', 'b2', 'c1'], ['a2', 'b1', 'c2'])
(['a2', 'b2', 'c1'], ['a1', 'b1', 'c2'])
(['a1', 'b1', 'c2'], ['a2', 'b2', 'c1'])
(['a2', 'b1', 'c2'], ['a1', 'b2', 'c1'])
(['a1', 'b2', 'c2'], ['a2', 'b1', 'c1'])
(['a2', 'b2', 'c2'], ['a1', 'b1', 'c1'])

由于输出大小是O(N * 2^N)您无法制作比这更好的算法。

推荐阅读