Program to list specific permutations of 5 digits

[Mark44]

Not long ago, a member posted a problem in the Homework section, concerned with determining which of the five-digit permutations of 4, 5, 6, 8, and 9 were divisible by 8.

I first thought about writing some C code to figure this out, but when I discovered that Python has some functions that would make this problem a lot easier, I abandoned my attempt using C. The permutations() and combinations() functions in the itertools module, are very useful in this problem.

I don't know much Python, so I used this problem as an exercise in becoming more knowledgeable with this language. If you have any comments on my code, feel free.

Here's the solution I came up with. BTW, my program reports that the are 20 permutations that are divisible by 8, and it lists them. There are several commented-out print statements that I used for debugging purposes. I left them in place, but commented-out, instead of removing them.

# plates.py
# Find all permutions of 4, 5, 6, 8, and 9 that are divisible by 8.
# I'm using license plates with five numeric digits as an analogy here. 
# Algorithm:
#   Construct all possible permutations of the set (4, 5, 6, 8, 9}.
#   For each permutation tuple, construct in integer whose digits are generated from the given tuple.
#   Strip off the two highest digits of the integer, leaving a three-digit integer.
#   If the three-digit integer is divisible by 8, the five-digit number it came from is also divisible by 8.
#   Display each of the five-digit numbers that are divisible by 8, together with how many there are.

import sys
import itertools

digit_set = ['4', '5', '6', '8', '9']
TotalCount = 0  # Count of all plates
Count8 = 0  # Count of plates with numbers that are divisible by 8
NumPlate = 0  # An individual license plate, as an integer
Last_three = 0# Make a collection of plates with the five digits in the list above.
plates = itertools.permutations(digit_set, 5)

# Iterate through each item in the plates collection.
for plate in plates:
    TotalCount = TotalCount + 1
    #print('Plate', plate)
    NumPlate = 0
  
    # A plate is a tuple of characters (actually, strings of length 1).
    # Construct a number out of the digit characters in each tuple.
    for ltr in plate:
    #print("Letter: ", ltr)
    NumPlate = 10 * NumPlate + int(ltr) 
    #print('Number plate: ', NumPlate)

    # Strip off the first two digits.
    # If the last three digits of an integer are divisible by 8, the integer is divisible by 8.
    # E.g., 1008 is divisible by 8, but 1009 is not.
    Last_three = NumPlate % 1000
    #print('Stripped digits: ', Last_three)
    if Last_three % 8 == 0:
       print('Last three digits: ', Last_three)
       print('Plate number: ', NumPlate)
       Count8 = Count8 + 1
    else:
       continue
  
print('Done')
print('Count of all permutations', TotalCount)
print('Count of permutations divisible by 8: ', Count8)

 

[pasmith]

Stripping the two leading digits before testing for divisibility by 8 should not be necessary; you should be able to use

   if NumPlate % 8 == 0:
      print('Plate number: ', NumPlate)
      Count8 = Count8 + 1

If you were only interested in obtaining the count rather than the actual numbers, you could instead check 5!/2 three-digit numbers for divisibility by 8 and then multiply the count by 2 to account for the permutations of the first two digits. This would be significantly more efficient than testing 5! five-digit numbers for divisibility by 8.

 

[wle]

I don't know much Python, so I used this problem as an exercise in becoming more knowledgeable with this language. If you have any comments on my code, feel free.

The else: continue in your loop isn't necessary. Like pasmith says, you're probably also not gaining anything by stripping off the first two digits before checking for a multiple of 8.

There are also some tricks you can use to reduce the number of intermediate variables and typing:

• You can define abbreviations for a package you import, e.g. import itertools as it would let you use it.permutations(...).
• If you insist on using characters for digits, int() will work with a string, so you could reduce your inner loop and counter to just num_plate = int(''.join(plate)).
• You can use map() to apply a function to each element of a list. For example, you could loop over all the permutations (as integers) by doing
  
  perms = map(lambda x: int(''.join(x)), it.permutations(digits))
  
  for p in perms:
    # Do something with p (p is an integer).
  In Python 3, map() returns an iterator which will generate the elements "on demand" rather than consume memory generating the whole list of elements at once.
• If you make digits a list of integers instead of characters, you can use reduce() from the functools package (import functools as ft) to turn a permutation into an integer. reduce() will apply a (user specified) function f of two arguments and accumulates a value by computing accum = f(accum, x) iteratively over the elements x of a list, so for example
  ft.reduce(lambda acc, x: 10 * acc + x, [1, 2, 3, 4, 5]) will return the integer 12345.

So if I wrote this program, it might look like this:

import functools as ft
import itertools as it

def digits_to_int(lst):
  return ft.reduce(lambda acc, x: 10 * acc + x, lst)

digits = [4, 5, 6, 8, 9]
total_count = 0
count8 = 0
perms = map(digits_to_int, it.permutations(digits)) 

for p in perms:
  total_count += 1

  if p % 8 == 0:
    count8 += 1
    print('Plate number:', p)

print('Total number of permutations:', total_count)
print('Permutations divisible by 8:', count8)

This is assuming you want to manually count the total number of permutations (presumably to check that the code is working as expected), otherwise it's just $5! = 120$.

A couple of other points:

• If you wanted to construct a list of permutations divisible by 8 rather than print them immediately, you could use a list comprehension for this:
  
  perms8 = [p for p in perms if p % 8 == 0]
  
  print('\n'.join(map(str, perms8)))
  print('Permutations divisible by 8:', len(perms8))
• The function digits_to_int could also have been defined/constructed using the partial() function, also from the functools module:
  
  digits_to_int = ft.partial(ft.reduce, lambda acc, x: 10 * acc + x)

I don't know Python that well myself. There may be even nicer ways of accomplishing some of these things.

 

[Mark44]

Thanks, @pasmith and @wle!

 

[D H]

You can define abbreviations for a package you import, e.g. import itertools as it would let you use it.permutations(...).

Alternatively, you can cherry-pick the items to be imported: from itertools import permutations imports itertools.permutations into the current namespace. All you need to do is type permutations(...).

You can use map() to apply a function to each element of a list.

Functions such as map, filter, and reduce are a bit frowned on by many as being not quite pythonic. You can almost always do the same with a list comprehension. The python BDFL Guido van Rossum proposed getting rid of all of them (along with lambda) back in 2005. That didn't happen, but the function reduce has been moved to the functools module in python 3.
I would attack this problem using list comprehensions. Using permutations over characters, a one liner to get the desired plates is
[n for n in (''.join(p) for p in permutations('45689')) if int(n) % 8 == 0]

Note that the above uses a list comprehension over a list comprehension, the outer one using a filter. List comprehensions are very powerful! Note also that the outer list comprehension creates a list while the inner one creates a generator. That the outer one is a list means it can be used to print the individual elements of the list and later reused to print the number of elements in the list. That the inner one is a generator means that a list of all of the possible permutations is not created. There are only 120 permutations in this case, so the memory savings are small. However, it's very easy to have a large number of permutations, in which case the memory savings can be huge. Finally, note that I'm using permutations('45689'). Python strings are iterables. There's no need for the more verbose permutations(('4','5','6','8','9')).

Incorporating this in a script,

from __future__ import print_function
from itertools import permutations
from math import factorial

plates8 = \
    [n for n in (''.join(p) for p in permutations('45689')) if int(n) % 8 == 0]
for plate in plates8 : print ('Plate number', plate)
print ('total=', factorial(5), 'count8=', len(plates8))

That first line ( from __future__ import print function) is important if you want the script to function in both python2 and python3.