Python: список целых чисел с равной суммой без повторений - PullRequest
Новая
       35

Python: список целых чисел с равной суммой без повторений

0 голосов
/ 02 ноября 2019

Для целых чисел в диапазоне (1, 13) мне нужно построить все возможные варианты трех целых чисел, сумма которых равна 13. Варианты не должны иметь повторений. Например, (1,2,10), (2,1,10), (10,1,2) и (10,2,1) являются повторениями одного варианта. Таким образом, результирующий список должен иметь только один из этих кортежей, независимо от того, какой именно. Варианты с одинаковыми целыми числами в разных позициях в результирующем кортеже (1,1,11) также допустимы. Для этих вариантов повторения будут такими, как (1,1,11), (1,11,1) и (11,1,1).

Чтобы дать, возможно, лучшее объяснение проблемы, вотИстория, откуда это происходит:

Встречаются два друга Алан и Дрейк.

Алан: У меня трое детей.

Дрейк: Сколько им лет?

Алан: Сумма возрастов детей равна 13.

Поэтому я пытаюсь получить список всех возможных возрастов.

У меня есть этот код, который генерирует все возможные повторения, которые янужно сбросить: 

ages = list(range(1,13))
kids_ages = []
for a in ages:
  for b in ages:
    for c in ages:
      if a + b + c == 13:
        kids_ages.append((a,b,c))

В результате я получаю: 

([(1, 1, 11),
(1, 2, 10),
(1, 3, 9),
(1, 4, 8),
(1, 5, 7),
(1, 6, 6),
(1, 7, 5),
(1, 8, 4),
(1, 9, 3),
(1, 10, 2),
(1, 11, 1),
(2, 1, 10),
(2, 2, 9),
(2, 3, 8),
...

Как избавиться от повторений?

Ответы [ 3 ]

1 голос
/ 02 ноября 2019

Попробуйте: 

import itertools

res=list(sorted(el) for el in itertools.combinations_with_replacement(range(1, 14), 3) if sum(el)==13)

print(res)

Вывод: 

[[1, 1, 11], [1, 2, 10], [1, 3, 9], [1, 4, 8], [1, 5, 7], [1, 6, 6], [2, 2, 9], [2, 3, 8], [2, 4, 7], [2, 5, 6], [3, 3, 7], [3, 4, 6], [3, 5, 5], [4, 4, 5]]

[Program finished]
1 голос
/ 02 ноября 2019

Frozenset может помочь вам удалить дубликаты. 

ages = list(range(1,13))
kids_ages = []
for a in ages:
  for b in ages:
    for c in ages:
      if a + b + c == 13:
        kids_ages.append((a,b,c))

result=set(map(frozenset, kids_ages))
print(result)
0 голосов
/ 02 ноября 2019

Я решил это, рассматривая только самый низкий возраст для первой позиции и второй самый низкий возраст для второй позиции. Таким образом, поиск дубликатов не требуется. 

ages = list(range(1,13))
kids_ages = []
# First, pick the smallest age
for age1 in range(1,13):
    remaining_sum = 13 - age1
    # Pick the next smallest age
    for age2 in range(age1 + 1, 13):
        age3 = 13 - age1 - age2
        if age3 > age1 and age3 > age2:
            kids_ages.append( (age1, age2, age3) )

print kids_ages
# Result:
# [(1, 2, 10), (1, 3, 9), (1, 4, 8), (1, 5, 7), (2, 3, 8), (2, 4, 7), (2, 5, 6), (3, 4, 6)]

РЕДАКТИРОВАТЬ: Решение выше не включает варианты, где число повторяется, например (1, 1, 11). Чтобы включить их, просто измените одно место в коде, чтобы получить: 

kids_ages = []
# First, pick the smallest age
for age1 in range(1,13):
    remaining_sum = 13 - age1
    # Pick the next smallest age, whch may be the same as the first
    for age2 in range(age1, 13):
        # Only a single number can be the third age. Check if it's valid.
        age3 = 13 - age1 - age2
        if age3 >= age2:
            kids_ages.append( (age1, age2, age3) )

# Result:
# [(1, 1, 11), (1, 2, 10), (1, 3, 9), (1, 4, 8), (1, 5, 7), (1, 6, 6), (2, 2, 9), (2, 3, 8), (2, 4, 7), (2, 5, 6), (3, 3, 7), (3, 4, 6), (3, 5, 5), (4, 4, 5)]

Для трех одинаковых чисел не существует такого решения, которое бы суммировалось в 13.

...