获得所有可能的通过打破一个数字形成的完美正方形列表

Question

获取通过打破一个数字而形成的完美正方形列表的所有可能排列

Ex：如果N=14，则列表为[1,1,4,4,4]，[1,4,9]，[1,1,1,1,9]，[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)

帮帮我

Answer 1

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)]

Answer 2

以下代码导致N=14的可能性为6，而不是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)]