So basically it tries all possible combinations of words from a pool of characters, but without repeating them, so for "XYZ" it should give:
XYZ, XZY, YXZ, YZX, ZXY, ZYX
First, line 2 is completely unnecessary. You take the string and turn it into a list, but the list then stays unchanged. You also save the number of characters in that string/list in a separate variable.
Second, redefining variables like that (string to list) is somewhat niggerlicious. You're not gaining anything, you're not saving memory: when you calling the function from outside and pass the string into it, the string still exists in memory in the outer scope. If you really needed a list to fuck around with it, you should've named it something else.
(But you don't need a list, you only access the list `chars` once, in line 35, and that line works for the string exactly the same way.)
From a purely code quality standpoint, the pre-calculation part (huh?) can be rewritten as
Python:
cycles = [1]
combinations = 1
for i in range(1, len(chars) + 1):
combinations *= i
cycles.append(combinations)
numeric_string = list(range(len(chars)))
print(f"-- The number of combinations is {combinations} --\n")
or even
Python:
cycles = [1]
for i in range(1, len(chars) + 1):
cycles.append(cycles[-1] * i)
numeric_string = list(range(len(chars)))
print(f"-- The number of combinations is {cycles[-1]} --\n")
numeric_string isn't something you need to build dynamically, it's a list of integers from 0 to n-1 inclusive where n is length of input. Once you have your input, it's a constant completely independent from anything else that might be happening.
(It's possible to write it even nicer by using itertools and such, but if we're looking at itertools at all, might as well use the permutations from there; I think extending the scope of this particular learning problem to learning itertools BUT NOT PERMUTATIONS NUH UH is retardedly contrived.)
A bigger issue is this pre-calculation is somewhat cheaty and contrived. Once you've tasked yourself with a recursion learning problem, to restrict your options for the purpose of learning, you should use recursion to solve it! Instead, you're relying on a preexisting mathematical result
that you haven't yet earned within the scope of the problem. The factorial formula came from outside the program.
Making the matrix is
Python:
matrix = [[] for _ in range(len(chars))]
# assert matrix[0] is not matrix[1]
Surprisingly for python, this is not a footgun, the lists in the matrix are all different, not shallow views of a single list.
A questionable issue is you're not permuting a list consisting of the actual elements of the input but numeric_string, an artificial proxy for it, then convert it back for output. This is a weird choice. I'm not anywhere good enough at python to say what the drawbacks of permuting raw elements might be, but in most cases you can safely operate on the actual objects, knowing that no extra copies will be created. E.g. if you permute a list in which every item is an episode of
Galaxy Express 999 (minus the recap and the three tv specials) in blu-ray, each of the 113 episodes will only be stored in memory the one time, not
22311927486598136465966070212187151182564399087952213171022161345724023063584214692821047352118139068425569179220877461124773845924561575264739138192463311667200000000000000000000000000
times.
Anyway, I'll leave that part as it is for now, but this is how to convert the numeric output back into strings:
Python:
for batch in matrix:
print("".join(chars[idx] for idx in batch))
Backing up a step, sorting the matrix is not good. Here's why:
Python:
# this is a test
m = [tuple(reversed(x)) for x in matrix]
msort = sorted(m)
assert m == msort
Sorting imposes order on unsorted data. You have some data, you don't know what the fuck's in it, you need to sort it. Sorting is somewhat hard work, O(n log n) -- read up on algorithm speed later -- that the computer must perform.
But your worker function already produced a matrix in good order, as proven by my code.
In lieu of sorting, you can
Python:
for batch in matrix:
print("".join(chars[idx] for idx in reversed(batch)))
Going back to the internals of the worker function,
Python:
def rec(leftover_pool, times):
if times == 1:
matrix[0].append(leftover_pool[0])
return
for x in range(times):
hold = leftover_pool.pop(x)
matrix[times - 1].extend([hold] * cycles[times - 1])
rec(leftover_pool, times - 1)
leftover_pool.insert(x, hold)
this looks better. I replaced the internal loop that adds the element the specified number of times with an extend, took out the base (the times=1 branch) outside the loop where it would be prominent, and replaced the else with the return in the base branch so the business logic would be less tabbed.
And then apply
@Shalalallah Akbar 's point about times being superfluous:
Python:
def rec(pool):
if len(pool) == 1:
matrix[0].append(pool[0])
return
for x in range(len(pool)):
hold = pool.pop(x)
matrix[len(pool)].extend([hold] * cycles[len(pool)])
rec(pool)
pool.insert(x, hold)
rec(numeric_string)
Now the biggest problem is, while this is indeed recursion, you're not actually solving the real problem as stated, you're doing a weird trick to reproduce an external solution. You already know how many times you need to add a number to the matrix (the cycles array: 120 permutations to a list of 5, and 24 permutations to a list of 4), you did not get that part naturally from the recursion.
- instead of using this approach where you work out which character is at a particular position in every single permutation, you should use recursion to build up the permutations themselves, based on the principle that, permutation(string) = character + each permutation in permutation(rest of string), for each character in the string, with the base case of permutation(single letter) = single letter.
So let's rewrite the whole thing.
Python:
# the meta-alphabetic order is left as an exercise for the reader
def all_strings(chars):
if len(chars) == 1:
return [chars]
return [
"".join((s[:idx], chars[-1], s[idx:]))
for s in all_strings(chars[:-1])
for idx in range(len(s)+1)
]
if __name__ == "__main__":
pool = "ABCDE"
print(all_strings(pool))
4 lines lmao
