如何根据不完整的标准排序? [英] How to sort based on incomplete criteria?

问题描述

首先，我尝试将自己的函数传递给Array.sort，但是它无法正确排序.请注意，即使正确处理了if (b == 'a' && a == 'c')情况，结果中'c'还是比'a'早.

First I tried passing my own function to Array.sort, but it doesn't sort correctly. Notice how 'c' comes before 'a' in the result, even though the case if (b == 'a' && a == 'c') is handled correctly.

这些数据仅是示例.我的实际数据不应该按字母顺序排序.它必须使用a_before_b和b_before_a函数中说明的逻辑.

These data are just for example. My actual data is not to be alphabetically sorted. It must use the logic illustrated in the a_before_b and b_before_a functions.

由于我仅具有确定某些(并非全部)元素对的相对排序的条件，因此可能存在多个有效的元素排序.我只需要产生任何有效的顺序即可，其中有效的方法并不与我的任何条件(在a_before_b和b_before_a函数中定义的)相矛盾.

Since I only have conditions to determine the relative ordering of SOME (NOT all) pairs of elements, there may be multiple valid orderings of elements. I just need to produce ANY valid ordering, where valid means does not contradict any of my conditions (which are defined in the a_before_b and b_before_a functions).

const sorted = ['a', 'b', 'c', 'd']; // I do NOT have access to this
const unsorted = ['c', 'd', 'a', 'b'];

const a_before_b = (a, b) => {
  if (a == 'a' && b == 'd') return true;
  if (a == 'b' && b == 'c') return true;
}

const b_before_a = (a, b) => {
  if (b == 'a' && a == 'c') return true;
  if (b == 'b' && a == 'c') return true;
}

const mySortingFunction = (a, b) => {
  if (a_before_b(a, b)) return -1;
  if (b_before_a(a, b)) return 1;
  return 0;
}

// doesn't produce correct sorting 
console.log(unsorted.sort(mySortingFunction)); // [ 'c', 'a', 'd', 'b' ]

然后我尝试从头开始编写自己的排序.但是它进入了无限循环，我不知道为什么.

Then I tried writing my own sort from scratch. But it enters an infinite loop and I don't know why.

const sorted = ['a', 'b', 'c', 'd'];
const unsorted = ['c', 'd', 'a', 'b'];

const a_before_b = (a, b) => {
  if (a == 'a' && b == 'd') return true;
  if (a == 'b' && b == 'c') return true;
}

const b_before_a = (a, b) => {
  if (b == 'a' && a == 'c') return true;
  if (b == 'b' && a == 'c') return true;
}

const findAnUnsortedElement = array => {
  for (let [i, element] of Object.entries(array)) {
    i = +i;
    const a = element;
    const b = array[i + 1];
    if (b === undefined) return 'SORTING_COMPLETE';
    if (!a_before_b(a, b)) console.log(a, 'should not be before', b);
    if (b_before_a(a, b)) console.log(b, 'should be before', a);
    if (!a_before_b(a, b) || b_before_a(a, b)) return a;
  }
}

// from w3schools
function move(arr, old_index, new_index) {
  while (old_index < 0) {
    old_index += arr.length;
  }
  while (new_index < 0) {
    new_index += arr.length;
  }
  if (new_index >= arr.length) {
    var k = new_index - arr.length;
    while ((k--) + 1) {
      arr.push(undefined);
    }
  }
  arr.splice(new_index, 0, arr.splice(old_index, 1)[0]);
  return arr;
}

// enters infinite loop, never returns
const myCustomSort = array => {
  while (findAnUnsortedElement(array) != 'SORTING_COMPLETE') {
    const element = findAnUnsortedElement(array);
    const index = array.findIndex(el => el == element);
    console.log('moving', element);
    array = move(array, index, index + 1);
    console.log(array);
  }
  return array;
}

console.log(myCustomSort(unsorted));

推荐答案

我早先给出的答案(您首先接受)中的算法实际上是基于启发式算法的.

The algorithm in the answer I gave earlier on, and which you (first) accepted, is really based on a heuristic.

要确保已排序的输出没有任何违规，可以将此问题视为图形问题.每当两个值可以进行比较以给出true(具有比较器功能)时，该对就代表图形中的一条边.

For a sorted output to be guaranteed to not have any violations, you could treat this problem as a graph problem. Whenever two values can make a comparison that gives true (with either comparator function), then that pair represents an edge in the graph.

如果顺序一致，则必须有一个值是其他值中最小的一个，否则您将有一个循环.

If the order is consistent, then there must be one value that is the least among the others, otherwise you would have a cycle.

因此，借助这些知识，我们可以为图中的每个节点确定到该最小节点的最长路径有多长时间.当您找到到此类最小节点的最长距离时，可以将该路径的长度用作绝对顺序指示.

So with that knowledge we can determine for each node in the graph how long the longest path is to such a least node. When you find the longest distance to such a least node, you can use the length of that path as an absolute order indication.

这是一个实现:

class Node {
    constructor(value) {
        this.value = value;
        this.prev = new Set;
        this.order = 0; // No order yet
    }
    orderWith(other) {
        if (other === this) return;
        if (a_before_b(this.value, other.value) || b_before_a(other.value, this.value)) {
            other.prev.add(this);
        } else if (a_before_b(other.value, this.value) || b_before_a(this.value, other.value)) {
            this.prev.add(other);
        }
    }
    setOrder(path = new Set) {
        // Use recursion to find length of longest path to "least" node.
        if (this.order) return; // already done
        if (path.has(this)) throw "cycle detected";
        let order = 1;
        for (let prev of this.prev) {
            prev.setOrder(path.add(this));
            order = Math.max(order, prev.order + 1);
        }
        this.order = order; // If order is 1, it is a "least" node
    }
}

const a_before_b = (a, b) => {
  if (a == 'a' && b == 'd') return true;
  if (a == 'b' && b == 'c') return true;
}

const b_before_a = (a, b) => {
  if (b == 'a' && a == 'c') return true;
  if (b == 'b' && a == 'c') return true;
}

function mySort(arr) {
    // Create a graph: first the nodes
    let nodes = {}; // keyed by values in arr
    for (let value of arr) nodes[value] = nodes[value] || new Node(value);

    // Then the edges...
    for (let i = 0; i < arr.length; i++) {
        for (let j = i+1; j < arr.length; j++) {
            nodes[arr[i]].orderWith(nodes[arr[j]]);
        }
    }
    
    // Set absolute order, using the longest path from a node to a "least" node.
    for (let node of Object.values(nodes)) node.setOrder();
    
    // Sort array by order:
    return arr.sort((a, b) => nodes[a].order - nodes[b].order);
}

const sorted = ['a', 'b', 'c', 'd'];
const unsorted = ['c', 'd', 'a', 'b'];
console.log(mySort(unsorted));

这篇关于如何根据不完整的标准排序?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！