Finding tuples of numbers subject to constraints

Question

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.

• SuperBiasedMan: As we all want to make our code more efficient or improve it in one way or another, try to write a title that summarizes what your code does, not what you want to get out of a review. For examples of good titles, check out Best of Code Review 2014 - Best Question Title Category You may also want to read How to get the best value out of Code Review - Asking Questions.
• Nick: @SuperBiasedMan Thank you very much for the reference link - I'm new here, the links are great for me.

Answer 1

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!

• Nick: 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.

Answer 2

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)

• Nick: 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?
• SuperBiasedMan: @Nick: It would be harder to read but f != p != s != f would be a shorter way of testing that none are equal.
• oliverpool: @SuperBiasedMan: that's what I implemented in my answer ;-). You can do it more generic: if len(x) == len(set(x)):
• oliverpool: @Nick or you can check if the product is a prime number ^^
• 200_success: You also need to check that s is in range (i.e. positive).

Answer 3

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.