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.
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.
Does such an algorithm exist?
--
UPDATE:
Yes, it does. Java code adapted from linked answer:
public static int[] unrank(int[] frequencies, int rank) {
// https://mcmap.net/q/1433255/-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;
}
And for running
@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)));
}
}