Кортежи целых чисел с фиксированными суммами с точностью до перестановок ⇐ Python

[Anonymous]

У меня возникла следующая проблема: мне нужно ускорить часть кода, который я написал ранее. Я программирую на Python, но этот вопрос больше об алгоритме, чем о коде Python.
Мне нужен итератор для всех наборов различные k кортежей целых чисел длиной a и суммой d с точностью до перестановки элементов кортежей.
Например, если k=2, a=2 и d =3, это все наборы различных k кортежей целых чисел длины a и суммы d:

Код: Выделить всё

{(3,0), (0,3)}, {(3,0), (2,1)}, {(3,0), (1,2)}, {(1,2), (2,1)}, {(0,3), (2,1)}, {(0,3), (1,2)}

Однако я хочу считать равными множества {(3,0), (1,2) и {(0,3), (2,1)} , поскольку, поменяв местами два числа в кортеже, я получу тот же результат. В итоге все наборы из двух разных кортежей целых чисел длиной 2 и суммой 3 равны:

Код: Выделить всё

{(3, 0), (2, 1)}: 2,
{(3, 0), (1, 2)}: 2,
{(3, 0), (0, 3)}: 1,
{(2, 1), (1, 2)}: 1}

Отличие от первого списка в том, что теперь я прикрепил к наборам еще и метку, подсчитывающую количество наборов с точностью до перестановок. Итак, снова {(3, 0), (2, 1) помечается цифрой 2, поскольку он также учитывается {(0, 3), (1, 2) >, а {(3, 0), (0, 3) помечен цифрой 1, поскольку перестановки просто возвращают тот же набор {(0, 3), (3, 0) .
В качестве еще одного примера рассмотрим случай с k=2, a=3, d=3 (поэтому наборы пар кортежей длины 3 с сумма 3).

Код: Выделить всё

{(2, 1, 0), (3, 0, 0)}: 6, {(1, 2, 0), (3, 0, 0)}: 6, {(0, 3, 0), (3, 0, 0)}: 3, {(1, 1, 1), (3, 0, 0)}: 3, {(0, 2, 1), (3, 0, 0)}: 6, {(1, 2, 0), (2, 1, 0)}: 3, {(2, 0, 1), (2, 1, 0)}: 3, {(1, 1, 1), (2, 1, 0)}: 6, {(0, 2, 1), (2, 1, 0)}: 6, {(0, 1, 2), (2, 1, 0)}: 3

Мне нужен итератор Python, который выдает этот результат, учитывая k (количество кортежей), a (длина каждого кортежа) и d (сумма элементов в каждом кортеже) .
Мой вопрос (надеюсь, на него есть положительный ответ): это где-то уже было сделано?
Самый близкий ответ, который мне удалось найти, - это эта библиотека, которая решает более общую проблему, но с k=1 (она просто перечисляет кортежи, а не наборы кортежей длиной k).
В неудачном случае этого никогда раньше не делалось, вот мои попытки найти решение.
Обратите внимание, что я не добавляю к вопросу явный код. Это потому, что оба подхода, которые я пробовал, неверны: первый работает, но это не итератор. Вторые просто не работают, но не из-за программирования, а из-за того, что алгоритм неправильный. Для вашего удобства/любопытства я добавляю несколько примеров кода, написанного на Python3 (если я смогу создать работающий код, я, конечно, буду рад им поделиться!)
Мой первый — бесполезный — подход заключался в том, чтобы просто построить результат, перебирая все наборы, а затем применить перестановки для сокращения списка. Это слишком медленно и требует много памяти. (Пример кода, опять же, это работает, но это не итератор)
Мой второй — незаконченный — подход, надеюсь, был немного умным: (Пример кода, это не работает, см. объяснение ниже)

• Первый шаг, я перебираю упорядоченные кортежи цифр: для k=2, a=3, d =3 Я получаю только (3,0,0), (2, 1, 0), (1, 1, 1).
• Второй шаг, я перехожу к создаю список цифр, которые составят окончательные кортежи: сначала я использую (3,0,0) дважды, затем (3,0,0) и (2,1,0), затем (3,0,0) и (1,1,1) и так далее.
• Третий шаг. Для каждого выбора цифры, мне нужно вычислить все возможные перестановки. Я делаю это с помощью рекурсии. Вот три примера:

• Цифры (3,0,0) дважды. Первый кортеж — это просто (3,0,0) (поскольку я работаю над перестановкой). Что касается второго кортежа, мне нужно запомнить, что в первом есть два нуля, чтобы я мог поменять вторую и третью цифры и создать набор {

  Код: Выделить всё

  (3,0,0)

  , (0,3,0)
• Цифры (3,0,0) и (2,1,0). Как и раньше, первый кортеж — (3,0,0), и я могу поменять местами вторую и третью цифры, поэтому для выбора второго кортежа у меня есть {

  Код: Выделить всё

  (3,0,0)

  , (2,1,0)}, {

  Код: Выделить всё

  (3,0,0)

  , (1,2,0)}, {

  Код: Выделить всё

  (3,0,0)

  , (0,2,1)
• Цифры (2,1,0) и (2,1,0). Как и раньше, первый кортеж — это (2,1,0), и теперь, поскольку все цифры разные, я могу поместить все перестановки для второго кортежа:
  {

  Код: Выделить всё

  (2,1,0)

  , (2,0,1)}, {

  Код: Выделить всё

  (2,1,0)

  , (1,2,0)}, {

  Код: Выделить всё

  (2,1,0)

  , (1,0,2)}, {

  Код: Выделить всё

  (2,1,0)

  , (0,2,1)}, {

  Код: Выделить всё

  (2,1,0), (0,1,2)}.  [b]ЭТО СОДЕРЖИТ ПРОБЛЕМУ![/b]
  Это неправильно, потому что я перечисляю несколько кортежей дважды: {(2,1,0)

  , (1,0,2)} то же самое, что {

  Код: Выделить всё

  (2,1,0)

  , (0,2,1)}, поместив третью цифру на первое место, первую цифру на второе место и вторую цифру на третье место.

Подводя итог:
Первая проблема с этим подходом: Мне нужно удалить последние дубликаты. Однако я знаю, что нужно просто сравнить их друг с другом, и для этого нужен полный список (так что... не итератор).
Вторая проблема с этим подходом : Мне также нужно прикрепить к парам метку, описывающую, сколько их существует с точностью до перестановки ({(2, 1, 0), (3, 0, 0)}: 6, означает, что есть 6 возможных пар кортежей, которые можно получить перестановкой этого). Однако известный мне способ вычисления по сути эквивалентен первому подходу, заключающемуся в перечислении всех перестановок этой единственной пары, так что, опять же, слишком медленно .

Подробнее здесь: https://stackoverflow.com/questions/789 ... rmutations