java - 生成合成的迭代算法

Question

我实现了一种算法，它在 Y 框中写出 X 项的所有可能组合(在组合学中，我相信它们被称为组合)。我使用递归函数编写了这个算法，因为它更容易跟踪我们正在放入元素的当前盒子，以及剩余的元素数量。 该算法为我提供以下输出(4 个框和 3 个项目):

[3, 0, 0, 0], [2, 1, 0, 0], [2, 0, 1, 0], [2, 0, 0, 1], [1, 2, 0, 0], [1, 1, 1, 0], ..., [0, 0, 1, 2], [0, 0, 0, 3]

正如您所想象的，对于较大的 X 和 Y，合成的数量会增加很多。由于我不关心合成的顺序，我想并行化进一步的计算，但我做不到在递归函数上(我试过通过保存递归的状态来做到这一点，但这相当困惑，尽管它有效，但它真的很慢)。 所以，我想知道是否可以迭代地重写相同的函数(使用 for 循环)，以便我可以并行化它。 (要记住的一件事是，优化也很重要，因为我需要为较大的 X 和 Y 运行函数)我的递归函数如下所示:

public void charArrangements (int boxes, int items, String strBuild) {
        if (boxes > 1) {
            for (int i = 0; i <= items; i++) {
                String ss = strBuild + (items - i) + ";";
                charArrangements(boxes - 1, i, ss);
            }
        }
        else {
            String ss = strBuild + items;
            List<Integer> charArrangement = new ArrayList<Integer>();
            charArrangement = Stream.of(ss.split(";")).map(Integer::parseInt).collect(Collectors.toList());

            doCalculations(charArrangement);
        }
} 

Answer 1

听起来您希望能够更直接地访问累积解决方案的状态；例如，能够保存和恢复它而不必每次都重建它。实现这一目标的一种方法是使用词典生成。

我建议首先创建不带任何零的数字分区，然后添加零并使用已知的简单算法进行下一个字典顺序排列，您可以轻松地在线查找。以下是将 5 件商品订购到 7 个盒子中的示例:

Order partitions in decreasing order by number of parts

[0,0,1,1,1,1,1] -> generate all lexicographic permutations
[0,0,0,1,1,1,2] -> generate all lexicographic permutations
[0,0,0,0,1,2,2] -> ...

这是我想出的用于反向下一个相同大小的字典分区的算法，也许它可以改进或更正(我们反转它以便我们可以在下一步中从最低排名的排列开始):

(0) The first partition is either k (n/k)'s if k divides n,
    or (remainder of n/k) (n/k + 1)'s and (k - remainder of n/k)'s (n/k)'s
    to their left.

(1) Find the leftmost part, l, greater than 1

(2) If l is the rightmost part, we're done.
    Otherwise, decrement l and increment the leftmost part, r,
      right of l that is lower than its right neighbour.
      If r is not found, increment the rightmost part and
        set the rest of the partition according to
        instruction (0), where k and n now would be 
        (k - 1) and (n - rightmost part), respectively.

[0,0,0,0,1,2,2] -> generate all lexicographic permutations
[0,0,0,0,1,1,3] -> ...
etc.