All permutations with known letter on one place

Question

Following code is doing what I want but I am looking for a way how to make it nicer and more effective

for i in c:
  for j in c:
    for k in c:
        for l in c:
            for m in c:                 
             if (i != j and i != k and i != l and j != k and j != l and k != l and i != m and j != m and k != m and l !=m):
                print i + j + 'u' + k + l + m

odusdi
odusdt
odusit
odusti
oduids
oduidt
oduist
oduits
odutds
odutdi
odutsi
...

I tried filters, lambdas and generators but that makes everything just worse.

I am new to python so I also have problems with copying and sending python code any hint with comment would be nice.

Answer 1

Usually, when you find yourself with multiple nested loops doing functionally the same thing, that's a good time to look for a solution using recursion, which are functions (you could indeed use generators) calling themselves.

So, you've got a list of characters c.
For the first letter, you pick from c.
For the second letter, you pick from c except that you can't choose the first letter.
For the third letter, likewise but letters 1 and 2 are banned.
And so on.

It should be clear that each of those is doing the same thing, it's just using a different set of allowed letters. That means you can use the same function for the job, and have it take as a parameter the letters that it's allowed to use.

---

There are two advantages to such a function over your implementation (although you could patch your version easily enough, it would involve writing even more duplicate code)

Firstly, at each step in my description, I rule out impossible options straight away. In your version, i and j will both be the first element of c straight away which is clearly a waste of time, but you don't check until you have looped through k, l, and m too. It would be better to move on to the next j as soon as it becomes clear that you can't use it. (And likewise with the others)

Secondly, your version is very specific to your input c. It's fine so long as c is exactly 5 long and only contains each letter once. If c contains any double letters you won't find any permutations at all. They'd all get swallowed up because python wouldn't know that they're meant to be different 'e's or whatever. Likewise if c was not 5 characters long, your code would not give a permutation. The recursive functional approach avoids both of those problems, and so is much more flexible.

---

Alternatively, as Peilonrayz suggests, look for the same code that someone else has written. itertools has permutations as well as combinations. The known letter thing is easy enough: you loop through permutations of the remaining characters, and for each one you print out the prefix, the 'u', and the suffix.

for perm in itertools.permutations(c):
    print (perm[0] + perm[1] + 'u' + perm[2] ...)

If you're a professional programmer, "use the library someone else wrote" is usually the best answer. It's just worth knowing the above so you can understand what's going on, including under the hood of the library function.

Answer 2

itertools.combinations does exactly what you want.