合并具有相似值的数组，保持值内部的顺序

Question

这是一个我今天遇到的有趣任务，我想不到任何简单的方法来实现所需结果。

假设我们有一个包含以下字段（列）的数据库：A、B、C、D、E、F、G，但是我们不知道这些字段的名称或数量。

我们从该数据库接收一组记录，格式如下：{A:value1, B:value2, ...}。

如果当前记录未设置值，则键也将丢失。这意味着我可以接收{A:value}或{C:value1, D:value2}等有效记录。密钥的顺序总是保持不变。这意味着{D:value，C:value}不是有效记录。

我正在尝试根据返回的记录恢复字段名称并保留密钥的顺序。

例如，我可以接收带有以下密钥的记录：

A、C、D、E、F

D、F、G

A、B、F

从上面的示例中，我应该能够恢复原始的序列，即A、B、C、D、E、F、G。

第一条记录给了我们A、C、D、E和F。

第二个告诉我们G在F之后，所以现在我们有A、C、D、E、F、G。

第三个记录给出B在A之后，所以现在我们有A、B、C、D、E、F、G。

如果确定不了顺序，我们可以使用字母顺序。例如：

A、B

A、C

在上面的示例中，我们无法确定原始顺序是A、B、C还是A、C、B。

有什么想法可以实现这个通用案例吗？

我将使用JavaScript实现此算法，但PHP、C ++或Java也可以。

• 创建一个对象，包含所有关系 - 每个数据库记录中的哪个列在哪个列之后。
• 创建每个a-b、b-c之间关系的关系 => a-c（受Floyd-Warshall启发，如果存在，则将每个距离视为1）。
• 创建一个排序函数（比较器），检查两个元素是否可以进行比较。如果不行 - 将使用字母顺序。
• 仅获取唯一的列名，并使用比较器函数对它们进行排序。

您可以在下面找到附加的源代码:

var allComparators = {};
var knownObjects = ['A,C,D,E,F','D,F,G','A,B,F'];
var allFields = knownObjects.join(',').split(',');

for (var i in knownObjects) {
    var arr = knownObjects[i].split(',');
    for (var i = 0; i < arr.length; i++) {
        for (var j = i + 1; j < arr.length; j++) {
            allComparators[arr[i]+'_'+arr[j]] = 1;
        }
    }
}

allFields = allFields.filter(function(value, index, self) { 
    return self.indexOf(value) === index;
});

for (var i in allFields) {
    for (var j in allFields) {
        for (var k in allFields) {
            if (allComparators[allFields[i]+'_'+allFields[j]] && allComparators[allFields[j]+'_'+allFields[k]]) {
                allComparators[allFields[i]+'_'+allFields[k]] = 1;
            }
        }
    }
}

allFields.sort(function(a, b) {
    if (typeof allComparators[a + '_' + b] != 'undefined') {
        return -1;
    }
    if (typeof allComparators[b + '_' + a] != 'undefined') {
        return 1;
    }
    return a > b;
});

console.log(allFields);

- Дамян Станчев

---

一个对象（字典）没有顺序！ - Amine Hajyoussef

你是在谈论数组还是对象？ - Christopher Chiche

你可以看到我所做的修改。 - Дамян Станчев

你应该将你想出的解决方案作为答案发布，而不是问题的一部分。如果其他答案有帮助的话（或者你使用了其他资源），不要忘记给予信用。 - Tibos

确实，您可以在A和F之间的任何位置放置B，因为除非您将新约束强加到问题中，否则没有任何规定必须在C之前。 - Mohsen Kamrani

Answer 1

你觉得像这样的东西会起作用吗？

var oMergedList = [];

function indexOfColumn(sColumnName)
{
    for(var i = 0 ; i < oMergedList.length;i++)
        if(oMergedList[i]==sColumnName)
            return i;
    return -1;
}
function getOrdinalIndex(sColumnName)
{
    var i = 0;
    for( ; i < oMergedList.length;i++)
        if(oMergedList[i]>sColumnName)
            break;
    return i;
}

function merge(oPartial)
{
    var nPreviousColumnPosition = -1;
    for(var i = 0 ; i < oPartial.length;i++)
    {
        var sColumnName =  oPartial[i] ;
        var nColumnPosition = indexOfColumn(sColumnName);
        if(nColumnPosition>=0)//already contained
        {
            if(nPreviousColumnPosition>=0 && nColumnPosition!=(nPreviousColumnPosition+1))//but inserted on wrong place
            {
                oMergedList.splice(nColumnPosition, 1);
                nColumnPosition = nPreviousColumnPosition
                 oMergedList.splice(nColumnPosition, 0, sColumnName);
            }
            nPreviousColumnPosition = nColumnPosition;
        }
        else //new
        {
            if(nPreviousColumnPosition<0)//no reference column
            {
                nPreviousColumnPosition = getOrdinalIndex(sColumnName);
            }
            else// insert after previous column
                nPreviousColumnPosition++;
            oMergedList.splice(nPreviousColumnPosition, 0, sColumnName);
        }

    }
}
/* latest sample
merge(['A','C','E','G']);
merge(['A','D']);
merge(['C','D']);
*/
/* default sample
merge(['A','C','D','E','F']);
merge(['D','F','G']);
merge(['A','B','F']);
*/
/* fix order
merge(['A','B']);
merge(['A','C']);
merge(['A','B','C']);
*/
/* insert alphabetically
merge(['B']);
merge(['A']);
merge(['C']);
*/
document.body.innerHTML = oMergedList.join(',');

唯一的“未定义”部分是如果没有先前的列要插入的位置（我把它放在了第一位），而在A、B.. A、C的情况下，当首次出现时将插入列。

意味着A、B..A、C会给出A、C、B..，意味着A、C..A、B会给出A、B、C。

---

编辑使用当前数组位置修复以前的加法，因此如果您添加 [A,C][A,B]，您将获得 [A,C,B]，但是如果您传递 [A,B,C]，则数组将被修复以反映新顺序。

此外，当出现新列且没有参考列附加时，按字母顺序附加。

---

修复了列校正参数，现在应该能够给出正确的结果。

- CaldasGSM

---

在这种情况下，这将失败：merge（['A'，'C'，'E'，'G']）; merge（['A'，'D']）; merge（['C'，'D']）; C在D之后，但D是在A之后插入的。+1为你的努力 :) - Дамян Станчев

Answer 2

我会用简明易懂的方式给出算法，但是代码！请自己尝试编写，如果需要帮助可以寻求帮助。 我有两种表达方式。

在技术术语方面： 1. 生成一个优先级图（即有向图） 2. 对其进行拓扑排序。

---

更详细的解释如下：

图：Map(String, ArrayList< String >) = [Map(key,value)]
地图中的每个键对应一个元素（A、B、C等）
每个值包含应该放置在该键后面的元素，例如对于A，它是{B、C、D等}
如何填充图：

对于每一行：
 对于行内的每个元素：
  如果该元素已经作为地图中的键，则将其紧接着的下一个项添加到列表中*
  否则，将该元素添加到地图中，并将值设置为它的下一个元素**

*如果该元素是该行中的最后一个元素，则不要向地图中添加任何内容
**如果该元素是该行中的最后一个元素，请使用{}作为空列表的值

拓扑排序：

List sortedList;
对于地图中的每个键：
  如果value.size() == 0 {
    从地图中删除key
    将key添加到sortedList中
    对于地图中的每个键'：
      如果value'.contains(key)
        value'.remove(key) （并更新地图）
  }
反转sortedList

---

测试用例：

你的第一个输入地图如下：
{ A:{C,B} , C:{D} , D:{E,F} , E:{F} , F:{G} , G:{} , B:{F} }
排序：
1 - G -> 排序列表， 地图= { A:{C,B} , C:{D} , D:{E,F} , E:{F} , F:{} , B:{F} }
2 - F -> 排序列表， 地图= { A:{C,B} , C:{D} , D:{E} , E:{} , B:{} }
3 - E -> 排序列表， 地图= { A:{C,B} , C:{D} , D:{} }
4 - D -> 排序列表， 地图= { A:{C,B} , C:{} }
5 - C -> 排序列表， 地图= { A:{B} , B:{} }
6 - B -> 排序列表， 地图= { A:{} }
6 - A -> 排序列表， 地图= { }
排序列表 = {G,F,E,D,C,B,A}
反转 - > {A,B,C,D,E,F,G}

- Mohsen Kamrani

---

嗨mok，我看到你对算法有很强的了解。你能否检查一下我刚刚在原始问题中添加的解决方案，并告诉我是否能够发现其中的任何弱点？我正在创建一个类似于你的图形，并将其用作JS排序的比较器。谢谢。 - Дамян Станчев

谢谢。我会做，但是你有什么问题吗？还是只是想改进它？ - Mohsen Kamrani

我只是不确定三个嵌套的for循环是否能涵盖所有情况，当比较a和d时，我可能会在一些测试中失败，例如a>b，b>c，c>d。在这个例子中它运行良好，但我不能说它在一般情况下百分之百有效。这是我现在唯一的担忧。我找到了一个优化并更新了我的第一篇帖子 - 如果在三个嵌套循环之前过滤变量，则可以获得更好的性能。 - Дамян Станчев

@mok 太棒了！省去了我数小时的头痛。优美的解决方案，演示清晰明了 - 谢谢！ - randomsock

Answer 3

根据JSON.org所述，Json没有有序键：

对象是一组无序的名称/值对。

因此，合并对象变得非常容易，因为您不需要顺序。

for (var attrname in obj2) { obj1[attrname] = obj2[attrname]; }

来源：如何动态合并两个JavaScript对象的属性？

- Christopher Chiche