Return to Blog

Solving the Number Placement Problem using Python

By John Lekberg on March 25, 2020.


This week's post is about solving the "Number Placement Problem". You will learn:

Problem statement

You are given a set of distinct numbers:

1, 4, 2, 9

And you are given empty boxes with comparisons between them:

[ ] > [ ] < [ ] > [ ] 

Your goal is to place all the numbers into the boxes in a way that satisfies all the comparisons. E.g.

[9] > [1] < [4] > [2] 

is a valid solution because all of the comparisons are true:

And

[9] > [4] < [2] > [1]

is an invalid solution because not all of the comparisons are true:

How I represent the data in the problem

I represent the set of numbers using a set object:

{ 1, 4, 2, 9 }

I represent a comparison using an Enum object:

import enum

Comparison = enum.Enum("Comparison", ["Less", "Greater"])

I represent the empty boxes with comparisons between them as a list of Comparison objects:

[Comparison.Greater, Comparison.Less, Comparison.Greater]

Creating a brute force solution

A brute force solution will attempt every way to place the numbers into the empty boxes.

Each attempt needs to be validated, so here is a function that generates all the constraints that the attempt must satisfy:

def constraints(placement, comparisons):
    """Generate all constraints for a potential solution.
    
    placement -- a sequence of numbers. E.g. [1, 4, 2, 9].
    comparisons -- a sequence of Comparison objects. E.g.
        [Comparison.Greater, Comparison.Less, Comparison.Greater].
    """
    for a, b, comp in zip(placement, placement[1:], comparisons):
        if comp is Comparison.Less:
            yield a < b
        elif comp is Comparison.Greater:
            yield a > b
            
list(constraints(
    [9, 4, 2, 1],
    [Comparison.Greater, Comparison.Less, Comparison.Greater]
))
[True, False, True]

And here is a function that checks if all comparisons are satisfied by a placement:

def valid_solution(placement, comparisons):
    """Check if a placement of numbers is valid."""
    return all(constraints(placement, comparisons))

valid_solution(
    [9, 1, 4, 2],
    [Comparison.Greater, Comparison.Less, Comparison.Greater]
)
True
valid_solution(
    [9, 4, 2, 1],
    [Comparison.Greater, Comparison.Less, Comparison.Greater]
)
False

Here's a function that attempts every placement of numbers to find a valid solution:

import itertools

def number_placement_bf(numbers, comparisons):
    """Use brute force to solve the Number Placement Problem.
    
    numbers -- a set of numbers. E.g. {1, 4, 2, 9}.
    comparisons -- a list of comparisons. E.g. 
        [Comparison.Greater, Comparison.Less, Comparison.Greater].
    """
    all_placements = itertools.permutations(numbers)
    for placement in all_placements:
        if valid_solution(placement, comparisons):
            return placement

number_placement_bf(
    {1, 4, 2, 9},
    [Comparison.Greater, Comparison.Less, Comparison.Greater]
)
(2, 1, 9, 4)

What is the time complexity of the solution? For a set of n numbers,

As a result, the time complexity of the brute force algorithm is:

O(n! n)

This means that, if using the brute force algorithm on a set of 4 numbers took 1 second, then using the brute force algorithm on a set of 10 numbers would take over 4 days!

Using a greedy algorithm to create a faster solution

I will use a greedy algorithm to generate a faster solution than using the brute force algorithm.

Here's the algorithm. Given the set of numbers N and the list of comparisons C,

Here's why this algorithm works:

Here's a function that implements this greedy algorithm:

import collections

def number_placement_greedy(numbers, comparisons):
    """Use a greedy strategy to solve the Number Placement Problem.
    
    numbers -- a set of numbers. E.g. { 1, 4, 2, 9 }.
    comparisons -- a list of comparisons. E.g.
        [Comparison.Greater, Comparison.Less, Comparison.Greater].
    """
    numbers = collections.deque(sorted(numbers))
    
    for comp in comparisons:
        if comp is Comparison.Less:
            least = numbers.popleft()
            yield least
        elif comp is Comparison.Greater:
            greatest = numbers.pop()
            yield greatest
    
    last = numbers.pop()
    yield last

list(number_placement_greedy(
    {1, 4, 2, 9},
    [Comparison.Greater, Comparison.Less, Comparison.Greater]
))
[9, 1, 4, 2]

I sort the list using the built-in function sorted. This allows me to easily remove the least and greatest remaining numbers.

I use a collections.deque object because removing an item from the beginning of a list object is an O(n) operation. (See the Python Wiki's "Time Complexity" page for a time complexity comparison of list objects and collections.deque objects.)

What is the time complexity of the greedy algorithm?

As a result, the time complexity of the greedy algorithm is

O(n logn)

This means that, if using the greedy algorithm on a set of 4 numbers took 1 second, then using the greedy algorithm on a set of 10 numbers would take about 4 seconds. Compare this with the brute force algorithm, which would take over 4 days.

In conclusion...

In this post, you learned how to use a greedy algorithm to quickly solve the "Number Placement Problem". Greedy algorithms only work on problems where you don't need to backtrack on decisions. But, when you can use a greedy algorithm, it is often one of the fastest ways to solve the problem.

My challenge to you:

How would you solve this problem if the numbers weren't distinct? For example, given this set of numbers:

1, 1, 2, 2, 3

And this layout of empty boxes with comparisons:

[ ] < [ ] < [ ] > [ ] < [ ]

A valid solution is

[1] < [2] < [3] > [1] < [2]

But the greedy algorithm would generate this invalid solution:

[1] < [1] < [3] > [2] < [2]

If you enjoyed this week's post, share it with your friends and stay tuned for next week's post. See you then!