用于蛮力装箱包装并行化的第N个置换算法(多次包含同一项目) [英] N-th permutation algorithm for use in brute force bin packaging parallelization (containing the same item more than once)

问题描述

我写了一个小的开源3D容器打包库与蛮力包装机一起用于实时计算网上商店订单的运输成本.许多订单包含少量物品，因此蛮力是其他算法的合理补充.

I've written a small open-source 3D bin packaging library with a brute-force packager for use in real-time calculation of web shop order shipping cost. Many orders contain a small number of items, making brute-force a fair supplement to other algorithms.

由于订单可以多次包含同一项目(即重复/重复/相同元素)，因此我采用了字典排列算法.

As orders can contain the same item more than once (i.e. repeated / duplicate / identical elements), I've gone with the lexographical permutations algorithm.

现在，我正尝试添加一些并行化/多线程功能，并发现一些用于计算第n个字典排列的算法.但是，没有人考虑到订单可以包含多个相同项目.

Now I'm attempting to add some paralellization / multi-threading and have found a few algorithms for calculating the n-th lexographical permutation. However none take into account that orders can contain the same items more than once.

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

Ideally I would be able to divide the number of permutations by the number of threads, and have each thread calculate its starting point and run a specific number of iterations.

是否存在这样的算法?

-

更新:

是的，确实如此.从链接的答案改编而成的Java代码:

Yes, it does. Java code adapted from linked answer:

public static int[] unrank(int[] frequencies, int rank) {
    // https://stackoverflow.com/questions/22642151/finding-the-ranking-of-a-word-permutations-with-duplicate-letters

    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)));
    }
}

推荐答案

您正在搜索的是一种具有重复排列的排列算法，到目前为止，我知道在该线程的答案中不存在一个排列(

What you are searching is a ranking algorithm for permutations with duplicates, so far i know there doesnt exist one, in the answer of the thread ( Finding the ranking of a word (permutations) with duplicate letters )you will find one without multithreading. I have read some where but dont know where anymore. That you can improve the complexity by the usage of some tree.

这篇关于用于蛮力装箱包装并行化的第N个置换算法(多次包含同一项目)的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！