Calculating the Number of Possible Permutations that Meet a Requirement

Question

This question has been bugging me for days now, and I am at a loss as how to solve it. I have tried very hard to solve it on my own, but now I would just very much appreciate some help and a pointer in the right direction.

Problem:

Given a set of numbers, and the maximum limits for which each number can be greater than or less than the following number, determine the number of valid orderings of the numbers according to the limits.

Example:

Numbers: 20, 30, 36, 40

Max amount that a number can be greater than the following number: 16

Max amount that a number can be less than the following number: 8

Here there would be 3 valid orderings:

36 40 30 20

40 36 30 20

40 30 36 20

I have devised a way to generate all valid permutations using recursion and trees, but unfortunately it takes far too long in cases in which there are many valid orders of the list (approaches n! run time I believe). I feel as if there is a quicker, more mathematical way of solving this using combinatorics that I am just not seeing. Any advice would be greatly appreciated, thank you!

EDIT: Here's the code for the permutation algorithm I came up with. The last part of the code tests it out with the sample I gave above. It is written in Python 3.6.

class block:
    def __init__(self, val, children):
        self.val = val
        self.children = children


# Gets all the possible children of the current head within the limits
def get_children(head, nums, b, visited, u, d):
    global total
    if all(visited):
        total += 1
        return

    for i in range(b):
        if not visited[i]:
            if head.val - nums[i] <= d and nums[i] - head.val <= u:
                head.children.append(block(nums[i], []))
                visited[i] = True
                get_children(head.children[-1], nums, b, visited, u, d)
                visited[i] = False


# Display all the valid permutations of the current head
def show(head, vals, b):
    vals.append(head.val)
    if head.children == [] and len(vals) == b:
        print(*vals)
        return
    for child in head.children:
        show(child, vals[:], b)


# Test it out with the sample
b, nums, u, d = 4, [20, 30, 36, 40], 8, 16
visited = [False for x in range(b)]
total = 0
heads = []
for i in range(b):
    heads.append(block(nums[i], []))
    visited[i] = True
    get_children(heads[-1], nums, b, visited, u, d)
    visited[i] = False
    show(heads[-1], [], b)
print(total)

This prints:

36 40 30 20
40 30 36 20
40 36 30 20
3

Answer 1

Trying your approach with 10 equal numbers resulted in a run-time of 35 seconds.

The first thing I noticed is that the function only needs the last entry in the list head, so the function can be simplified to take an integer instead of a list. The following code has three simplifications:

1. Pass in an integer for head instead of a list
2. Change total to be a return value instead of a global
3. Avoid storing the children (as only the count of orderings is required)

The simplified code looks like:

def get_children(head, nums, b, visited, u, d):
    if all(visited):
        return 1
    t = 0
    for i in range(b):
        if not visited[i]:
            if head - nums[i] <= d and nums[i] - head <= u:
                head2 = nums[i]
                visited[i] = True
                t += get_children(head2, nums, b, visited, u, d)
                visited[i] = False
    return t

# Test it out with the sample
nums, u, d = [20, 30, 36, 40], 8, 16
b = len(nums)
visited = [False for x in range(b)]
total = 0
for i in range(b):
    head = nums[i]
    visited[i] = True
    total += get_children(head, nums, b, visited, u, d)
    visited[i] = False
print(total)

This takes 7 seconds for a list of 10 equal numbers.

The second thing I noticed is that (for a particular test case) the return value of get_children only depends on the things that are True in visited and the value of head.

Therefore we can cache the results to avoid recomputing them:

cache={}
# Gets all the possible children of the current head within the limits
def get_children(head, nums, b, visited, u, d):
    if all(visited):
        return 1
    key = head,sum(1<<i for i,v in enumerate(visited) if v)
    result = cache.get(key,None)
    if result is not None:
        return result
    t = 0
    for i in range(b):
        if not visited[i]:
            if head - nums[i] <= d and nums[i] - head <= u:
                head2 = nums[i]
                visited[i] = True
                t += get_children(head2, nums, b, visited, u, d)
                visited[i] = False
    cache[key] = t
    return t

This version only takes 0.03 seconds for a list of 10 equal number (i.e. 1000 times faster than the original.)

If you are doing multiple test cases with different values of b/u/d you should reset the cache at the start of each testcase (i.e. cache={}).

Answer 2

As has been noted in the comments, finding all valid permutations here is equivalent to identifying all Hamiltonian paths in the directed graph that has your numbers as vertices and edges corresponding to each pair of numbers that are permitted to follow one another.

Here's a very simple Java (IDEOne) program to find such paths. Whether this makes your problem tractable depends on the size of your graph and the branching factor.

public static void main(String[] args)
{
  int[] values = {20, 30, 36, 40};

  Vertex[] g = new Vertex[values.length];
  for(int i=0; i<g.length; i++) 
    g[i] = new Vertex(values[i]);

  for(int i=0; i<g.length; i++) 
    for(int j=0; j<g.length; j++)
      if(i != j && g[j].id >= g[i].id-16 && g[j].id <= g[i].id+8)
        g[i].adj.add(g[j]);

  Set<Vertex> toVisit = new HashSet<>(Arrays.asList(g));
  LinkedList<Vertex> path = new LinkedList<>();
  for(int i=0; i<g.length; i++)
  {
    path.addLast(g[i]);
    toVisit.remove(g[i]);
    findPaths(g[i], path, toVisit);
    toVisit.add(g[i]);
    path.removeLast();
  }
}

static void findPaths(Vertex v, LinkedList<Vertex> path, Set<Vertex> toVisit)
{
  if(toVisit.isEmpty())
  {
    System.out.println(path);
    return;
  }

  for(Vertex av : v.adj)
  {
    if(toVisit.contains(av))
    {
      toVisit.remove(av);
      path.addLast(av);
      findPaths(av, path, toVisit);
      path.removeLast();
      toVisit.add(av);
    }
  }
}

static class Vertex
{
  int id;
  List<Vertex> adj;

  Vertex(int id)
  {
    this.id = id;
    adj = new ArrayList<>();
  }

  public String toString()
  {
    return String.valueOf(id);
  }
}

Output:

[36, 40, 30, 20]
[40, 30, 36, 20]
[40, 36, 30, 20]