Мне нужно организовать свой список определенным образом - Python

Question

Обычно пользователь вводит любое положительное число, а затем программа должна упорядочить список, который содержит все положительные числа вплоть до этого введенного числа, так чтобы сумма двух последовательных элементов в списке была квадратным числом.Если введенный номер не позволяет эту сортировку, я просто хочу, чтобы программа напечатала ошибку.Пока это код:

u = int(input("ENTER: "))
l = []
for i in range(1, u + 1):
    l.append(i)
o = l
t = []
for elem in l:
    for x in o:
        p = elem + x
        p = math.sqrt(p)
        if p%1 == 0:
            if x == elem:
                break
            else:
                t.append(x)
                t.append(elem)

Если я, например, введу 15, то список t, в конце концов, будет выглядеть так:

[3, 1, 8, 1, 15, 1, 1, 3, 6, 3, 13, 3, 5, 4, 12, 4, 4, 5, 11, 5, 3, 6, 10, 6, 2, 7, 9, 7, 1, 8, 7, 9, 6, 10, 15, 10, 5, 11, 14, 11, 4, 12, 13, 12, 3, 13, 12, 13, 2, 14, 11, 14, 1, 15, 10, 15]

Список содержит всепары, которые теоретически будут работать, я застрял, упорядочив этот список так, чтобы каждое число появлялось один раз и чтобы каждое последующее число следовало за свойством, упомянутым выше.

Итак, список, который я ищу в конце, будет следующим:

[8, 1, 15, 10, 6, 3, 13, 12, 4, 5, 11, 14, 2, 7, 9]

Заранее благодарю за любую помощь.

Answer 1

Я внесу несколько небольших улучшений в ответ @Jayjayyy.Этот код, немного измененный по сравнению с @ Jayjayyy, несколько сложнее, но и быстрее.Для n = 15 этот код более чем в 7,5 раз быстрее в моей системе, а для n = 30 он более чем в 19 раз быстрее.Это увеличение скорости достигается за счет уменьшения количества проверок, что сумма является квадратным числом, и за счет ускорения этих проверок.Я также переместил проверку квадратного числа, чтобы уменьшить количество вызовов самой процедуры.

Наконец, я изменил некоторые имена переменных для большей самодокументированности.Но код @ Jayjayyy по-прежнему очень похвален за его простоту.

import math

def f(listsofar, numbersleft):
    if not numbersleft:
        return listsofar
    result = False
    for i in numbersleft:
        if not listsofar or math.sqrt(listsofar[-1] + i).is_integer():
            result = f(listsofar + [i], [j for j in numbersleft if j != i])
            if result:
                break
    return result

n = int(input("Arrange numbers from 1 to ").strip())
numbers = list(range(1, n+1))
print("Input:", numbers)
print("Output:", f([], numbers))

Answer 2

Это был бы вид подхода грубой силы с рекурсивной функцией:

import math

def f(temp, numbers):
    for i, j in zip(temp[:-1], temp[1:]):
        sqrt = math.sqrt(i+j)
        if int(sqrt) != sqrt:
            return False
    if not numbers:
        return temp
    for i in numbers:
        result = f(temp + [i], [j for j in numbers if j != i])
        if result:
            break
    return result

n = int(input("Arrange numbers from 1 to ").strip())
numbers = list(range(1, n+1))
print("Input:", numbers)
print("Output:", f([], numbers))

Пример с 4:

Arrange numbers from 1 to 4
Input: [1, 2, 3, 4]
Output: False

Пример с 15:

Arrange numbers from 1 to 15
Input: [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15]
Output: [8, 1, 15, 10, 6, 3, 13, 12, 4, 5, 11, 14, 2, 7, 9]

Answer 3

Ты почти у цели.Вы можете выполнить последние шаги с помощью графиков.Список t лучше использовать в виде пар кортежей, представляющих ребра.

Вы также можете изменить список позже, как показано ниже.

t =[3, 1, 8, 1, 15, 1, 1, 3, 6, 3, 13, 3, 5, 4, 12, 4, 4, 5, 11, 5, 3, 6, 10, 6, 2, 7, 9, 7, 1, 8, 7, 9, 6, 10, 15, 10, 5, 11, 14, 11, 4, 12, 13, 12, 3, 13, 12, 13, 2, 14, 11, 14, 1, 15, 10, 15]
t = list(zip(t[::2],t[1::2]))

Я бы порекомендовал слегка изменить исходный код.

import networkx as nx
import math

u = int(input("ENTER: "))
l = []
for i in range(1, u + 1):
    l.append(i)
o = l
t = []
for elem in l:
    for x in o:
        p = elem + x
        p = math.sqrt(p)
        if p%1 == 0:
            if x == elem:
                break
            else:
                t.append((x, elem)) #to keep tuples instead

Теперь просто превратите его в проблему с графиком.Найдите всех соседей рекурсивно, пока не получите максимальную длину.Следите за тем, каких соседей вы уже посетили, чтобы избежать повторного прохождения тех же путей.

G = nx.Graph()
G.add_edges_from(t)
#Now, you need to find "new" neighbours for all possible combinations that make the longest chain in your case
def findPaths(G, current_node, n, to_exclude = None):
    if to_exclude == None:
        to_exclude = set([current_node])
    else:
        to_exclude.add(current_node)
    if n==1:
        return [[current_node]]
    paths = [[current_node]+path for neighbor in G.neighbors(current_node) if neighbor not in to_exclude for path in findPaths(G,neighbor,n-1,to_exclude)]
    to_exclude.remove(current_node)
    return paths


allpaths = []
for node in G:
    allpaths.extend(findPaths(G, node, G.number_of_nodes()))
if allpaths:
    print('match found')
    [print(x) for x in allpaths]
else:
    print('no matches')

Answer 4

Когда вы использовали два цикла, вы обычно добавляете одинаковые числа друг к другу, а не к следующему в списке, поэтому (элемент в l == x в o) всегда истинно

, и когда вы использовали (p% 1 == 0) другой всегда True

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

NoDuplicatedList = set (t)

t - список, из которого вы хотите удалить дубликаты.

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