Алгоритм N-й перестановки для использования при распараллеливании упаковки брут-бин (содержит один и тот же элемент более одного раза)

Question

Я написал небольшую открытую библиотеку 3D-пакетов с открытым исходным кодом с упаковщиком грубой силы для использования в режиме реального времени для расчета стоимости доставки заказа в интернет-магазине.Многие заказы содержат небольшое количество элементов, что делает грубую силу хорошим дополнением к другим алгоритмам.

Поскольку заказы могут содержать один и тот же элемент более одного раза (т.е. повторяющиеся / дублирующие / идентичные элементы), я перешелс алгоритмом лексографической перестановки.

Теперь я пытаюсь добавить паралеллизации / многопоточности и нашел несколько алгоритмов для вычисления n-й лексографической перестановки .Однако никто не принимает во внимание, что заказы могут содержать одни и те же элементы более одного раза.

В идеале я мог бы разделить число перестановок на количество потоков, и каждый поток рассчитал бы свою начальную точку и выполнил быопределенное количество итераций.

Существует ли такой алгоритм?

-

ОБНОВЛЕНИЕ:

Да, это действительно .Java-код адаптирован из связанного ответа:

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

Answer 1

То, что вы ищете, является алгоритмом ранжирования для перестановок с дубликатами, насколько я знаю, его не существует, в ответе темы ( Нахождение ранжирования слова (перестановок) с повторяющимися буквами ) вы найдете один без многопоточности. Я читал кое-где, но не знаю, где больше. Что вы можете улучшить сложность путем использования какого-то дерева.

Answer 2

Это будет работать (в Java), это из моего решения проблемы Project Euler 24. Вам просто нужно реализовать функцию факториала (или, что еще лучше, инициализировать некоторые в массив, если вы выполняете многие из этих вычислений перестановки). Вызовите функцию с аргументами («», ArrayList, содержащий ваши значения, которые могут повторяться, n), где n - это n-я перестановка, которую вы ищете:)

Вот код, я вставляю его со своего телефона, поэтому я не могу сделать блок кода, но вы можете найти его на моем github @oriyonay в Project Euler Solutions / Euler24.java:)

public static String permutation(String s, ArrayList<Integer> digits, int p) {
    if (p == 1) {
      for (int i: digits) s+= i;
      return s;
    }
    int fact = factorial(digits.size() - 1);
    int n = (p % fact == 0) ? (p / fact) - 1 : p / fact;
    s+= digits.get(n);
    digits.remove(n);
    return permutation(s, digits, p - (n*fact));
  }

Надеюсь, это было полезно!