Duplicates end up in list despite "if statement"

Question

Okay, I was working on a code that would give every possible combination of the scrambled letters you input. Here it is:

import random, math

words = []
original = raw_input("What do you need scrambled? ")

def word_scramble(scrambled):

    original_length = len(scrambled)
    loops = math.factorial(original_length)

    while loops > 0:
        new_word = []

        used_numbers = []

        while len(new_word) < original_length:

            number = random.randint(0, original_length - 1)

            while number in used_numbers:
                number = random.randint(0, original_length - 1)

            while number not in used_numbers:
                used_numbers.append(number)
                new_word.append(scrambled[number])

        if new_word not in words:
            words.append(("".join(str(x) for x in new_word)))
            loops -= 1

word_scramble(original)

print ("\n".join(str(x) for x in words))

The problem is, it still gives duplicates, even though it isn't supposed to. For instance, I can input "imlk" and will sometimes get "milk" twice, while still only giving me 24 permutations, meaning some permutations are being excluded. The:

if new_word not in words:
    words.append(("".join(str(x) for x in new_word)))
    loops -= 1

is supposed to prevent duplicates from being in the list. So I'm not really sure what the issue is. And sorry that the main title of the question was so vague/weird. I wasn't really sure how to phrase it better.

Answer 1

How about itertools.permutations?

import itertools
original = raw_input("What do you need scrambled? ")
result = [''.join(s) for s in itertools.permutations(original)]

Answer 2

if new_word not in words:
    words.append(("".join(str(x) for x in new_word)))
    loops -= 1

new_word is a list of letters, but words contains strings not lists of letters. They're in different formats, so the check will always succeed.

For instance, you might get the check:

if ['m', 'i', 'l', 'k'] not in ['imlk', 'milk', 'klim']

rather than

if 'milk' not in ['imlk', 'milk', 'klim']

By the way, your algorithm is going to scale very badly the more letters it needs to scramble. It relies upon randomly stumbling upon unused words, which is fast at first, but slow the more words are used.

You'll be better off if you can figure out a way to enumerate the permutations in a predictable order without guessing.