09 NOV 2018
538 Riddler Express
What Are The Odds
You Already Have My Phone Number

Assume the phone company assigns seven digit phone numbers in a random way. What are the chances that when you get a second phone then the number it will be assigned will contain the same digits as your first phone number, including any repetitions of digits.  Such numbers are said to be ‘scrambles’ of each other.

An example of a ‘scramble’ is the pair 608-2338 and 830-2386.  Also suppose that all the phone numbers from 000-0000 up to and including 999-9999 are are up for grabs. (Note there are many different seven digit numbers that the phone company actually never assigns, and we ignore this).

NOTE: if your first phone’s number is like 000-0000 or 111-1111 or other number with all seven digits the same then you would be guaranteed to get a number that is not a ‘scramble’ of your first phone when you get the number for your second phone since all ‘scrambles’ of such numbers come out the same. There is only ONE of each of these types.  So your chances of getting a scramble would be: ZERO. So we do not consider these.

So here is how to figure this out:  Think of a line of buckets each filled    with numbers each number in a any bucket is a scrambles of any other in that bucket.  If you pick two numbers from any of those buckets you will be guaranteed they will be scrambles of each other.

What are the chances that after randomly picking a ball from one of ‘m’ buckets.  You again choose a bucket at random and that is the same bucket you picked your first ball from.

Easy: 1/m — you have ‘one-chance-in-m’ of getting the same bucket.

Here is the interesting part:  How many buckets are there?

For each number from 000 0000 all the way to 999 9999 take that number and reduce it to a number whose digits are ‘in-order’.

For example the number 608 2338 would be reduced to 023 3688.  Scratch that number on the bucket and toss in the original number.  Do this and track that numbers from 000 0000 to 999 9999 when the number you come up with after ordering the digits already exist then just toss your number in the bucket.  If there is no bucket just scratch the ordered number on the bucket and toss it in.

Some buckets have a few numbers and some buckets have a lot of numbers.  The buckets with the fewest numbers in them have only 7 numbers in them.  The buckets with the most numbers in them have 5,040 numbers in them. And the total number of buckets is 11,430 buckets.

So grab a number from a bucket then you have a 1 in 11,430 chance of putting your hand in the same bucket.  But if you do then you get a ‘scramble’. 

Here is one way to count the number of buckets:

import sys
import random

n_dct = {}

def set_itm_val_in_dct(n_raw):
    """
        Update The Dictionary:
        Using the input number 'n_raw'
        create a new value/pair for the dictionary 'n_dct'
        or increment the value part of an existing value/pair
    """
    n_str = str(n_raw)
    n_lst = list(n_str)
    n_len = len(n_lst)
    for _ in range(7-n_len):
        n_lst.insert(0,"0")
    n_lst.sort()

    """ Ignore Numbers That Have All The Same Digits """
    if n_lst[0] == n_lst[6]:
        return

    n_lst = "".join(n_lst)

    if n_lst in n_dct:
        n_dct[n_lst] += 1
    else:
        n_dct[n_lst] = 1

def n_dct_fill(n_max):
    """
        Build The Dictionary
        Create n_dct using the values 0 ... n (n_max-1)
    """
    for n in range(1, n_max):
        set_itm_val_in_dct(n)

def dct_print():
    """
        Print The Dictionary
    """
    print len(n_dct)
    count = 0
    n_tup = n_dct.items()
    n_tup.sort(key=lambda elem: elem[1])
    for tup in n_tup:
        count += 1
        if count % 10 == 0:
            print("")
        prt_str = '{: >7}:{: >5}'.format(tup[0], tup[1])
        print (prt_str),
    print count

# Create The Dictionary
if __name__ == "__main__":
    """ From 000-0000 to 999-9999 """
    n_dct_fill(10000000)
    dct_print()