java - 如何按最接近的值排序列表

Question

所以我有如下代表仓库位置的小列表:

30 09 05
30 04 05
30 02 01 
31 07 05 
31 07 04 
31 03 05 
31 03 06 
31 09 05 
31 02 05 

第一列代表位置行，第二列代表位置高度，第三列代表位置位置(向前)

我需要计算叉车运算符(operator)根据不同位置检索不同元素的最佳路径(行、位置、高度)

为此，我使用 Collection.sort 对列表进行排序，首先按行排序，然后按位置(向前)，最后按高度排序。

行成对分组，因为运算符(operator)可以在不移动叉车位置和高度的情况下从偶数行(运算符(operator)左)和奇数行(运算符(operator)右)取回元素

我快到了，我只需要一只手，当 pos 向前移动时，我需要保持相同的高度并获得最近的高度，而不是从底部开始，这会使运算符(operator)浪费时间上下移动

代码如下:

Collections.sort(unoptimizedLocations, new Comparator<ItemOrderLocation>() {
    @Override
    public int compare(ItemOrderLocation item1, ItemOrderLocation item2) {

        int rowCmp = item1.row.compareTo(item2.row);
        int heightCmp = item1.height.compareTo(item2.height);
        int posCmp = item1.pos.compareTo(item2.pos);

        int item1Row = Integer.parseInt(item1.row);
        int item2Row = Integer.parseInt(item2.row);

        boolean onForkLiftPath = false;

        if (item1Row == (item2Row + 1) && (item2Row % 2 == 0)) {
            onForkLiftPath = true;
        }

        if (!onForkLiftPath && rowCmp != 0) {
            //Two differents rows which are not on Fork Lift Path
            return rowCmp;
        }

        //If are on forklift path we compare the position
        if (posCmp != 0) {
            return posCmp;
        }

        //Lastly if row is on forklift path and we are on same position we need to sort by nearest height
        return heightCmp;
    }
});

使用此代码，列表将按如下方式排序:

30 02 01 
31 07 04 
31 02 05 
31 03 05 
30 04 05 
31 07 05 
30 09 05 
31 09 05 
31 03 06

为了更好地理解最终的排序列表(最近的高度用于较少的高度行进)应该如下所示:

30 02 01 
31 07 04
31 07 05 
30 09 05
31 09 05 
30 04 05
31 03 05    
31 02 05
31 03 06 

有什么想法可以使用我的排序算法达到这个结果吗？

Answer 1

在给定约束的情况下，以下解决叉车问题。

ALGORITHM
Input:  All locations
Output:  Shortest path given constraints
1.  For all row/pairs, in increasing order
2.  For all positions in that row, in increasing order
3.  For all heights with same row/pair and position, add locations to minimize the height change given a starting height

该代码使用 Java 8 流。该代码尝试使用单一用途的方法；所以请随意用更熟悉的语法重写任何方法。它不能保证被优化，但考虑到输入的小尺寸，这不应该是一个问题。如果您有任何问题，请告诉我。

还有代码:

public class ForkLiftOperator {

public static void main(String[] args) {
    new ForkLiftOperator().start();
}

private void start() {

    List<Location> locations = new ArrayList<Location>();
    locations.add(new Location(30, 9, 5));
    locations.add(new Location(30, 4, 5));
    locations.add(new Location(30, 2, 1));
    locations.add(new Location(31, 7, 5));
    locations.add(new Location(31, 7, 4));
    locations.add(new Location(31, 3, 5));
    locations.add(new Location(31, 3, 6));
    locations.add(new Location(31, 9, 5));
    locations.add(new Location(31, 2, 5));
    locations.add(new Location(32, 2, 5));  // Extra to simulate additional row/pair

    List<Location> solution = solve(locations);
    System.out.println(solution);
}


private List<Location> solve(List<Location> locations) {

    List<Location> shortestPath = new ArrayList<Location>();
    int activeRow, activePosition, activeHeight;
    while ((activeRow = getNextRow(locations)) != 0) {
        System.out.println("Working on row="+activeRow);
        List<Location> activeLocations = getLocationsByRowPair(activeRow, locations);
        activePosition = 0;
        activeHeight = 0;
        while ((activePosition = getNextPos(activePosition, activeLocations)) != 0) {
            System.out.println("Working on pos="+activePosition);
            List<Location> activePositionLocations = getLocationsForRowAndPosition(activeRow, activePosition, activeLocations);
            shortestPath.addAll(minimizeHeight(activeHeight, activePositionLocations));
            activeHeight = shortestPath.get(shortestPath.size()-1).height;
        }
    }


    return shortestPath;
}

enum Direction { UP, DOWN }
/**
 * For the given locations (which are guaranteed to be at the same row/position), minimize the total height change
 * @param activePositionLocations The locations at this row/pair and location (they will only differ in height)
 * @return The order will minimize the height change
 */
private List<Location> minimizeHeight(int currentHeight, List<Location> activePositionLocations) {
    List<Location> optimizedHeightLocations = new ArrayList<Location>();
    System.out.println("Processing locations="+activePositionLocations);
    int minHeight = activePositionLocations.stream().mapToInt(location -> location.height).min().getAsInt();
    int maxHeight = activePositionLocations.stream().mapToInt(location -> location.height).max().getAsInt();
    /*
     * There are only two options to minimize (if the current height falls between min and max):
     * 1)  Travel down then up
     * 2)  Travel up then down
     */
    // First determine the first direction to go
    Direction direction;
    if (currentHeight == minHeight)
        direction = Direction.UP;
    else if (currentHeight == maxHeight)
        direction = Direction.DOWN;
    else {
        int distanceUp = maxHeight-currentHeight;
        int distanceDown = currentHeight-minHeight;
        direction = distanceUp < distanceDown ? Direction.UP : Direction.DOWN;
    }
    // Now travel in that direction (must sort the correct way first
    List<Location> sortedAscending = activePositionLocations.stream().sorted((l1, l2) -> Integer.compare(l1.height, l2.height)).collect(Collectors.toList());
    List<Location> sortedDescending = activePositionLocations.stream().sorted((l1, l2) -> Integer.compare(l2.height, l1.height)).collect(Collectors.toList());
    if (direction == Direction.UP) {
        optimizedHeightLocations.addAll(sortedAscending.stream().filter(location -> location.height >= currentHeight).collect(Collectors.toList()));
        optimizedHeightLocations.addAll(sortedDescending.stream().filter(location -> location.height < currentHeight).collect(Collectors.toList()));
    } else {    // Direction = DOWN
        optimizedHeightLocations.addAll(sortedDescending.stream().filter(location -> location.height <= currentHeight).collect(Collectors.toList()));
        optimizedHeightLocations.addAll(sortedAscending.stream().filter(location -> location.height > currentHeight).collect(Collectors.toList()));
    }

    return optimizedHeightLocations;
}

/**
 * Determine all the locations for this current row/pair and position
 * @param activeRow The current row/pair
 * @param activePos The current position
 * @param locations The locations for this row/pair
 * @return The locations at this exact row/pair and position
 */
private List<Location> getLocationsForRowAndPosition(int activeRow, int activePos,
        List<Location> locations) {
    int minRow = activeRow;
    int maxRow = ((activeRow & 1) == 0) ? activeRow + 1 : activeRow;    // If even, then pair includes the next higher row
    return locations.stream().filter(location -> location.row >= minRow && location.row <= maxRow && location.position == activePos)
            .collect(Collectors.toList());
}

/**
 * Determine the next position, given the current position
 * @param currentPosition Where the operator is currently
 * @param locations The locations for this row/pair
 * @return The next closest, or zero if they are at the end
 */
private int getNextPos(int currentPosition, List<Location> locations) {
    if (locations.isEmpty())
        return 0;
    OptionalInt min = locations.stream().filter(location -> location.position > currentPosition)
            .mapToInt(location -> location.position)
            .min(); 
    return min.isPresent() ? min.getAsInt() : 0;
}

/**
 * Filter out any locations for this row pair.
 * The locations for this row will be removed from the original list
 * @param nextRow The current row being processed
 * @param locations The remaining locations
 * @return The locations for the active row
 */
private List<Location> getLocationsByRowPair(int nextRow, List<Location> locations) {
    List<Location> activeLocations = new ArrayList<Location>();
    Iterator<Location> i = locations.iterator();
    int minRow = nextRow;
    int maxRow = ((nextRow & 1) == 0) ? nextRow + 1 : nextRow;  // If even, then pair includes the next higher row
    while (i.hasNext()) {
        Location current = i.next();
        if (current.row >= minRow && current.row <= maxRow) {
            activeLocations.add(current);
            i.remove();
        }
    }
    return activeLocations;
}

/**
 * Determine the lowest row from the locations provided
 * @param locations All remaining locations
 * @return The minimum row number remaining
 */
private int getNextRow(List<Location> locations) {
    if (locations.isEmpty())
        return 0;
    return locations.stream().mapToInt(location -> location.row)
            .min().getAsInt();
}

class Location {
    final int row;
    final int position;
    final int height;
    public Location(int row, int height, int position) {
        this.row = row;
        this.position = position;
        this.height = height;
    }
    @Override
    public String toString() {
        return "[" + row + ", " + height + ", " + position + "]";
    }

}

生成以下输出，与所需的输出相匹配:

[[30, 2, 1], [31, 7, 4], [31, 7, 5], [30, 9, 5], [31, 9, 5], [30, 4, 5 ], [31, 3, 5], [31, 2, 5], [31, 3, 6], [32, 2, 5]]

以下是当前 Java8 代码的 Java7 版本:

Java8:

private List<Location> getLocationsForRowAndPosition(int activeRow, int activePos,
        List<Location> locations) {
    int minRow = activeRow;
    int maxRow = ((activeRow & 1) == 0) ? activeRow + 1 : activeRow;    // If even, then pair includes the next higher row
    return locations.stream().filter(location -> location.row >= minRow && location.row <= maxRow && location.position == activePos)
            .collect(Collectors.toList());
}

Java 7:

private List<Location> getLocationsForRowAndPosition(int activeRow, int activePos,
        List<Location> locations) {
    int minRow = activeRow;
    int maxRow = ((activeRow & 1) == 0) ? activeRow + 1 : activeRow;    // If even, then pair includes the next higher row
    List<Location> positionLocations = new ArrayList<Location>();
    for (Location location : locations) {
        if (location.row >= minRow && location.row <= maxRow && location.position == activePos)
            positionLocations.add(location);
    }
    return positionLocations;
}

Java 8:

private int getNextPos(int currentPosition, List<Location> locations) {
    if (locations.isEmpty())
        return 0;
    OptionalInt min = locations.stream().filter(location -> location.position > currentPosition)
            .mapToInt(location -> location.position)
            .min(); 
    return min.isPresent() ? min.getAsInt() : 0;
}

Java 7:

private int getNextPos(int currentPosition, List<Location> locations) {
    if (locations.isEmpty())
        return 0;
    int minValue = Integer.MAX_VALUE;
    for (Location location : locations) {
        if (location.position > currentPosition && location.position < minValue)
            minValue = location.position;
    }
    return minValue == Integer.MAX_VALUE ? 0 : minValue;
}

Java 8:

private int getNextRow(List<Location> locations) {
    if (locations.isEmpty())
        return 0;
    return locations.stream().mapToInt(location -> location.row)
            .min().getAsInt();
}

Java 7:

private int getNextRow(List<Location> locations) {
    if (locations.isEmpty())
        return 0;
    int minValue = Integer.MAX_VALUE;
    for (Location location : locations) {
        if (location.row < minValue)
            minValue = location.row;
    }
    return minValue;
}

最后是 Java 7 的 minimizeHeight:

private List<Location> minimizeHeight(int currentHeight, List<Location> activePositionLocations) {
    List<Location> optimizedHeightLocations = new ArrayList<Location>();

    int minHeight = Integer.MAX_VALUE;
    int maxHeight = Integer.MIN_VALUE;
    for (Location location : activePositionLocations) {
        if (location.height < minHeight)
            minHeight = location.height;
        if (location.height > maxHeight)
            maxHeight = location.height;
    }

    /*
     * There are only two options to minimize (if the current height falls between min and max):
     * 1)  Travel down then up
     * 2)  Travel up then down
     */
    // First determine the first direction to go
    Direction direction;
    if (currentHeight == minHeight)
        direction = Direction.UP;
    else if (currentHeight == maxHeight)
        direction = Direction.DOWN;
    else {
        int distanceUp = maxHeight-currentHeight;
        int distanceDown = currentHeight-minHeight;
        direction = distanceUp < distanceDown ? Direction.UP : Direction.DOWN;
    }
    // Now travel in that direction (must sort the correct way first
    List<Location> sortedAscending = new ArrayList<Location>(activePositionLocations);  // Clone it
    Collections.sort(sortedAscending, new Comparator<Location>() {
        @Override
        public int compare(Location l1, Location l2) {
            return Integer.compare(l1.height, l2.height);
        }
    });
    List<Location> sortedDescending = new ArrayList<Location>(activePositionLocations); // Clone it
    Collections.sort(sortedDescending, new Comparator<Location>() {
        @Override
        public int compare(Location l1, Location l2) {
            return Integer.compare(l2.height, l1.height);
        }
    });

    if (direction == Direction.UP) {
        for (Location location : sortedAscending) {
            if (location.height >= currentHeight)
                optimizedHeightLocations.add(location);
        }
        for (Location location : sortedDescending) {
            if (location.height < currentHeight)
                optimizedHeightLocations.add(location);
        }
    } else {    // Direction = DOWN
        for (Location location : sortedDescending) {
            if (location.height <= currentHeight)
                optimizedHeightLocations.add(location);
        }
        for (Location location : sortedAscending) {
            if (location.height > currentHeight)
                optimizedHeightLocations.add(location);
        }
    }

    return optimizedHeightLocations;
}