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:

How to use a brute force algorithm to solve the problem.
How to use a greedy algorithm to solve the problem faster.

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:

9 > 1 is true.
1 < 4 is true.
4 > 2 is true.

And

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

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

9 > 4 is true.
4 < 2 is not true.
2 > 1 is 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,

There are n! placements.
Validating each placement requires n-1 operations (one for each constraint).

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,

Iterate over each comparison in C:
- If the comparison is "<", then take the least number from N.
- If the comparison is ">", then take the greatest number from N.
- Place the chosen number into the next empty box.
Place the remaining number from N into the last empty box.

Here's why this algorithm works:

In each iteration, a number is chosen to be placed into the next empty box.
If the comparison is "<", the least number in N, min(N), is chosen. Thus, the partial comparison looks like

[min(N)] < [x]

Where x is a number that has not been chosen yet.

It doesn't matter that x is not yet chosen, because the least number in N is less than every other number in N. As a result, any choice of x from the remaining numbers in N works.
If the comparison is ">", the greatest number in N, max(N), is chosen. Thus, the partial comparison looks like

[max(N)] > [x]

Where x is a number that has not been chosen yet.

It doesn't matter that x is not yet chosen, because the greatest number in N is greater than every other number in N. As a result, any choice of x from the remaining numbers in N works.
In the first iteration, there are no restrictions in choosing the least or greatest remaining number in N, because there are no previous partial comparisons to satisfy.
In the remaining iterations, using the above strategy never introduces restrictions in choosing the least or greatest remaining number in N, so each iteration can safely continue using the strategy.
As a result, every comparison is satistfied after the iteration is complete.

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.

The least remaining number is always the first number in numbers.
The greatest remaining number is always the last number in 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?

sorted uses timsort, which runs in O(n logn) time.
There are O(n) comparisons (n-1 comparisons) to iterate over.
Each iteration pops a number off of either end of the collections.deque object, which takes O(1) time per iteration.

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!

(If you spot any errors or typos on this post, contact me via my contact page.)