Получите весь возможный список идеальных квадратов, образованных путем разбиения числа - PullRequest
Новая
       5

Получите весь возможный список идеальных квадратов, образованных путем разбиения числа

0 голосов
/ 06 мая 2020

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

Пример : Если N = 14, то списки будут [1,1,4,4,4] , [1,4,9], [1,1,1,1,1,9], [1,1,1,1,1,1,1,1,1,1,1,1,1, 1]

Списки вывода могут быть в любом порядке

Я получил этот код, но он может давать только правильные квадраты по порядку. 

l = []
b = int(input())
for i in range(1,b):
    k = i*i
    l.append(k)
    if sum(l)>b:
        l.pop()
        break
    else:
        pass
print(l)

помогите мне ..

Ответы [ 2 ]

2 голосов
/ 06 мая 2020

Следующий код приводит к 6 возможностям для N = 14, а не к опубликованным 4.

Код 

from itertools import chain, combinations
from pprint import pprint

# flatten and powerset from
#   https://docs.python.org/3/library/itertools.html#itertools-recipes
def flatten(list_of_lists):
    "Flatten one level of nesting"
    return chain.from_iterable(list_of_lists)

def powerset(iterable):
    "powerset([1,2,3]) --> () (1,) (2,) (3,) (1,2) (1,3) (2,3) (1,2,3)"
    s = list(iterable)
    return chain.from_iterable(combinations(s, r) for r in range(len(s)+1))

def solve(n):
  " Get all possible permutations of list of perfect squares formed by breaking a number "
  squares = (i*i for i in range(1, int(b**0.5)+1)) # squares that can be used
  multiples = ([i]*int(b//i) for i in squares)     # repetition of squares that can be used
  numbers = flatten(multiples)                     # flatten to single list

  # Compute set of powerset, and take results which sum to b
  return [x for x in set(powerset(numbers)) if sum(x) == b]

Тест 

b = int(input('input number: '))  # Enter 14
result = solve(b)
pprint(result)

Выход 

input number: 14
[(1, 1, 1, 1, 1, 1, 4, 4),
 (1, 1, 1, 1, 1, 9),
 (1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 4),
 (1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1),
 (1, 4, 9),
 (1, 1, 4, 4, 4)]

Ограничить максимальную длину 

def solve_maxlen(n, maxlen):
  " Get all possible permutations of list of perfect squares formed by breaking a number "
  squares = (i*i for i in range(1, int(b**0.5)+1)) # squares that can be used
  multiples = ([i]*int(b//i) for i in squares)     # repetition of squares that can be used
  numbers = flatten(multiples)                     # flatten to single list

  # Compute set of powerset, and take results which sum to b
  return [x for x in set(powerset(numbers)) if sum(x) == b and len(x) <= maxlen] 

pprint(solve_maxlen(14, 6))

Выход 

[(1, 1, 1, 1, 1, 9), (1, 4, 9), (1, 1, 4, 4, 4)]
1 голос
/ 06 мая 2020 
import itertools

up_to = int(input())

def is_perfect_square(number):
  squared = pow(number, 0.5)
  return int(squared) == squared

perfect_squares = filter(is_perfect_square, range(1, up_to))
permutations = list(itertools.permutations(perfect_squares))

print(permutations)

Результат: 

[(1, 4, 9), (1, 9, 4), (4, 1, 9), (4, 9, 1), (9, 1, 4), (9, 4, 1)]
...