Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Program to list specific permutations of 5 digits

  1. Oct 10, 2015 #1

    Mark44

    Staff: Mentor

    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.

    Code (Python):

    # 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)
     
     
  2. jcsd
  3. Oct 10, 2015 #2

    pasmith

    User Avatar
    Homework Helper

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

       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.
     
  4. Oct 11, 2015 #3

    wle

    User Avatar

    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
      Code (Python):
      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:
    Code (Python):
    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:
      Code (Python):
      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:
      Code (Python):
      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.
     
    Last edited: Oct 11, 2015
  5. Oct 11, 2015 #4

    Mark44

    Staff: Mentor

  6. Oct 12, 2015 #5

    D H

    User Avatar
    Staff Emeritus
    Science Advisor

    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(...).

    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,
    Code (Python):
    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.
     
    Last edited: Oct 12, 2015
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook




Similar Discussions: Program to list specific permutations of 5 digits
Loading...