2
\$\begingroup\$

I just watched the video from "Think Like a Programmer, Episode 2: Puzzles & Problems".

The problem is:

Assign number 1-7 to three departments in a city: Fire, Police, Sanitation.

Requirement:

  • Each department should have a unique number
  • Police should be an even number
  • Fire + Police + Sanitation = 12

Generate a list of permutations for these department numbers.

Here is my Python attempt:

def valid_department_number(f, p, s):
    if (f != p != s) and (f+p+s == 12) and p % 2 == 0:
        return True
    else:
        return False

numbers = range(1, 8)

for f in numbers:
    for p in numbers:
        for s in numbers:
            if valid_department_number(f, p, s):
                print(f, p, s)

I searched the python documentation and found that I could use the permutations function from itertools:

import itertools


all_permutations = list(itertools.permutations(numbers, 3))

for each_p in all_permutations:
    f, p, s = each_p[0], each_p[1], each_p[2]
    if valid_department_number(f, p, s):
        print(each_p)

The permutation function gets rid of three levels of nested for loops. I'm wondering whether there's a better way to deconstruct the tuples from permutation generated list of tuples.

\$\endgroup\$
1
\$\begingroup\$

One of the contracts of itertools.permutations is:

So if the input elements are unique, there will be no repeat values in each permutation.

So the full-blown solution with permutations doesn't need to check for equality at all (thereby avoiding the trap of writing x != y != z to test for mutual inequality):

def valid_assignments():
    for f, p, s in itertools.permutations(range(1, 8), 3):
        if f+p+s == 12 and p%2 == 0:
            yield f, p, s

However, this is less efficient than necessary simply because there are 210 things you're iterating over. It'd be better to iterate over just f and p and select s as a result:

def valid_assignments2():
    for f in xrange(1, 8):          ## f can be any number
        for p in xrange(2, 8, 2):   ## p must be even
            s = 12 - (f+p)
            if 1 <= s <= 7 and f != s and f != p and s != p:
                yield f, p, s

Now we're only going over 21 things. Just saved ourselves a bunch of work!

\$\endgroup\$
  • \$\begingroup\$ Thank you for pointing out that the elements are unique in itertools.permutations. Though your second solution is more efficient, I like your first one, it is straight forward, clean and easy to maintain. \$\endgroup\$ – Nick Dec 13 '15 at 2:19
2
\$\begingroup\$

f != p != s does not prevent f and s from being equal

You can improve your algorithmic approach, using your constraints:

def iter_permutations():
    total = 12
    for f in range(1, 8):        # Fire must be between 1 and 7
        for p in range(2, 8, 2): # Police must be even
            s = total - p - f    # The sum must be 12
            if 0 < s < 8 and f != p != s != f: # They must be all different
                 yield f, p, s   # Use an iterator, because it's elegant!

You can simply use it with : for f, p, s in iter_permutations():

I think using an iterator is nicer than a list (you can easily get a list with list(iter_permutations()) if needed)

\$\endgroup\$
  • \$\begingroup\$ After reading your answer, I tested f != p != s and found that you are right. Then in order to express the inequality, I have to write f != p and p != s and f != s. Is there a better way to express this? \$\endgroup\$ – Nick Dec 12 '15 at 14:20
  • 1
    \$\begingroup\$ @Nick: It would be harder to read but f != p != s != f would be a shorter way of testing that none are equal. \$\endgroup\$ – SuperBiasedMan Dec 12 '15 at 14:37
  • 1
    \$\begingroup\$ @SuperBiasedMan: that's what I implemented in my answer ;-). You can do it more generic: if len(x) == len(set(x)): \$\endgroup\$ – oliverpool Dec 12 '15 at 14:46
  • \$\begingroup\$ @Nick or you can check if the product is a prime number ^^ \$\endgroup\$ – oliverpool Dec 12 '15 at 14:47
  • 2
    \$\begingroup\$ You also need to check that s is in range (i.e. positive). \$\endgroup\$ – 200_success Dec 12 '15 at 16:49
0
\$\begingroup\$

Well the short answer is yes there is a better way to unpack the tuple:

f, p, s = each_p

This unpacks each_p into three values so you no longer need to index the three values.

Also there's no need to call list on the result of permutations. You can iterate over the result with a loop just fine, and it will be more efficient than building a full list of all the permutations up front.


Also for valid_department_number, instead of using if blocks you could return the result of your boolean:

def valid_department_number(f, p, s):
    return f != p != s and f + p + s == 12 and p % 2 == 0

You don't need the brackets around the separate conditions so I removed them.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.