Расчет количества возможных перестановок, которые соответствуют требованию

Question

Этот вопрос беспокоит меня уже несколько дней, и я не знаю, как его решить.Я очень старался решить ее самостоятельно, но теперь я был бы очень признателен за помощь и указатель в правильном направлении.

Проблема:

Учитывая набор чисел и максимальные пределы, для которых каждое число может быть больше или меньше, чем следующий номер, определите количество действительных порядков чисел в соответствии с ограничениями.

Пример:

Числа: 20, 30, 36, 40

Максимальная сумма, на которую число может превышать следующее число: 16

Максимальная сумма, на которую число можетбыть меньше следующего числа: 8

Здесь будет 3 действительных заказа:

36 40 30 20

40 36 30 20

40 3036 20

Я разработал способ генерирования всех допустимых перестановок, используя рекурсию и деревья, но, к сожалению, это занимает слишком много времени в случаях, когда существует много допустимых порядков списка (приближается к n! Время выполнения, я считаю,).Мне кажется, что есть более быстрый, более математический способ решения этой проблемы с помощью комбинаторики, которого я просто не вижу.Буду признателен за любые советы, спасибо!

РЕДАКТИРОВАТЬ: Вот код для алгоритма перестановки, который я придумал.Последняя часть кода тестирует его на примере, который я привел выше.Это написано в 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)

Это печатает:

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

Answer 1

Попытка вашего подхода с 10 равными числами привела к времени выполнения 35 секунд.

Первое, что я заметил, это то, что функция нуждается только в последней записи в заголовке списка, поэтому функцию можноупрощено, чтобы взять целое число вместо списка.Следующий код имеет три упрощения:

1. Передать целое число для заголовка вместо списка
2. Измените итоговое значение на возвращаемое значение вместо глобального
3. Избегайтехранение дочерних элементов (поскольку требуется только количество порядков)

Упрощенный код выглядит следующим образом:

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)

Это занимает 7 секунд для списка из 10 равных чисел.

Второе, что я заметил, это то, что (для конкретного тестового примера) возвращаемое значение get_children зависит только от того, что True в посещенных, и от значения head.

Поэтому мы можем кешироватьрезультаты, чтобы избежать их пересчета:

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

Эта версия занимает всего 0,03 секунды для списка из 10 равных чисел (т.е. в 1000 раз быстрее, чем оригинал.)

Если вы делаете несколькоВ тестовых случаях с различными значениями b / u / d вы должны сбросить кэш в начале каждого тестового случая (т. е. cache = {}).

Answer 2

Как было отмечено в комментариях, нахождение всех действительных перестановок здесь эквивалентно идентификации всех гамильтоновых путей в ориентированном графе, в котором ваши числа представлены в виде вершин и ребер, соответствующих каждой паре чисел, которым разрешено следовать друг за другом.

Вот очень простая программа на Java ( IDEOne ) для поиска таких путей.Возможность решения этой проблемы зависит от размера вашего графика и коэффициента ветвления.

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);
  }
}

Вывод:

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