代码之家 › 专栏 › 技术社区 › Chris

Javascript按最短步骤排序数组

shortest sorting arrays javascript

0

Chris · 技术社区 · 4 年前

这是仓库过道/行/架的问题。顺着过道往下看,我左边有第6排,右边有第5排。

我需要以最少的步骤访问机架列表。以下是一组行和机架:

[   
    {"rowIndex": 5, "rowRackIndexActual": 1},
    {"rowIndex": 5, "rowRackIndexActual": 3},
    {"rowIndex": 5, "rowRackIndexActual": 4},
    {"rowIndex": 6, "rowRackIndexActual": 5},
    {"rowIndex": 6, "rowRackIndexActual": 6},
    {"rowIndex": 5, "rowRackIndexActual": 6},
    {"rowIndex": 5, "rowRackIndexActual": 7},
    {"rowIndex": 6, "rowRackIndexActual": 8},
    {"rowIndex": 5, "rowRackIndexActual": 8},
    {"rowIndex": 6, "rowRackIndexActual": 9}
]

输出应该从下到上如下所示:

(step 9) row 6, rack 9  |  
(step 8) row 6, rack 8  + row 5, rack 8 (step 7)
                        | row 5, rack 7 (step 6)
                        / row 5, rack 6 (step 5)
(step 4) row 6, rack 5  \
                        | row 5, rack 4 (step 3)
                        | row 5, rack 3 (step 2)
                        | row 5, rack 1 (step 1)

此问题与出现在两行中的机架8有关。我的排序是先选择左边一行,但最短的一步实际上是向上移动一步,因为我的最后一个架子在第5行(右边一行)——在这种情况下是第7步;

很明显,我需要跟踪一行何时发生变化——当我们向左或向右移动时。以下是我迄今为止的分类陈述:

        let prevRow = aisleRackArr[0].rowIndex; // the first item in the array
        aisleRackArr.sort(function(a, b) {
            console.log(a.rowIndex, a.rowRackIndexActual, b.rowIndex, b.rowRackIndexActual, prevRow);
            if (a.rowRackIndexActual === b.rowRackIndexActual) {
                console.log(`got the same rowRackIndex`);
                if (a.rowIndex === prevRow) {
                    console.log(`a should come first`);
                    return 0;
                } else {
                    console.log(`a came second`);
                    return 1;
                }
            }
            prevRow = b.rowIndex;
            return 0;
        });

以下是排序函数(a.row、a.rack、b.row、b.rack、prevRow)的输出:

5 3 5 1 5
5 4 5 3 5
6 5 5 4 5
5 6 6 5 5
5 7 5 6 6
6 8 5 7 5
5 8 6 8 5 <---------- not returning a even though a.row===prevRow
got the same rowRackIndex
a should come first
6 9 5 8 5

乍一看,我们似乎可以简单地按rackIndex和rowIndex进行排序。然而,当我们需要在左一行向上移动,并且接下来的两个机架是相同的索引时,这并不能解释这种情况。

我能做些什么来解决这个问题?

编辑以下是它的外观图片:

0 回复 | 直到 4 年前

1

0

zer00ne 4 年前

好吧,不管机架号如何,下面的例子都是一个不可知的解决方案——一个可重复使用的函数,它将获取一个对象数组,并根据主要属性(“机架”)的值对对象进行排序,如果它们恰好相等,则将根据次要属性(“行”)的价值进行比较:

a[primary] - b[primary] || a[secondary] - b[secondary]

即:

{row: 6 rack: 8} - {row:5, rack: 8} OR {row: 6 rack: 8} - {row:5, rack: 8}
//           â¬ï¸ This equals out â¬ï¸ âï¸      â¬ï¸  row: 5 first  â¬ï¸

以下示例对详细信息进行了评论

// Mixed order to really test capability
const rowRack = [   
  {"row": 5, "rack": 1},  
  {"row": 6, "rack": 9},  
  {"row": 5, "rack": 3},
  {"row": 5, "rack": 4},
  {"row": 6, "rack": 5},
  {"row": 5, "rack": 7},
  {"row": 6, "rack": 8},
  {"row": 5, "rack": 8},
  {"row": 5, "rack": 6},
  {"row": 5, "rack": 2}
];
/**
* Given an array of objects (objectArray), it will sort each object by the
* first given property's (primary) value. If there is a value that equals
* another value, the second given property's (secondary) value will be 
* compared to each other.
* @param {array<object>} objectArray - An array of object literals
* @param {string} primary - The property's value to compare with.
* @param {string} secondary - The property's value to compare with if the 
*                             primary values are equal. 
* @return {array<object>}
*/  

const route = (objectArray, primary, secondary) => {
  return objectArray.sort((a, b) => 
    a[primary] - b[primary] || a[secondary] - b[secondary]);
};
  
console.log(route(rowRack, "rack", "row"));

.as-console-row::after { width: 0; font-size: 0; }
.as-console-row-code { width: 100%; word-break: break-word; }
.as-console-wrapper { min-height: 100% !important; max-width: 30%; margin-left: 70%; }

<pre>
(step 9) row 6, rack 9  |  
(step 8) row 6, rack 8  + row 5, rack 8 (step 7)
                        | row 5, rack 7 (step 6)
                        / row 5, rack 6 (step 5)
(step 4) row 6, rack 5  \
                        | row 5, rack 4 (step 3)
                        | row 5, rack 3 (step 2)
                        | row 5, rack 2 (step 1)
                        | row 5, rack 1 (step 0)
</pre>

2

0

Chris 4 年前

正如我所怀疑的那样,我需要跟踪当前的争吵。由于我们可以向上移动一行或向下移动一行,因此每行中的每个机架都被赋予了两个索引,如果选择了通道中的每个货架,则这两个索引表示通过通道的最佳路线。“向下”索引与“向上”索引不是相反的。当向下移动一排时,第一个支架将在您的左侧。当向上移动一排时,第一个支架将在您的右侧。然后,向上移动行时按over/up/over分配索引,向下移动时按over/down/over分配索引。

我们提取我们的选择列表——一个订单中所有项目的数组,其中还包含可以找到产品的行和架——并提取出独特的通道。

以下是选择列表中的示例记录:

{
    "idorder": 527261,
    "orderIndex": 3,
    "sku": "WZH76-4-W-YRS-PKP-XL",
    "upc": "195041059206",
    "quantity": 1,
    "warehouse": 10,
    "zone": 10,
    "row": "20",
    "rack": 20,
    "tier": 1,
    "shelf": 2,
    "bin": 5,
    "rowNorm": "000020",
    "aisleNum": 1,
    "rowIndex": 2,
    "rowRackIndex": 2,
    "rowRackIndexActual": 2,
    "revRowRackIndexActual": -2,
    "ecFactor": 0,
    "aisleMaxRackIndex": 10,
    "aisleRackIndex": 3,
    "reverseAisleRackIndex": 16,
    "rackCode": "10-10-20-20"
  }

从整个选择列表中,我们可以获得独特的通道:

uniqueAisles = [...new Set(pickListArr.map((a) => a.aisleNum))].keySort({aisleNum: `asc`});

然后,我们在过道中循环,从挑选列表中选择与当前过道匹配的每一种产品:

sarr = [];
aisleRackArr = pickListArr.filter((r) => r.aisleNum === aa);

然后通过获得该通道的独特机架,再次完善我们的aisleRackArray:

aisleRackArr = [...new Map(aisleRackArr.map((item) => [item.aisleRackIndex, item])).values()];

然后我们弄清楚我们要往哪个方向走:向上还是向下。这与本次讨论无关,因此我们将跳过它。

一旦我们知道了我们的前进方向,我们就会根据订单选择列表中的向上或向下索引,对行中的每个选定机架进行粗略排序:

if (curDir === `up`) {
    aisleRackArr.keySort({rowRackIndexActual: `asc`, rowindex: `desc`});
} else {
    aisleRackArr.keySort({revRowRackIndexActual: `asc`, rowIndex: `asc`});
}

根据以上分类,我们知道我们的第一个机架,也知道我们要朝哪个方向发展。

const dirFactor = curDir === `up`?1 : -1;
curRack = aisleRackArr[0];

让我们取第一条记录,并将其推送到临时排序数组(sarr)中

sarr.push({rowIndex: curRack.rowIndex, rackIndex: curRack.rowRackIndexActual, aisleNum: curAisleNum, aisleSort: +(+(+curRack.rowRackIndex * 10)) * (+dirFactor), rackCode: curRack.rackCode});

然后将其从我们的过道机架阵列中移除:

aisleRackArr.splice(0, 1);

现在,我们将循环浏览通道机架阵列中的剩余记录,寻找我们应该移动到的下一个机架:

while (aisleRackArr.length > 0) {
    curRack = getNextRack(aisleRackArr, dirFactor, curRack.rowIndex);

一旦我们知道我们的下一个机架,将其推入临时阵列,然后将其从机架阵列中移除:

    sarr.push({rowIndex: curRack.rowIndex, rackIndex: curRack.rowRackIndexActual, aisleNum: curAisleNum, aisleSort: curRack.sorter, rackCode: curRack.rackCode});
    const curIndex=aisleRackArr.indexOf(curRack);
    aisleRackArr.splice(curIndex, 1);

并继续循环;

完成循环后,将整个临时数组推入主路由数组:

mapRouteArr.push(...sarr);

确定下一个机架的代码:

我们需要获得数组中的下三条记录,因为这些记录将包含我们下一步可以执行的每一步:向左移动、向右移动或向上移动。一旦我们有了这三条记录,我们就会根据机架索引(我们所在行的上下距离)以及其中一条或多条记录是否在我们当前所在的同一行(左或右)来分配新的排序顺序。我们将根据该标准对这三条记录进行排序。如果其中两个机架位于同一级别,请优先选择当前行中的机架。

然后返回该行,while循环将其存储在temp排序数组中,然后将其从混合中删除。

我们继续,直到机架阵列为空。

function getNextRack(rackArray, dirFactor, curRow) {
    next3Arr = rackArray.slice(0, 4);

    if (dirFactor === 1) { // going up!
        next3Arr.forEach((a) => {
            a.sorter = +(+(+a.rowRackIndexActual * 10) + (+curRow === +a.rowIndex ? 0 : 1));
            a.currentRow = curRow;
        });
        return next3Arr.sort((a, b)=> a.sorter-b.sorter)[0];
    } else { // going down!
        next3Arr.forEach((a) => {
            a.sorter = +((+a.rowRackIndexActual) * -10) - (+curRow === +a.rowIndex ? 1 : 0);
            a.currentRow = curRow;
        });
        return next3Arr.sort((a, b) => a.sorter - b.sorter)[0];
    }
}

我的测试用例使用了10个订单,导致47个不同的机架需要访问。排序结果如下所示。此数组考虑了所有可能的左/右、上/下和不同行长的情况,并且正是它应该的方式:

[
    {
        "rowIndex": 2,
        "rackIndex": 2,
        "aisleNum": 1,
        "aisleSort": 20,
        "rackCode": "10-10-20-20"
    },
    {
        "rowIndex": 1,
        "rackIndex": 6,
        "aisleNum": 1,
        "aisleSort": 61,
        "rackCode": "10-10-10-70"
    },
    {
        "rowIndex": 1,
        "rackIndex": 8,
        "aisleNum": 1,
        "aisleSort": 80,
        "rackCode": "10-10-10-90"
    },
    {
        "rowIndex": 2,
        "rackIndex": 9,
        "aisleNum": 1,
        "aisleSort": 91,
        "rackCode": "10-10-20-90"
    },
    {
        "rowIndex": 3,
        "rackIndex": 9,
        "aisleNum": 2,
        "aisleSort": -100,
        "rackCode": "10-10-30-90"
    },
    {
        "rowIndex": 3,
        "rackIndex": 8,
        "aisleNum": 2,
        "aisleSort": -81,
        "rackCode": "10-10-30-80"
    },
    {
        "rowIndex": 4,
        "rackIndex": 8,
        "aisleNum": 2,
        "aisleSort": -80,
        "rackCode": "10-10-40-80"
    },
    {
        "rowIndex": 4,
        "rackIndex": 7,
        "aisleNum": 2,
        "aisleSort": -71,
        "rackCode": "10-10-40-70"
    },
    {
        "rowIndex": 4,
        "rackIndex": 4,
        "aisleNum": 2,
        "aisleSort": -41,
        "rackCode": "10-10-40-40"
    },
    {
        "rowIndex": 3,
        "rackIndex": 0,
        "aisleNum": 2,
        "aisleSort": 0,
        "rackCode": "10-10-e4-10"
    },
    {
        "rowIndex": 5,
        "rackIndex": 1,
        "aisleNum": 3,
        "aisleSort": 20,
        "rackCode": "10-10-50-10"
    },
    {
        "rowIndex": 5,
        "rackIndex": 3,
        "aisleNum": 3,
        "aisleSort": 30,
        "rackCode": "10-10-50-30"
    },
    {
        "rowIndex": 5,
        "rackIndex": 4,
        "aisleNum": 3,
        "aisleSort": 40,
        "rackCode": "10-10-50-40"
    },
    {
        "rowIndex": 6,
        "rackIndex": 5,
        "aisleNum": 3,
        "aisleSort": 51,
        "rackCode": "10-10-60-50"
    },
    {
        "rowIndex": 6,
        "rackIndex": 6,
        "aisleNum": 3,
        "aisleSort": 60,
        "rackCode": "10-10-60-60"
    },
    {
        "rowIndex": 5,
        "rackIndex": 6,
        "aisleNum": 3,
        "aisleSort": 61,
        "rackCode": "10-10-50-60"
    },
    {
        "rowIndex": 5,
        "rackIndex": 7,
        "aisleNum": 3,
        "aisleSort": 70,
        "rackCode": "10-10-50-70"
    },
    {
        "rowIndex": 5,
        "rackIndex": 8,
        "aisleNum": 3,
        "aisleSort": 80,
        "rackCode": "10-10-50-80"
    },
    {
        "rowIndex": 6,
        "rackIndex": 8,
        "aisleNum": 3,
        "aisleSort": 81,
        "rackCode": "10-10-60-80"
    },
    {
        "rowIndex": 6,
        "rackIndex": 9,
        "aisleNum": 3,
        "aisleSort": 90,
        "rackCode": "10-10-60-90"
    },
    {
        "rowIndex": 7,
        "rackIndex": 9,
        "aisleNum": 4,
        "aisleSort": -100,
        "rackCode": "10-10-70-90"
    },
    {
        "rowIndex": 8,
        "rackIndex": 8,
        "aisleNum": 4,
        "aisleSort": -80,
        "rackCode": "10-10-80-80"
    },
    {
        "rowIndex": 7,
        "rackIndex": 4,
        "aisleNum": 4,
        "aisleSort": -40,
        "rackCode": "10-10-70-40"
    },
    {
        "rowIndex": 9,
        "rackIndex": 2,
        "aisleNum": 5,
        "aisleSort": 30,
        "rackCode": "10-10-90-20"
    },
    {
        "rowIndex": 10,
        "rackIndex": 3,
        "aisleNum": 5,
        "aisleSort": 31,
        "rackCode": "10-10-100-30"
    },
    {
        "rowIndex": 10,
        "rackIndex": 7,
        "aisleNum": 5,
        "aisleSort": 70,
        "rackCode": "10-10-100-70"
    },
    {
        "rowIndex": 11,
        "rackIndex": 8,
        "aisleNum": 6,
        "aisleSort": -90,
        "rackCode": "10-10-110-80"
    },
    {
        "rowIndex": 11,
        "rackIndex": 7,
        "aisleNum": 6,
        "aisleSort": -71,
        "rackCode": "10-10-110-70"
    },
    {
        "rowIndex": 12,
        "rackIndex": 7,
        "aisleNum": 6,
        "aisleSort": -70,
        "rackCode": "10-10-120-70"
    },
    {
        "rowIndex": 12,
        "rackIndex": 5,
        "aisleNum": 6,
        "aisleSort": -51,
        "rackCode": "10-10-120-50"
    },
    {
        "rowIndex": 11,
        "rackIndex": 4,
        "aisleNum": 6,
        "aisleSort": -40,
        "rackCode": "10-10-110-40"
    },
    {
        "rowIndex": 12,
        "rackIndex": 3,
        "aisleNum": 6,
        "aisleSort": -30,
        "rackCode": "10-10-120-30"
    },
    {
        "rowIndex": 11,
        "rackIndex": 2,
        "aisleNum": 6,
        "aisleSort": -20,
        "rackCode": "10-10-110-20"
    },
    {
        "rowIndex": 11,
        "rackIndex": 1,
        "aisleNum": 6,
        "aisleSort": -11,
        "rackCode": "10-10-110-10"
    },
    {
        "rowIndex": 12,
        "rackIndex": 1,
        "aisleNum": 6,
        "aisleSort": -10,
        "rackCode": "10-10-120-10"
    },
    {
        "rowIndex": 13,
        "rackIndex": 2,
        "aisleNum": 7,
        "aisleSort": 30,
        "rackCode": "10-10-130-20"
    },
    {
        "rowIndex": 13,
        "rackIndex": 4,
        "aisleNum": 7,
        "aisleSort": 40,
        "rackCode": "10-10-130-40"
    },
    {
        "rowIndex": 13,
        "rackIndex": 6,
        "aisleNum": 7,
        "aisleSort": 60,
        "rackCode": "10-10-130-60"
    },
    {
        "rowIndex": 15,
        "rackIndex": 6,
        "aisleNum": 8,
        "aisleSort": -70,
        "rackCode": "10-10-150-60"
    },
    {
        "rowIndex": 16,
        "rackIndex": 6,
        "aisleNum": 8,
        "aisleSort": -60,
        "rackCode": "10-10-160-60"
    },
    {
        "rowIndex": 15,
        "rackIndex": 5,
        "aisleNum": 8,
        "aisleSort": -50,
        "rackCode": "10-10-150-50"
    },
    {
        "rowIndex": 15,
        "rackIndex": 4,
        "aisleNum": 8,
        "aisleSort": -41,
        "rackCode": "10-10-150-40"
    },
    {
        "rowIndex": 15,
        "rackIndex": 3,
        "aisleNum": 8,
        "aisleSort": -31,
        "rackCode": "10-10-150-30"
    },
    {
        "rowIndex": 16,
        "rackIndex": 2,
        "aisleNum": 8,
        "aisleSort": -20,
        "rackCode": "10-10-160-20"
    },
    {
        "rowIndex": 15,
        "rackIndex": 1,
        "aisleNum": 8,
        "aisleSort": -10,
        "rackCode": "10-10-150-10"
    },
    {
        "rowIndex": 17,
        "rackIndex": 2,
        "aisleNum": 9,
        "aisleSort": 20,
        "rackCode": "10-10-170-20"
    },
    {
        "rowIndex": 17,
        "rackIndex": 3,
        "aisleNum": 9,
        "aisleSort": 30,
        "rackCode": "10-10-170-30"
    }
]

EC机架是端盖,它们属于奇数排——从过道上看,右边的几排。整个排序中的第一个货架是红色的。使用这个起点并按照上面的数组,我们现在可以找到最短的路径来挑选一组订单。

注意:当我们完成一个通道时,有时下一个通道中最近的机架会在我们身后。以下是确定下一个过道中最近机架的计算,这是必须在当前通道中转身才能移动到下一个最近机架的因素:

if (curDir === `up`) {
    x = reverseMinRack.reverseAisleRackIndex + previousReverseAisleRackIndex + curDir === `up` ? 0 : 1;// +1 accounts for having to turn around
    y = minRack.aisleRackIndex + previousAisleRackIndex + curDir === `down` ? 0 : 1; // +1 accounts for having to turn around
}
if (x === y) {
    curDir = curDir === `up` ? `down` : `up`;
}
if (x < y) {
    curDir = `down`;
}
if (x > y) {
    curDir = `up`;
}