Как проверить список на уникальность основания степени?

Question

[Дмитрий Темников]

Как сделать алгоритм для проверки списка на уникальность основания степени? Например:
[16, 25, 125] это False так как 25=5**2 и 125=5**3
[2,7,7] это False так как есть дубли
[2,5,43] это True
Критерий качества - скорость выполнения алгоритма

Comments

[Сергей Соколов]

256 == 4^4 == 2^8
каким вариантом воспользоваться для оценки?

[Wataru]

А что делать с числами, которые не степени?

Допустим, [6, 2] - это true? Правильно понимаю, что надо вернуть False, только если одно число из списка в какой-то рациональной степени будет равно другому числу?

Answer 1

[Дмитрий Темников]

from math import gcd
def uniqueFactor(lst):
    if len(set(lst)) != 3:
        return False
    lch=[]
    for num in lst:
        i=0; pr=prime[i]
        while gcd(num,pr) != pr:
            i+=1
            pr=prime[i]
        lch.append(pr)
    if len(set(lch)) != 3:
        return False
    return True

В моём случае prime это список простых чисел в Вашем может быть обыкновенный range(X)

Comments

[Wataru]

gcd() c простым числом!? Почему бы просто не проверить делимость через num % pr == 0?

[longclaps]

в Вашем может быть обыкновенный range(X)

Что еще за X, дурик?

Answer 2

[anikavoi]

А не хватит ли в этом случае "Повторяется ли НОД" ?

Comments

[Сергей Соколов]

2^5 и 4^4 имеют общие делители

[Дмитрий Темников]

Спасибо. Ваш комментарий навел на мысль, правда тут было не понятно что с чем сравнивать на НОД
В итоге в цикле просто перебирается gcd(num,pr) != pr, где:
num - проверяемое число, pr - перечень потенциальных оснований

Answer 3

[lz961]

1) Удалить повторяющиеся элементы и единицы.
2) Список пуст или состоит из одного элемента? вернуть "правда".
3) Выбрать среди элементов списка наименьший -- a
4) Заменить все элементы списка, кроме 'a', на частное от деления этого элемента на 'a'
5) При делении был ненулевой остаток? Вернуть"ложь"
6) Перейти к п. 1

как работает.
* единица -- не информативный элемент, поскольку любое число в нулевой степени -- 1, её можно исключить
* повторяющиеся элементы не информативны, можно оставить один из них
* если список состоит из степеней одного числа: b^k1, b^k2,... b^kn, то
1) На каждой итерации произведение элементов списка будет уменьшаться вплоть до прекращения работы алгоритма
2) список будет сохранять свое свойство уникальности основания степени
* если основания степени не уникальны, к какой-то момент остаток от деления окажется ненулевым

по суть на каждой итерации проверяется что наименьший элемент не равный 1 -- НОД для всего списка