program takes long time to calculate........recursion(python)

Question

my program takes long time to look up all the list of the vocab in the file in order to print all the possible words that can be created. How can i make it read more faster by not using any import? I'm new to python by the way :( For example, i have more than 4000+ vocabs/letters/words contain in 1 file if you enter any letter, it will find all possible outcome in that file.

if the user enter: a c t b

it will display: (assuming all these 3 letters/words out of 4000+ are in that file that can be created)

ab
abc
act

here is my program

def scramble(r_letters, s_letters):
    """
    Output every possible combination of a word.
    Each recursive call moves a letter from
    r_letters (remaining letters) to
    s_letters (scrambled letters)
    """
    if len(r_letters) == 0:  # Base case: All letters used
        words.add(s_letters)
    else:  # Recursive case: For each call to scramble()
           # move a letter from remaining to scrambled
        for i in range(len(r_letters)):
            # Move letter to scrambled
            tmp = r_letters[i]
            r_letters = r_letters[:i] + r_letters[i+1:]
            s_letters += tmp

            scramble(r_letters, s_letters)

            # Put letter back in remaining letters
            r_letters = r_letters[:i] + tmp + r_letters[i:]
            s_letters = s_letters[:-1]
        if s_letters:
             words.add(s_letters)

What exactly is the program supposed to do? Get all the "real" words from a file that can be obtained by "scrambling" some letters? Like the words you can create with your letters in "Scrabble"? — tobias_k
– tobias_k, Commented Jun 2, 2015 at 7:43
yes,.it will try to display all the possible words (if those words are in the file) that can be created from the given letters. — Besttee
– Besttee, Commented Jun 2, 2015 at 7:48

tobias_k · Accepted Answer · 2015-06-02 09:29:26Z

1

It seems you want to generate all the permutations that can be created from the given letters and then check whether those correspond to any "real" word from some dictionary, kind of like for looking up what words can be created in a game of Scrabble.

You can make your scramble function a bit faster (and a whole lot shorter) by just swapping the letters in the arguments to the recursive call. This way, you do not have to swap them back:

def scramble(r_letters, s_letters):
    if s_letters:
        words.add(s_letters)
    for i in range(len(r_letters)):
        scramble(r_letters[:i] + r_letters[i+1:], s_letters + r_letters[i])

You could also use itertools.permutations for this, e.g. like this, generating all the permutations for different word length using the given letters:

def scramble2(letters):
    for i in range(1, len(letters) + 1):
        for p in itertools.permutations(letters, i):
            words.add(''.join(p))

According to IPython's %timeit, this is about three times faster than your implementation:

In [3]: %timeit test.scramble("test", "")
10000 loops, best of 3: 50.4 µs per loop
In [4]: %timeit test.scramble2("test")
100000 loops, best of 3: 16.7 µs per loop

However, you do not need to generate all the permutations at all! Just count the letters in the words and compare them to the counts of the letters you have available. You can use collections.Counter for this, or create your own counter-like dictionary.

import collections
letters = "abctk"
words = "cat back track tact".split()
letter_counts = collections.Counter(letters)
for word in words:
    word_counts = collections.Counter(word)
    if all(letter_counts.get(c, 0) >= n for c, n in word_counts.iteritems()):
        print word

This will print "cat" and "back"

If you want to avoid using libraries (okay for practicing, but don't stick to this habit) you can create your own counter, e.g. like this:

def count(word):
    d = {}
    for c in word:
        d[c] = d.get(c, 0) + 1
    return d

edited Jun 2, 2015 at 9:29

answered Jun 2, 2015 at 7:56

tobias_k

83.1k12 gold badges130 silver badges186 bronze badges

Sign up to request clarification or add additional context in comments.

4 Comments

Besttee Over a year ago

is it possible to not using any import? here is my full code mediafire.com/view/v1w408w18qazpbd/bbbbb.py

Łukasz Rogalski Over a year ago

@Besttee collections and itertools is built-in, highly optimized (implemented in C) modules to perform kind of operations, which suits your purpose perfectly. Why you do not want to use them?

Besttee Over a year ago

because I'm practicing on recursion, and trying to get the solid on it

tobias_k Over a year ago

@Besttee I understand that, and there might be some potential for improvement in your function (have not looked at it too much yet). Still, I think that generating all the permutations is not the right way to solve the problem in the first place.

Collectives™ on Stack Overflow

program takes long time to calculate........recursion(python)

1 Answer 1

4 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

4 Comments

Your Answer

Sign up or log in

Post as a guest

Related