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

The goal of this program is to make as many permutations of x in size 3 (nPr(5,3), hence the iterations of (i, j, k)).

My effort on trying to achieve the permutations nPr(5,3), where 5 is the length of the list x and 3 is the length of the tuple (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)}")

I'm expecting len(y) to be 60, as nPr(5,3) = 60. But i get the output Len of y = 125. Also, making y = set() does not fix this issue

What have I done wrong?
How do I fix this code to work (without using itertools)

Answer TL;DR: I was allowing duplicates (1,1,1)

CodePudding user response：

You are allowing repeats (for example, [1,1,1] and [2,2,2]). The value of 60 is for permutations without repeats. You do that by checking that you aren't repeating a value.

NOTE that this code only works if there are no repeats in x. If there are duplicates, then you would have to use indexes instead (that is, 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)

CodePudding user response：

As pointed out by Tim Roberts, I was adding repeats of i,j or k, (1,1,1). My fix is to just make sure i,j and k are different:

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))

As set((i, j, k)) will remove the duplicates in the tuple (i, j, k), so the length must equal 3. This is also helpful if I need to make this recursive for nPr(n,r) as set((i, j, k ... r)) == r.

CodePudding user response：

This will work, though it's a bit too deeply nested for my taste:

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

Note this will only work if all members of x are unique. Better would be to check that the indices are different:

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

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

This does the job with recursion, though without dynamic programming, it's going to do a lot of extra work for large x and 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))

But probably the best way of all is to steal the answer directly from 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