用于强力 bin 打包并行化的第 N 次置换算法（多次包含相同的项目）

Question

我用强力打包程序编写了一个小程序 open-source 3D bin packaging library，用于实时计算网上商店订单的运费。许多订单包含少量商品，这使得暴力破解成为对其他算法的公平补充。

由于订单可以多次包含相同的项目（即重复/重复/相同的元素），我采用了词法排列算法。

现在我正在尝试添加一些并行化/多线程并找到 a few algorithms for calculating the n-th lexographical permutation。但是 none 考虑到订单可能多次包含相同的商品。

理想情况下，我可以将排列数除以线程数，并让每个线程计算其起点和运行特定的迭代次数。

有这样的算法吗？

--

更新：

是的，it does。 Java 代码改编自链接答案：

public static int[] unrank(int[] frequencies, int rank) {
    // 

    int count = 0;
    for(int f : frequencies) {
        count += f;
    }

    int permutationCount = 1;
    int first = firstDuplicate(frequencies);
    if(first == -1) {
        for(int i = 0; i < count; i++) {
            permutationCount = permutationCount * (i + 1);
        }

        // use classic n-th lexographical permutation algorithm
        throw new RuntimeException("Not implemented");
    } else {
        for(int i = frequencies[first]; i < count; i++) {
            permutationCount = permutationCount * (i + 1);
        }
        for(int i = first + 1; i < frequencies.length; i++) {
            if(frequencies[i] > 1) {
                for(int k = 1; k < frequencies[i]; k++) {
                    permutationCount = permutationCount / (k + 1);
                }
            }
        }

        return unrank(frequencies, count, permutationCount, rank);
    }

}

private static int firstDuplicate(int[] frequencies) {
    for(int i = 0; i < frequencies.length; i++) {
        if(frequencies[i] > 1) {
            return i;
        }
    }
    return -1;
}   

private static int[] unrank(int[] frequencies, int elementCount, int permutationCount, int rank) {
    int[] result = new int[elementCount];

    for(int i = 0; i < elementCount; i++) {
        for(int k = 0; k < frequencies.length; k++) {
            if(frequencies[k] == 0) {
                continue;
            }
            int suffixcount = permutationCount * frequencies[k] / (elementCount - i);
            if (rank <= suffixcount) {
                result[i] = k;

                permutationCount = suffixcount;

                frequencies[k]--;
                break;
            }
            rank -= suffixcount;
        }
    }
    return result;
}

而对于运行宁

@Test
public void testUnranking() {
    int count = (7 * 6 * 5 * 4 * 3 * 2 * 1) / ((4 * 3 * 2 * 1) * (3 * 2 * 1));
    for(int i = 0; i < count; i++) {
        int[] frequencies = new int[2];
        frequencies[0] = 3;
        frequencies[1] = 4;

        System.out.println(Arrays.asList(NthPermutationRotationIterator.unrank(frequencies, i + 1)));
    }
}

Answer 1

您正在搜索的是一种用于重复排列的排名算法，到目前为止我知道不存在，在线程（Finding the ranking of a word (permutations) with duplicate letters）的答案中您会找到一个没有多线程的算法。我读过一些地方但不知道在哪里了。你可以通过使用一些树来提高复杂性。

用于强力 bin 打包并行化的第 N 次置换算法（多次包含相同的项目）

N-th permutation algorithm for use in brute force bin packaging parallelization (containing the same item more than once)

parallel-processing

permutation

bin-packing