列表上的排列 nPr(5,3) 数量错误

Question

该程序的目标是对 x 进行尽可能多的排列，大小为 3 (nPr(5,3)，因此迭代 <代码>（i，j，k））。

我尝试实现排列 nPr(5,3)，其中 5 是列表 x 和 3 的长度 是元组 (i,j,k) 的长度：

# x will never have any repeats
x = [1, 2, 3, 4, 5]
# nPr(5,3) = 60
y = []


for i in x:
    for j in x:
        for k in x:
            y.append((i, j, k))

print(f"Len of y = {len(y)}")

我期望 len(y) 为 60，如 nPr( 5,3) = 60。但我得到输出Len of y = 125。另外，使用 y = set() 并不能解决这个问题

• 我做错了什么？
• 如何修复此代码以使其工作（不使用 itertools）

---

答案 TL;DR：我允许重复 (1,1 ,1)

Answer 1

您允许重复（例如，[1,1,1] 和 [2,2,2]）。值 60 用于无重复的排列。您可以通过检查是否没有重复某个值来做到这一点。

注意，此代码仅在 x 中没有重复的情况下才有效。如果存在重复项，则必须改用索引（即 for i in range(len(x)):）。

x = [1,2,3,4,5]
y = []
for i in x:
    for j in x:
        if i == j:
            continue
        for k in x:
            if i!=k and j!= k: 
                y.append((i,j,k))
print(y)

Answer 2

正如 Tim Roberts 所指出的，我添加了 i,j 或 k、(1,1,1) 的重复。我的解决方法是确保 i,j 和 k 不同：

for i in x:
    for j in x:
        for k in x:
            # If i,j,k are different
            if len(set((i, j, k))) == 3:
                y.append((i, j, k))

因为 set((i, j, k)) 将删除元组中的重复项 (i, j, k)，因此长度必须等于 3。如果我需要将 nPr(n,r) 递归为 set( (i,j,k...r)) == r。

Answer 3

这会起作用，尽管它对我来说嵌套得有点太深了：

y = []
for i in x:
    for j in x:
        if i != j:
            for k in x:
                if i != k and j != k:
                    y.append((i, j, k))

assert list(itertools.permutations(x, 3)) == y

否定条件并使用 continue 会增加可读性：

y = []
for i in x:
    for j in x:
        if i == j:
            continue
        for k in x:
            if i == k or j == k:
                continue
            y.append((i, j, k))

assert list(itertools.permutations(x, 3)) == y

但这只有在 x 的所有成员都是唯一的情况下才有效。更好的方法是检查索引是否不同：

y = []
for i in range(len(x)):
    for j in range(len(x)):
        if i == j:
            continue
        for k in range(len(x)):
            if i == k or j == k:
                continue
            y.append((x[i], x[j], x[k]))

assert list(itertools.permutations(x, 3)) == y

我们还可以通过递归来完成这项工作，在过程中参数化 r （每个排列中的项目数），尽管没有 动态编程，这种方法将为大型 x 做很多额外的工作，并且r：

# if x were hashable, i.e. a tuple in this case, we could use the
# @functools.cache decorator to avoid repeated work
def permutations(x, r):
    if not r:
        return [(),]
    res = []
    for i in range(len(x)):
        perms_without_x_i = permutations(x[:i] + x[i + 1 :], r - 1)
        res += [(x[i],) + p for p in perms_without_x_i]
    return res


assert permutations(x, 3) == list(itertools.permutations(x, 3))

但最好的方法可能是直接从 文档：

def permutations(iterable, r=None):
    # permutations('ABCD', 2) --> AB AC AD BA BC BD CA CB CD DA DB DC
    # permutations(range(3)) --> 012 021 102 120 201 210
    pool = tuple(iterable)
    n = len(pool)
    r = n if r is None else r
    if r > n:
        return
    indices = list(range(n))
    cycles = list(range(n, n-r, -1))
    yield tuple(pool[i] for i in indices[:r])
    while n:
        for i in reversed(range(r)):
            cycles[i] -= 1
            if cycles[i] == 0:
                indices[i:] = indices[i+1:] + indices[i:i+1]
                cycles[i] = n - i
            else:
                j = cycles[i]
                indices[i], indices[-j] = indices[-j], indices[i]
                yield tuple(pool[i] for i in indices[:r])
                break
        else:
            return