Ответ 1

Это называется топологической сортировкой. Вы можете смоделировать "блокирование" как ребра ориентированного графа. Это должно работать, если нет круглых "блокировок".

Ответ 2

Я сделал это в <100 строк кода С# (с комментариями). Эта реализация кажется немного сложной.

Вот схема алгоритма

1. Создайте очередь с приоритетами по значению, по которому вы хотите отсортировать
2. Вставьте все элементы, которые не имеют никаких "блокирующих" соединений входящих
3. Пока есть элементы в очереди:
   1. Возьмите элемент очереди. Поместите это в свой итоговый список.
   2. Если есть какие-либо элементы, которые были напрямую заблокированы этим элементом и ранее не посещались, поместите их в очередь (элемент может иметь более одного блокирующего элемента, поэтому вы должны проверить это)

Список необработанных элементов должен быть пустым в конце, или у вас был цикл в ваших зависимостях.

Это очень важно Топологическая сортировка со встроенным приоритетом для узлов. Имейте в виду, что результат может быть весьма удивительным, в зависимости от количества соединений в вашем графике (например, возможно получить элементы в обратном порядке).

Ответ 3

Как сказал в своем ответе Pratik Deoghare, вы можете использовать топологическую сортировку. Вы можете просматривать свои "зависимости" как дуги направленного ациклического графа (DAG). Ограничение того, что зависимости от объектов являются ациклическими, важно, так как топологическая сортировка возможна только "тогда и только тогда, когда граф не имеет направленных циклов". Зависимости также, конечно, не имеют смысла в противном случае (то есть a зависит от b, а b зависит от a, не имеет смысла, потому что это циклическая зависимость).

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

Общее время выполнения по-прежнему равно O (n log n), поскольку топологическая сортировка - O (n), а сортировка по слоям - O (n log n). Смотрите топологическую сортировку вики для полного анализа времени выполнения.

Ответ 4

Java-код для топологической сортировки:

static List<ValueType> topoSort(List<ValueType> vertices) {
        List<ValueType> result = new ArrayList<>();
        List<ValueType> todo = new LinkedList<>();

        Collections.sort(vertices);
        for (ValueType v : vertices){
            todo.add(v);
        }

        outer:
        while (!todo.isEmpty()) {
            for (ValueType r : todo) {
                if (!hasDependency(r, todo)) {
                    todo.remove(r);
                    result.add(r);
                    // no need to worry about concurrent modification
                    continue outer;
                }
            }
        }
        return result;
    }

    static boolean hasDependency(ValueType r, List<ValueType> todo) {
        for (ValueType c : todo) {
            if (r.getDependencies().contains(c))
                return true;
        }
        return false;
    }

ValueType описан как ниже:

class ValueType implements Comparable<ValueType> {
    private Integer index;
    private String value;
    private List<ValueType> dependencies;

    public ValueType(int index, String value, ValueType...dependencies){
        this.index = index;
        this.value = value;
        this.dependencies = dependencies==null?null:Arrays.asList(dependencies);
    }

    public List<ValueType> getDependencies() {
        return dependencies;
    }

    public void setDependencies(List<ValueType> dependencies) {
        this.dependencies = dependencies;
    }

    @Override
    public int compareTo(@NotNull ValueType o) {
        return this.index.compareTo(o.index);
    }

    @Override
    public String toString() {
        return value +"(" + index +")";
    }
}

И проверено с этими значениями:

public static void main(String[] args) {
    //[{'a',6},{'b',1},{'c',5},{'d',15},{'e',12},{'f',20},{'g',14},{'h',7}]
    //a depends on e
    //g depends on d
    //c depends on b
    ValueType b = new ValueType(1,"b");
    ValueType c = new ValueType(5,"c", b);
    ValueType d = new ValueType(15,"d");
    ValueType e = new ValueType(12,"e");
    ValueType a = new ValueType(6,"a", e);
    ValueType f = new ValueType(20,"f");
    ValueType g = new ValueType(14,"g", d);
    ValueType h = new ValueType(7,"h");
    List<ValueType> valueTypes = Arrays.asList(a,b,c,d,e,f,g,h);
    List<ValueType> r = topoSort(valueTypes);
    for(ValueType v: r){
        System.out.println(v);
    }
}

Ответ 5

Поскольку вы сказали, что любой язык может быть преобразован в Java, я сделал комбинацию из [того, что я думаю] вашего алгоритма и ghord в C.

Большая часть кода является шаблонной для обработки массивов, поисков и вставки массивов/списков, которые, я считаю, могут быть сокращены с помощью стандартных примитивов Java. Таким образом, количество фактического кода алгоритма довольно мало.

Алгоритм, который я придумал:

Дано: необработанный список всех элементов и список зависимостей

Скопируйте элементы, которые зависят от другого элемента, в список "Hold". В противном случае скопируйте их в список "сортировки".

Примечание: альтернативой является использование только списка сортировки и просто удаление узлов, которые зависят от другого, в список удержания.

Сортировать список "сортировка".

Для всех элементов в списке зависимостей найдите соответствующие узлы в списке сортировки и в списке удержания. Вставьте элемент hold в список сортировки после соответствующего элемента сортировки.

Вот код:

#include <stdio.h>
#include <stdlib.h>

// sort node definition
typedef struct {
    int key;
    int val;
} Node;

// dependency definition
typedef struct {
    int keybef;                         // key of node that keyaft depends on
    int keyaft;                         // key of node to insert
} Dep;

// raw list of all nodes
Node rawlist[] = {
    {'a',6},  // depends on e
    {'b',1},
    {'c',5},  // depends on b
    {'d',15},
    {'e',12},
    {'f',20},
    {'g',14},  // depends on d
    {'h',7}
};

// dependency list
Dep deplist[] = {
    {'e','a'},
    {'b','c'},
    {'d','g'},
    {0,0}
};

#define MAXLIST     (sizeof(rawlist) / sizeof(rawlist[0]))

// hold list -- all nodes that depend on another
int holdcnt;
Node holdlist[MAXLIST];

// sort list -- all nodes that do _not_ depend on another
int sortcnt;
Node sortlist[MAXLIST];

// prtlist -- print all nodes in a list
void
prtlist(Node *node,int nodecnt,const char *tag)
{

    printf("%s:\n",tag);
    for (;  nodecnt > 0;  --nodecnt, ++node)
        printf("  %c:%d\n",node->key,node->val);
}

// placenode -- put node into hold list or sort list
void
placenode(Node *node)
{
    Dep *dep;
    int holdflg;

    holdflg = 0;

    // decide if node depends on another
    for (dep = deplist;  dep->keybef != 0;  ++dep) {
        holdflg = (node->key == dep->keyaft);
        if (holdflg)
            break;
    }

    if (holdflg)
        holdlist[holdcnt++] = *node;
    else
        sortlist[sortcnt++] = *node;
}

// sortcmp -- qsort compare function
int
sortcmp(const void *vlhs,const void *vrhs)
{
    const Node *lhs = vlhs;
    const Node *rhs = vrhs;
    int cmpflg;

    cmpflg = lhs->val - rhs->val;

    return cmpflg;
}

// findnode -- find node in list that matches the given key
Node *
findnode(Node *node,int nodecnt,int key)
{

    for (;  nodecnt > 0;  --nodecnt, ++node) {
        if (node->key == key)
            break;
    }

    return node;
}

// insert -- insert hold node into sorted list at correct spot
void
insert(Node *sort,Node *hold)
{
    Node prev;
    Node next;
    int sortidx;

    prev = *sort;
    *sort = *hold;

    ++sortcnt;

    for (;  sort < &sortlist[sortcnt];  ++sort) {
        next = *sort;
        *sort = prev;
        prev = next;
    }
}

int
main(void)
{
    Node *node;
    Node *sort;
    Node *hold;
    Dep *dep;

    prtlist(rawlist,MAXLIST,"RAW");

    printf("DEP:\n");
    for (dep = deplist;  dep->keybef != 0;  ++dep)
        printf("  %c depends on %c\n",dep->keyaft,dep->keybef);

    // place nodes into hold list or sort list
    for (node = rawlist;  node < &rawlist[MAXLIST];  ++node)
        placenode(node);
    prtlist(sortlist,sortcnt,"SORT");
    prtlist(holdlist,holdcnt,"HOLD");

    // sort the "sort" list
    qsort(sortlist,sortcnt,sizeof(Node),sortcmp);
    prtlist(sortlist,sortcnt,"SORT");

    // add nodes from hold list to sort list
    for (dep = deplist;  dep->keybef != 0;  ++dep) {
        printf("inserting %c after %c\n",dep->keyaft,dep->keybef);
        sort = findnode(sortlist,sortcnt,dep->keybef);
        hold = findnode(holdlist,holdcnt,dep->keyaft);
        insert(sort,hold);
        prtlist(sortlist,sortcnt,"POST");
    }

    return 0;
}

Вот вывод программы:

RAW:
  a:6
  b:1
  c:5
  d:15
  e:12
  f:20
  g:14
  h:7
DEP:
  a depends on e
  c depends on b
  g depends on d
SORT:
  b:1
  d:15
  e:12
  f:20
  h:7
HOLD:
  a:6
  c:5
  g:14
SORT:
  b:1
  h:7
  e:12
  d:15
  f:20
inserting a after e
POST:
  b:1
  h:7
  e:12
  a:6
  d:15
  f:20
inserting c after b
POST:
  b:1
  c:5
  h:7
  e:12
  a:6
  d:15
  f:20
inserting g after d
POST:
  b:1
  c:5
  h:7
  e:12
  a:6
  d:15
  g:14
  f:20

Ответ 6

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

1. Создайте карту, которая связывает каждый элемент с элементами, которые зависят от него.
2. Вставьте элементы без зависимостей в кучу.
3. Удалить верхний элемент из кучи.
4. Вычтите 1 из числа зависимостей каждого зависимого элемента.
5. Добавьте любые элементы с нулевым количеством зависимостей в кучу.
6. Повторите с шага 3, пока куча не станет пустой.

Для простоты я заменил ваш ValueType на String, но применимы те же понятия.

Класс BlockedItem:

import java.util.ArrayList;
import java.util.List;

public class BlockedItem implements Comparable<BlockedItem> {

    private String value;
    private int index;
    private List<BlockedItem> dependentUpon;
    private int dependencies;

    public BlockedItem(String value, int index){
        this.value = value;
        this.index = index;
        this.dependentUpon = new ArrayList<>();
        this.dependencies = 0;
    }

    public String getValue() {
        return value;
    }

    public List<BlockedItem> getDependentUpon() {
        return dependentUpon;
    }

    public void addDependency(BlockedItem dependentUpon) {
        this.dependentUpon.add(dependentUpon);
        this.dependencies++;
    }

    @Override
    public int compareTo(BlockedItem other){
        return this.index - other.index;
    }

    public int countDependencies() {
        return dependencies;
    }

    public int subtractDependent(){
        return --this.dependencies;
    }

    @Override
    public String toString(){
        return "{'" + this.value + "', " + this.index + "}";
    }

}

Класс BlockedItemHeapSort:

import java.util.*;

public class BlockedItemHeapSort {

    //maps all blockedItems to the blockItems which depend on them
    private static Map<String, Set<BlockedItem>> generateBlockedMap(List<BlockedItem> unsortedList){
        Map<String, Set<BlockedItem>> blockedMap = new HashMap<>();
        //initialize a set for each element
        unsortedList.stream().forEach(item -> {
            Set<BlockedItem> dependents = new HashSet<>();
            blockedMap.put(item.getValue(), dependents);
                });
        //place each element in the sets corresponding to its dependencies
        unsortedList.stream().forEach(item -> {
            if(item.countDependencies() > 0){
                item.getDependentUpon().stream().forEach(dependency -> blockedMap.get(dependency.getValue()).add(item));
            }
        });
        return blockedMap;
    }

    public static List<BlockedItem> sortBlockedItems(List<BlockedItem> unsortedList){
        List<BlockedItem> sorted = new ArrayList<>();
        Map<String, Set<BlockedItem>> blockedMap = generateBlockedMap(unsortedList);

        PriorityQueue<BlockedItem> itemHeap = new PriorityQueue<>();

        //put elements with no dependencies in the heap
        unsortedList.stream().forEach(item -> {
            if(item.countDependencies() == 0) itemHeap.add(item);
        });

        while(itemHeap.size() > 0){
            //get the top element
            BlockedItem item = itemHeap.poll();
            sorted.add(item);
            //for each element that depends upon item, decrease its dependency count
            //if it has a zero dependency count after subtraction, add it to the heap
            if(!blockedMap.get(item.getValue()).isEmpty()){
                blockedMap.get(item.getValue()).stream().forEach(dependent -> {
                    if(dependent.subtractDependent() == 0) itemHeap.add(dependent);
                });
            }
        }

        return sorted;
    }

}

Вы можете изменить это, чтобы более точно соответствовать вашему варианту использования.