How to make the code runs faster in Python (multiple nested for loops efficiency)-CodePudding

I have some codes here that I want to know if there's a way to make the code run better and take less time... I use multiple nested loops here and I don't really know how to improve this piece of code, so thanks for any help that you guys shared down here :)

from time import time

def mult_comb(combinations: list[tuple], T: list) -> None:
    for x in range(len(combinations)):
        for _ in range(len(T)):
            for j in range(len(T)):
                combinations.append(combinations[x]   (T[j], ))

def all_possible_combinations(T: list, r: int) -> list:
    combinations: list = []

    for i in range(len(T)):
        for j in range(len(T)): combinations.append((T[i], T[j]))

    for _ in range(r - 2): mult_comb(combinations, T)

    combs_result: set = set(combinations)
    final_combs_result = sorted(combs_result)
    return final_combs_result

if __name__ == "__main__":
    start: float = time()
    n, k = ['N', 'P'], 12

    data: list = all_possible_combinations(n, k)    
    print(data)
    print(f"The runtime took: {time() - start:.3f}s")

So, this code simply takes probability things, like this example... "One coin consists of two main body parts, showing the number of the coin and the picture of the coin (N represents the number, and P represents the picture). If I have 3 coins, then what's the probability of the coins of the samples?" (Sorry for my bad English...)

Basically, the answer is just: NN, NP, PN, PP, NNN, NNP, NPN, NPP, PNN, PNP, PPN, PPP.

The code already outputs the correct answer, but when I give the k value to 12, the code runs for about81.933s, which is took so much time considering this code only does simple things that our brain can even do this faster... Is there any ways to improve those nested loops? Thank you once again...

CodePudding user response：

you can create permutations like this

l = ['N', 'P']
k = 12

def perm(l, k):
    n, p = l
    res = ['N', 'P']
    prev_gen = (i for i in res)
    for i in range(1, k 1):
        res = (f'{j}{i}' for i in prev_gen for j in (n, p))
        prev_gen = res
    return res
print(list(perm(l,k)))

CodePudding user response：

IIUC you're trying to find all combinations of N and P for any given number of coins.

If that's the case then:

from itertools import combinations_with_replacement
from time import perf_counter

start = perf_counter()

for comb in combinations_with_replacement('NP', r=12):
    print(''.join(comb))

end = perf_counter()

print(f'Duration={end-start:.4f}')

Output:

NNNNNNNNNNNN
NNNNNNNNNNNP
NNNNNNNNNNPP
NNNNNNNNNPPP
NNNNNNNNPPPP
NNNNNNNPPPPP
NNNNNNPPPPPP
NNNNNPPPPPPP
NNNNPPPPPPPP
NNNPPPPPPPPP
NNPPPPPPPPPP
NPPPPPPPPPPP
PPPPPPPPPPPP
Duration=0.0001