算法面试题解析：层板衣柜问题

给定一个高度为 2000mm 的柜子空间，以及 n 个层板距离柜子底部高度，满足移动层板位置 使得层板等分衣柜的空间。计算所有移动层板的顺序。

层板号自下向上依次排列，1，2…n。层板需要考虑空间位置，不能跨层板移动。

示例 1

输入:n = 3，zs = 50，60，1000 输出:

321

示例 2

输入:n = 4，zs = 50，600，700，1000 输出:

1，4，3，2

4，1，3，2

4，3，1，2

4，3，2，1

提示 1:1 <= n <= 10

提示 2:输出结果需要按小到大排序

这个问题可以使用递归的方式解决。我们可以将问题拆分成两个子问题：移动最上面的层板和移动剩余层板的问题。

首先，我们需要找到当前可以移动的层板，即距离柜子顶部最近的层板。然后，我们将该层板移动到最底部的位置。这样，我们就完成了一个层板的移动，剩下的问题就是将剩余的层板进行等分。

接下来，我们可以将剩余的层板作为一个子问题来处理。我们使用递归调用来解决这个子问题，直到没有剩余的层板需要移动。

以下是使用Python实现的代码：

def move_shelves(n, zs):
    if n == 1:
        return [[1]]  # 只有一个层板，直接返回

    result = []  # 存储所有移动层板的顺序

    for i in range(n):
        new_zs = zs[:i] + zs[i+1:]  # 剩余层板的高度列表，去除当前层板的高度

        # 递归调用，移动剩余层板
        sub_result = move_shelves(n-1, new_zs)

        # 将当前层板的编号插入到每个子问题的结果中
        for sub in sub_result:
            result.append([i+1] + sub)

    return result

n = int(input("请输入层板个数："))
zs = list(map(int, input("请输入层板距离柜子底部的高度：").split()))

results = move_shelves(n, zs)

# 按小到大排序
results.sort()

print("所有移动层板的顺序：")
for res in results:
    print("，".join(map(str, res)))

通过递归调用move_shelves()函数，我们可以得到所有移动层板的顺序。最后，我们按照小到大的顺序输出结果。

java代码

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
import java.util.Scanner;

public class ShelfMovement {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        System.out.print("请输入层板个数：");
        int n = scanner.nextInt();
        int[] zs = new int[n];
        System.out.print("请输入层板距离柜子底部的高度：");
        for (int i = 0; i < n; i++) {
            zs[i] = scanner.nextInt();
        }

        List<List<Integer>> results = moveShelves(n, zs);

        // 按小到大排序
        Collections.sort(results, (a, b) -> {
            for (int i = 0; i < n; i++) {
                if (a.get(i) != b.get(i)) {
                    return a.get(i) - b.get(i);
                }
            }
            return 0;
        });

        System.out.println("所有移动层板的顺序：");
        for (List<Integer> res : results) {
            for (int i = 0; i < n; i++) {
                System.out.print(res.get(i));
                if (i < n - 1) {
                    System.out.print(",");
                }
            }
            System.out.println();
        }
    }

    public static List<List<Integer>> moveShelves(int n, int[] zs) {
        List<List<Integer>> result = new ArrayList<>();

        if (n == 1) {
            List<Integer> singleResult = new ArrayList<>();
            singleResult.add(1);
            result.add(singleResult);
            return result;
        }

        for (int i = 0; i < n; i++) {
            int[] newZs = new int[n - 1];
            int index = 0;
            for (int j = 0; j < n; j++) {
                if (j != i) {
                    newZs[index] = zs[j];
                    index++;
                }
            }

            List<List<Integer>> subResult = moveShelves(n - 1, newZs);

            for (List<Integer> sub : subResult) {
                List<Integer> res = new ArrayList<>();
                res.add(i + 1);
                res.addAll(sub);
                result.add(res);
            }
        }

        return result;
    }
}

注意：这个问题的解空间非常大，随着层板数量的增加，解的数量会呈指数级增长。因此，在层板数量较大时，计算所有的移动顺序可能会非常耗时。