0

Задачка на codewars сосчитать кол-во возможных комбинаций элементов. Всё вроде работает кроме момента когда arr = [1] *8.

Текст задания: Учитывая набор элементов (целые числа или строковые символы, символы только в RISC-V), где любой элемент может встречаться более одного раза, верните количество подмножеств, которые не содержат повторяющегося элемента.

Давайте посмотрим на примере:

set numbers = {1, 2, 3, 4} Подмножества являются:

{{1}, {2}, {3}, {4}, {1,2}, {1,3}, {1,4}, {2,3}, {2,4}, {3,4}, {1,2,3}, {1,2,4}, {1,3,4}, {2,3,4}, {1,2,3,4}} Существует 15 подмножеств. Как вы можете видеть, пустое множество {} не учитывается.

Давайте посмотрим пример с повторениями элемента:

set letters = {a, b, c, d, d} Подмножества для этого случая (включая только те, которые не имеют повторяющихся элементов внутри) будут:

{{a}, {b}, {c}, {d}, {a,b}, {a,c}, {a,d}, {b,c}, {b,d}, {c,d}, {a,b,c}, {a,b,d}, {a,c,d}, {b,c,d}, {a,b,c,d}} Существует 15 подмножеств.

Функция est_subsets()(javascript:estSubsets()) вычислит количество этих подмножеств.

Он получит массив в качестве аргумента и в соответствии со своими особенностями выведет количество подмножеств, которые не содержат повторяющегося элемента.

est_subsets([1, 2, 3, 4]) == 15 est_subsets(['a', 'b', 'c', 'd', 'd']) == 15

Мой код:

import itertools
def est_subsets(arr):
    for m in arr:
        if arr.count(m) > 1:
            arr.remove(m)
    z = []
    c = list(z)
    x = 1
    while x < len(arr) +1:
        n = itertools.combinations(arr, x)
        for i in n:
            z.append(i)
        x += 1

    print(len(z))
est_subsets([1,2,3,4])
est_subsets(['a', 'z', 'z', 'z', 'b', 'j', 'f', 'k', 'b',
        'd', 'j', 'j', 'n', 'm', 'm'])
est_subsets([1] * 8)
3
  • нет возможности корректировать заданные переменные в est_susbsets
    – joynik
    Commented 9 окт. 2022 в 9:57
  • 2
    вместо первого цикла arr = list(set(arr))
    – splash58
    Commented 9 окт. 2022 в 10:03
  • А что вы называете комбинациями? Где точное условие?
    – MBo
    Commented 9 окт. 2022 в 12:46

1 ответ 1

1

При использовании комментария от @splash58 решение будет довольно коротким:

 def est_subsets(arr):
     return (1<<len((set(arr))) - 1

Почему так? Потому что подмножеств из k уникальных элементов ровно 2^k, включая пустое множество. 1<<n эквивалентно возведению двойки в эту степень, минус один - не учитываем пустое множество

2
  • 1
    не надо в лист обратно преобразовывать len(set отлично работает
    – splash58
    Commented 10 окт. 2022 в 7:49
  • @splash58 Точно, эт я механически перенёс.
    – MBo
    Commented 10 окт. 2022 в 7:57

Ваш ответ

Нажимая «Отправить ответ», вы соглашаетесь с условиями пользования и подтверждаете, что прочитали политику конфиденциальности.

Всё ещё ищете ответ? Посмотрите другие вопросы с метками или задайте свой вопрос.