1

Тема: Булеан множини

Прийшов мій час засирати форум лабами.

Тож, вчуся я в НУ Львів Політех. Комп. науки. Перша лаба, з дискретки.

Треба вивести булеан множин. Можна на пітоні, можна на сішці. Я взагалі не викопаю, алгоритму.

було таке
a = [1, 2, 3]

i = 0
result = []
current = ''

lens = 2
used = []
while i < len(a):
    if a[i] not in used:
        pass
        current += str(a[i])
        used.append(a[i])
        print current
        if len(current) == lens:
            result.append(current)
            current = ''
            if i != (len(a) - 1):
                i = 0
            else:
                i += 1
        else:
            i += 1
    else:
        i += 1

print result

Рахує ок лише на певній стадії. Тобто якщо є множина a, b. c то код вище виведе ab. Не модифікував далі.

Нагуглив що булеан має шукатись через рекурсію, але теж не зрозуміло як. з вікі: https://image.prntscr.com/image/9y_Dr7Q8S1y7H5Lbamnftg.png

-------------

Ще нагугли c код: але в ньому розібратись не можу, також не зрозумів алгоритму (побітовий зсув тут до чого взагалі?)

#include<iostream>

void Print(char *a, int n, int i)
{
    if (n)
    {
        if (n & 1)
            std::cout << a[i] << " ";
        Print(a, n >> 1, i + 1);
    }
}

int main()
{
    int r, i, size;
    char a[] = {'a', 'b', 'c'};
    size = sizeof(a) / sizeof (*a);
    r = 1 << size;
    for (i = 0; i < r; i++)
    {
        Print(a, i, 0);
        std::cout << "\n";
    }
    return 0;
}

Буду дуже радий за будь-яку допомогу. Просто супер було б якби я вкурив алгоритм.

Якщо хтось напише мені на пітоні - віддячусь (переносити тему в розділ пошуку роботи, думаю не треба).

Прихований текст

Чесно, от зараз - це просто влом. Можливо, це, і потрібний матеріал, але просто влом справді.

Подякували: 0xDADA11C71

2

Re: Булеан множини

то якщо ви не розбираєтесь в алгоритмі, то нащо ви шукаєте незрозумілий вам код, якщо можна надибати сам алгоритм і зрозуміти його без усіляких кодів?

3 Востаннє редагувалося Master_Sergius (18.09.2017 23:39:21)

Re: Булеан множини

Ну, можна погуглити трішки і зрозуміти що то таке той булеан взагалі.
Якщо X – множина {x,y,z}, то булеан (множина усіх підмножин):
{}, {x}, {y}, {z}, {x,y}, {x,z}, {y,z}, {x,y,z}

Ну і якби звідси задача уже не є складною. Якщо писати на Python, можна поглянути на бібліотеку itertools.

Подякували: 0xDADA11C7, NaharD, LoganRoss, FakiNyan, sensei5

4 Востаннє редагувалося koala (19.09.2017 06:56:27)

Re: Булеан множини

Все просто. Потужність булеана дорівнює 2^p (p - потужність множини). Знаєте чому? Бо кожен елемент множини може як входити, так і не входити (2 варіанти) в елемент булеана. А отже, є взаємно однозначна відповідність між двійковими числами довжини p та елементами булеана (наприклад, 00...0 - це {}, а 11...1 - це початкова множина). Тепер зможете сформувати булеан?

Звісно, можна вручну реалізовувати операцію додавання (чи віднімання) 1 від числа за допомогою сірників та клею побітових операцій, але нащо, якщо це вже є вбудоване в процесор?

Подякували: NaharD, Q-bart, LoganRoss, 0xDADA11C74

5

Re: Булеан множини

Master_Sergius написав:

Ну, можна погуглити трішки і зрозуміти що то таке той булеан взагалі.
Якщо X – множина {x,y,z}, то булеан (множина усіх підмножин):
{}, {x}, {y}, {z}, {x,y}, {x,z}, {y,z}, {x,y,z}

Ну і якби звідси задача уже не є складною. Якщо писати на Python, можна поглянути на бібліотеку itertools.

типу itertools.combinations(iterable, r) for r in range(len(iterable) +1)  ?

6

Re: Булеан множини

Master_Sergius написав:

Ну, можна погуглити трішки і зрозуміти що то таке той булеан взагалі.
Якщо X – множина {x,y,z}, то булеан (множина усіх підмножин):
{}, {x}, {y}, {z}, {x,y}, {x,z}, {y,z}, {x,y,z}

Ну і якби звідси задача уже не є складною. Якщо писати на Python, можна поглянути на бібліотеку itertools.

Та це все я загуглив. Як виглядає булеан - зрозуміло.
А от iteertools - banned to use. Самому треба написати

7

Re: Булеан множини

koala написав:

Все просто. Потужність булеана дорівнює 2^p (p - потужність множини). Знаєте чому? Бо кожен елемент множини може як входити, так і не входити (2 варіанти) в елемент булеана. А отже, є взаємно однозначна відповідність між двійковими числами довжини p та елементами булеана (наприклад, 00...0 - це {}, а 11...1 - це початкова множина). Тепер зможете сформувати булеан?

Звісно, можна вручну реалізовувати операцію додавання (чи віднімання) 1 від числа за допомогою сірників та клею побітових операцій, але нащо, якщо це вже є вбудоване в процесор?

Здається, я починаю розуміти, зараз спробую написати на папері алгоритм

8

Re: Булеан множини

Перше наближення на Python:

def boolean(s):
    for i in range(2**len(s)):
        print('{',','.join(c for n,c in zip(('0'*len(s)+bin(i)[2:])[-len(s):],s) if n=='1'),'}')
>>> boolean("abc")
{  }
{ c }
{ b }
{ b,c }
{ a }
{ a,c }
{ a,b }
{ a,b,c }

Друге наближення:

def boolean(s):
    for i in range(2**len(s)):
        yield [c for n,c in zip(('0'*len(s)+bin(i)[2:])[-len(s):],s) if n=='1']
>>> print(list(boolean("abc")))
[[], ['c'], ['b'], ['b', 'c'], ['a'], ['a', 'c'], ['a', 'b'], ['a', 'b', 'c']]
>>> print(list(boolean([1,2,3])))
[[], [3], [2], [2, 3], [1], [1, 3], [1, 2], [1, 2, 3]]
Подякували: Q-bart1

9

Re: Булеан множини

Q-bart написав:
Master_Sergius написав:

Ну, можна погуглити трішки і зрозуміти що то таке той булеан взагалі.
Якщо X – множина {x,y,z}, то булеан (множина усіх підмножин):
{}, {x}, {y}, {z}, {x,y}, {x,z}, {y,z}, {x,y,z}

Ну і якби звідси задача уже не є складною. Якщо писати на Python, можна поглянути на бібліотеку itertools.

Та це все я загуглив. Як виглядає булеан - зрозуміло.
А от iteertools - banned to use. Самому треба написати

так і пиши.
а потім порівняй з кодом itertools для самовдосконалення:

Прихований текст
def combinations(iterable, r):
    # combinations('ABCD', 2) --> AB AC AD BC BD CD
    # combinations(range(4), 3) --> 012 013 023 123
    pool = tuple(iterable)
    n = len(pool)
    if r > n:
        return
    indices = list(range(r))
    yield tuple(pool[i] for i in indices)
    while True:
        for i in reversed(range(r)):
            if indices[i] != i + n - r:
                break
        else:
            return
        indices[i] += 1
        for j in range(i+1, r):
            indices[j] = indices[j-1] + 1
        yield tuple(pool[i] for i in indices)

10

Re: Булеан множини

Так це ж не combinations.

11

Re: Булеан множини

koala написав:

Так це ж не combinations.

хіба це не  itertools.combinations(iterable, r) for r in range(len(iterable) +1) ?

12

Re: Булеан множини

Для отримання булеана можна скористатися комбінаціями. Але нащо, якщо можна простіше?

13

Re: Булеан множини

Прихований текст

те відчуття, коли ти тупенький і не розумієш, про що йдеться..

Подякували: Q-bart1

14

Re: Булеан множини

Про те, що combinations повертає всі можливі комбінації по r елементів, і робить це з вкладеними циклами. А для того, щоб був булеан, треба застосувати ще один цикл.
А булеан за моїм алгоритмом (не за кодом, код скорочений коштом швидкості) отримується двома вкладеними циклами - по номеру і по бітах номера. Простіше не буде.
Ще б якось пітонізувати цей код :)

def boolean(iterable):
    iterable = tuple(iterable)
    for i in range(1<<len(iterable)):
        number = i #параметр буде зменшуватися у внутрішньому циклі, тому робимо копію i
        index = 0
        result = []
        while number>0:
            if number & 1:
                result.append(iterable[index])
            index += 1
            number >>= 1
        yield result
Подякували: 0xDADA11C7, sensei2

15

Re: Булеан множини

Прихований текст

І ці люди потім будуть щось там розповідати за БіґДата та ШІ.  :|  Як в тому анекдоті -- оскільки для будівництва сараю дощок не вистачає, то перейдемо одразу до будівництва комунізму.

Подякували: P.Y., quez, Q-bart3

16

Re: Булеан множини

koala написав:

Перше наближення на Python:

def boolean(s):
    for i in range(2**len(s)):
        print('{',','.join(c for n,c in zip(('0'*len(s)+bin(i)[2:])[-len(s):],s) if n=='1'),'}')
>>> boolean("abc")
{  }
{ c }
{ b }
{ b,c }
{ a }
{ a,c }
{ a,b }
{ a,b,c }

Друге наближення:

def boolean(s):
    for i in range(2**len(s)):
        yield [c for n,c in zip(('0'*len(s)+bin(i)[2:])[-len(s):],s) if n=='1']
>>> print(list(boolean("abc")))
[[], ['c'], ['b'], ['b', 'c'], ['a'], ['a', 'c'], ['a', 'b'], ['a', 'b', 'c']]
>>> print(list(boolean([1,2,3])))
[[], [3], [2], [2, 3], [1], [1, 3], [1, 2], [1, 2, 3]]


Я правильно все зрозумів:

1. Ми перебираємо всі числа від нуля до довжини булеана.

2.

('0' * len(s) + bin(i)[2:])[-len(s):]

Це число переводимо в бінарний формат.

3. І тут можемо якраз зробити це:

000 123 => {}
001 123 => {3}
010 123 => {2}
....

Так, геніально ж.
Дякую

17

Re: Булеан множини

Та я досі пам'ятаю, скільки я зібрав шишок, доки дійшов до цього. Спершу я намагався робити так: беремо пусту множину, намагаємося додати перший елемент. Якщо його нема, додаємо. Якщо є - видаляємо і намагаємося додати другий, і так в циклі. Після години тупих багів раптом збагнув, що це я роблю звичайний алгоритм додавання двійкових чисел - і тут все стало просто, але не дуже просто. Дуже просто стало, коли я перестав намагатися формувати маски виду 1<<j і став "з'їдати" копію i.

Подякували: Q-bart1

18

Re: Булеан множини

Так, і з останніми новаціями bin(i)[2:] записується як f"{i:b}".

Подякували: ping, Q-bart2