Мне нужен итератор для всех наборов различные 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), (2, 1)}: 2,
{(3, 0), (1, 2)}: 2,
{(3, 0), (0, 3)}: 1,
{(2, 1), (1, 2)}: 1}
В качестве еще одного примера рассмотрим случай с 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
Мой вопрос (надеюсь, на него есть положительный ответ): это где-то уже было сделано?
Самый близкий ответ, который мне удалось найти, - это эта библиотека, которая решает более общую проблему, но с 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) (поскольку я работаю над перестановкой). Что касается второго кортежа, мне нужно запомнить, что в первом есть два нуля, чтобы я мог поменять вторую и третью цифры и создать набор {, (0,3,0)
Код: Выделить всё
(3,0,0) - Цифры (3,0,0) и (2,1,0). Как и раньше, первый кортеж — (3,0,0), и я могу поменять местами вторую и третью цифры, поэтому для выбора второго кортежа у меня есть {, (2,1,0)}, {
Код: Выделить всё
(3,0,0), (1,2,0)}, {Код: Выделить всё
(3,0,0), (0,2,1)Код: Выделить всё
(3,0,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), (1,0,2)} то же самое, что {Код: Выделить всё
(2,1,0), (0,1,2)}. [b]ЭТО СОДЕРЖИТ ПРОБЛЕМУ![/b] Это неправильно, потому что я перечисляю несколько кортежей дважды: {(2,1,0), (0,2,1)}, поместив третью цифру на первое место, первую цифру на второе место и вторую цифру на третье место.Код: Выделить всё
(2,1,0)
Первая проблема с этим подходом: Мне нужно удалить последние дубликаты. Однако я знаю, что нужно просто сравнить их друг с другом, и для этого нужен полный список (так что... не итератор).
Вторая проблема с этим подходом : Мне также нужно прикрепить к парам метку, описывающую, сколько их существует с точностью до перестановки ({(2, 1, 0), (3, 0, 0)}: 6, означает, что есть 6 возможных пар кортежей, которые можно получить перестановкой этого). Однако известный мне способ вычисления по сути эквивалентен первому подходу путем перечисления всех перестановок этой единственной пары, поэтому, опять же, слишком медленно
.Если вы все еще читаете это, спасибо за терпение!
Подробнее здесь: https://stackoverflow.com/questions/789 ... rmutations
