列表中错误的排列数 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）

回答长话短说：我允许重复 (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（每个排列中的项目数），尽管没有 dynamic programming，这种方法将为大 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))

但可能最好的方法是直接从 the docs:

窃取答案

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 Roberts 所指出的，我添加了 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.

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

Wrong number of permutations nPr(5,3) on a list

python

permutation

python-3.x