Как выявить логическое противоречие в условиях сортировки? - PullRequest
Новая
       34

Как выявить логическое противоречие в условиях сортировки?

1 голос
/ 04 августа 2020

У меня есть список строк вместе с условиями, которые определяют способ их сортировки.

Условия можно упростить до формы, X before Y или X after Y.

Однако , одно (или несколько) условий противоречат остальным. друг с другом.

Как только это будет сделано, я смогу реконструировать исходный массив sorted (который мне не известен).

conditions ниже - согласовано, но для иллюстрации может быть сделано противоречивым, что приведет к неправильной сортировке, просто добавив 'Sam' before 'Sue', как показано в комментариях.

Такое крошечное противоречие в таком крошечном примере может быть идентифицировано вручную в минуту. Но мой реальный случай включает в себя список из 100 строк и нескольких сотен условий.

Сначала я ищу ответ на вопрос: «Возможно ли выявить не просто какое-либо противоречие, но и как можно меньше противоречий, которые могут быть устранены, чтобы оставить согласованные условия? "

И во-вторых, надеюсь, некоторая помощь в том, как к этому подойти.

Противоречие, используемое здесь в качестве примера, легко идентифицировать. Но представьте, если бы среди них были включены условия 'Sam' before 'Sue', 'Sue' before 'Bob' и 'Bob' before 'Sam'. Тогда было бы не так очевидно, что существует круговая цепочка условий. 

'use strict';

const sorted = ['Sam', 'Sue', 'Bob', 'Dylan'];

const conditions = {
  Sam: {
    before: ['Sue', 'Bob', 'Dylan'],
    after: [],
  },
  Sue: {
    before: ['Bob', 'Dylan'], // adding 'Sam' causes incorrect sort
    // and contradiction, because it can't be both before 'Sam' and after 'Sam'
    after: ['Sam']
  },
  Bob: {
    before: ['Dylan'],
    after: ['Sam', 'Sue']
  },
  Dylan: {
    before: [],
    after: ['Sam', 'Sue', 'Bob'],
  }
};

const unsorted = ['Bob', 'Dylan', 'Sam', 'Sue'];

const resorted = [...unsorted].sort((a, b) => {
  if (conditions[a].before.includes(b)) return -1;
  if (conditions[b].after.includes(b)) return 1;
  return 0;
});

console.log(resorted); // [ 'Sam', 'Sue', 'Bob', 'Dylan' ]

Когда я впервые попробовал это с противоречивыми условиями, я надеялся, что метод .sort() введет бесконечное l oop как способ сказать мне, что существует противоречие. Но на самом деле он все равно сортирует их, просто неправильно.

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

...