列表上的排列错误数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。而且，making y = set()并不能解决这个问题。

• 我做错了什么？
• 如何修复此代码(不使用itertools)

回答TL博士:我允许重复的(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

这是可行的，尽管它对我的口味来说嵌套得太深了：

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

Answer 3

正如蒂姆·罗伯茨( Tim )指出的，我在添加i,j or k，(1,1,1)的重复。我的解决办法是确保i,j and 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，这也很有帮助。