Ответы пользователя по тегу Алгоритмы
  • Как восстановить пароль?

    ayazer
    @ayazer
    Sr. Software Engineer
    питон3:
    import itertools
    
    list = ["a", "bb", "ccc"] #тут список слов. использоватся могут в любом порядке, но не более одного раза каждое
    result = []
    for i in range(1,len(list)+1):
        for iter in itertools.permutations(list,i):
            result.append("".join(iter))
    
    print(result)


    результат для списка "a", "bb", "ccc":
    ['a', 'bb', 'ccc', 'abb', 'accc', 'bba', 'bbccc', 'ccca', 'cccbb', 'abbccc', 'acccbb', 'bbaccc', 'bbccca', 'cccabb', 'cccbba']
    Ответ написан
    Комментировать
  • Алгоритм для минимизации стоимости товаров от разных поставщиков, какие ресурсы изучить?

    ayazer
    @ayazer
    Sr. Software Engineer
    угу. вы на своем примере поняли почему жадные алгоритмы не работают и практически пришли к branch-and-bound. "достаточно неплохое" решение можно получить эвристиками, лучшее - только перебором (правда, не полным, но иногда весьма длительным т.к. надо доказать что это действительно лучшее решение).

    у вас задача о рюкзаке (наполнить рюкзак необходимым кол-вом товаров при условии минимизации общей цены).

    вот тут я даже набрасывал пример решения такого типа задач с использованием готовых солверов (модель у вас другая, но принцип тот-же): Какие есть достойные альтернативы жадному алгоритму (greedy)?. По крайней мере там есть все ключевые слова чтоб понять что надо искать дальше

    (ну и да, это далеко не единственный способ решения, я просто ленивый и описать модель для мип солвера у меня выходит быстрее всего. Илья Николаевский и Сергей Соколов смогут еще много интересного добавить)
    Ответ написан
    Комментировать
  • Название алгоритма для генерации не похожих смиволов?

    ayazer
    @ayazer
    Sr. Software Engineer
    вам нужен альфанумерик без похожих символов. например DEC Alphabet:

    A,B,C,D,E,F,H,J,K,L,M,N,P,R,S,T,U,V
    Ответ написан
    Комментировать
  • Подсчет возможных комбинаций спрайтов в редакторе аватара / персонажа?

    ayazer
    @ayazer
    Sr. Software Engineer
    сумма = мощность прямого произведение всех можеств что у вас есть. т.е. S = A x B x C x ...., где A = {руки1, руки2, руки3, руки4, руки5}, B = {шапка1, шапка2 ...}, ...

    формула простая - просто перемножаете мощность всех множеств что у вас есть. т.е. как писали в комментариях - 5 * 10 * 20 ...

    сами группировки = само прямое прозведение. Т.к. в вашем случае у вас множества известны на входе, то нужно просто пробежаться по ним и собрать все возможные варианты. Выглядеть будет где-то так - https://github.com/novak-as/gimp-tileset-generator...

    UPD:
    Если вынести оттуда минимально необходимую часть (и выкинув усложнения не нужные в контексте этого примера) - выходит совсем немного

    (define (push stack value)
      (append (list value) stack)
      )
    
    (define (combine-list list1 list2)  
      (let combine-list ((set '()) (olist2 list2) (list1 list1) (list2 list2))
        (if (null? olist2)
            (if (null? list1)
                set
                (combine-list (push set (car list1)) olist2 (cdr list1) list2)
                )
            (if (null? list1)
                set
                (if (null? list2)
                    (combine-list set olist2 (cdr list1) olist2)
                    (if (list? (car list2))
                        (combine-list (push set (append (car list2) (list (car list1)))) olist2 list1 (cdr list2))
                        (combine-list (push set (list (car list2) (car list1))) olist2 list1 (cdr list2))
                        )
                    )
                )
            )
        )
      )
    
    (define (combine-groups groups)
      (let combine-groups ((result '()) (groups groups))
        (if (null? groups)
            result
            (combine-groups (combine-list (car groups) result) (cdr groups))
            )
        )
      )


    с результатом

    (combine-groups (list (list "head1" "head2" "head3") (list "body1" "body2" "body3") (list "left_hand_1" "left_hand_2") (list "right_hand_1" "right_hand_2")))
    
    '(("head1" "body3" "left_hand_1" "right_hand_2")
      ("head2" "body3" "left_hand_1" "right_hand_2")
      ("head3" "body3" "left_hand_1" "right_hand_2")
      ("head1" "body2" "left_hand_1" "right_hand_2")
      ("head2" "body2" "left_hand_1" "right_hand_2")
      ("head3" "body2" "left_hand_1" "right_hand_2")
      ("head1" "body1" "left_hand_1" "right_hand_2")
      ("head2" "body1" "left_hand_1" "right_hand_2")
      ("head3" "body1" "left_hand_1" "right_hand_2")
      ("head1" "body3" "left_hand_2" "right_hand_2")
      ("head2" "body3" "left_hand_2" "right_hand_2")
      ("head3" "body3" "left_hand_2" "right_hand_2")
      ("head1" "body2" "left_hand_2" "right_hand_2")
      ("head2" "body2" "left_hand_2" "right_hand_2")
      ("head3" "body2" "left_hand_2" "right_hand_2")
      ("head1" "body1" "left_hand_2" "right_hand_2")
      ("head2" "body1" "left_hand_2" "right_hand_2")
      ("head3" "body1" "left_hand_2" "right_hand_2")
      ("head1" "body3" "left_hand_1" "right_hand_1")
      ("head2" "body3" "left_hand_1" "right_hand_1")
      ("head3" "body3" "left_hand_1" "right_hand_1")
      ("head1" "body2" "left_hand_1" "right_hand_1")
      ("head2" "body2" "left_hand_1" "right_hand_1")
      ("head3" "body2" "left_hand_1" "right_hand_1")
      ("head1" "body1" "left_hand_1" "right_hand_1")
      ("head2" "body1" "left_hand_1" "right_hand_1")
      ("head3" "body1" "left_hand_1" "right_hand_1")
      ("head1" "body3" "left_hand_2" "right_hand_1")
      ("head2" "body3" "left_hand_2" "right_hand_1")
      ("head3" "body3" "left_hand_2" "right_hand_1")
      ("head1" "body2" "left_hand_2" "right_hand_1")
      ("head2" "body2" "left_hand_2" "right_hand_1")
      ("head3" "body2" "left_hand_2" "right_hand_1")
      ("head1" "body1" "left_hand_2" "right_hand_1")
      ("head2" "body1" "left_hand_2" "right_hand_1")
      ("head3" "body1" "left_hand_2" "right_hand_1"))
    Ответ написан
    Комментировать
  • Какие есть достойные альтернативы жадному алгоритму (greedy)?

    ayazer
    @ayazer
    Sr. Software Engineer
    ну после всех выяснений выходит что у вас действительно задача про n рюкзаков. Тогда как уже заметили
    - это действительно np-полная задача со всеми вытекающими проблемами и подходами к решению. Ну и я уже писал что с использованием MIP солвера оно решается буквально в пару строчек (без использования - писать кода прийдется заметно больше). Вот тут https://python-mip.readthedocs.io/_/downloads/en/l... даже есть пример для решения рюкзака, его надо просто расширить с условием что рюкзаков много и нужно строгое совпадение.

    зы: может оказатся что данных сильно много и подход с использованием MIP "в лоб" будет работать сильно медленно. В таком случае уже можно будет думать и комбинировать разные подходы.

    зыы: питоновский код чисто для примера, обертки для cbc (https://github.com/coin-or/Cbc) есть уже наверно для всех языков где это может понадобится, потому менятся будет только синтаксис. под капотом там одни фиг будет плюсовая либа

    на вид должно выйти что-то такое

    from typing import List
    from mip import Model, minimize, xsum, BINARY
    
    
    def solve(input_values: List[int], target_values: List[int]):
    
        model = Model("m")
    
        bin_input_is_used_to_build_target = {}
    
        for index in range(0, len(input_values)):
            bin_input_is_used_to_build_target[index] = [model.add_var(var_type=BINARY) for _ in target_values]
    
    
        model.objective = minimize(
            xsum(
                bin_input_is_used_to_build_target[input_index][target_index] * input_values[input_index]
                    for input_index in range(0, len(input_values))
                    for target_index in range(0, len(target_values)))
        )
    
        for target_index in range(0, len(target_values)):
            model += xsum(bin_input_is_used_to_build_target[input_index][target_index] * input_values[input_index]
                           for input_index in range(0, len(input_values))) == target_values[target_index]
    
        for input_index in range(0, len(input_values)):
            model += xsum(bin_input_is_used_to_build_target[input_index][target_index] * input_values[input_index]
                          for target_index in range(0, len(target_values))) <= input_values[input_index]
    
        model.optimize()
    
        result = {}
    
        for target_index in range(0, len(target_values)):
            result[target_index] = [input_values[input_index]
                                        for input_index in range(0, len(input_values))
                                        if bin_input_is_used_to_build_target[input_index][target_index].x >= 0.99]
    
    
        return result
    
    
    if __name__ == "__main__":
    
        input_values = [1, 2, 1, 1, 1, 1, 3, 2, 5]
    
        target_values= [3, 4, 5, 5]
    
        result = solve(input_values, target_values)
    
        for i in range(0, len(result)):
            print(target_values[i], " : ", result[i])
    
        # 3: [2, 1]
        # 4: [1, 1, 2]
        # 5: [5]
        # 5: [1, 1, 3]
    Ответ написан
    2 комментария
  • Убрать все повторяющиеся элемента за O(n) времени?

    ayazer
    @ayazer
    Sr. Software Engineer
    используйте доп. структуру данных чтоб хранить кол-во вхождений каждого элемента в список. т.е. для каждого элемента в списке (сложность O(n)) нужно увеличить счетчик в этой структуре данных (в случ. с хеш таблицой это O(n) в худшем и О(1) в среднем). и потом еще раз пройтись по хештаблице и достать с нее все элементы где счетчик = 1 (сложность O(n)). в итоге даже сложность для худшего случая будет o(n + n + n) = O(n)

    те
    var inputArray = new[] { 1, 2, 3, 4, 5, 4, 3, 2, 1 };
    var set = new Dictionary<int, int>();
    
    foreach (var val in inputArray)
    {
        if (!set.ContainsKey(val))
        {
            set.Add(val, 1);
        }
        else
        {
            set[val] = set[val] + 1;
        }
    }
    
    var result = new List<int>();
    foreach (var val in set)
    {
        if (val.Value == 1)
        {
            result.Add(val.Key);
        }
    }
    
    return result; //[5]

    ^ можете считать примером на псевдокоде, читатся вроде должно без проблем
    Ответ написан
    2 комментария
  • Обход Binary-Tree, как сделать быстрее?

    ayazer
    @ayazer
    Sr. Software Engineer
    1) питон не умеет отбрасывать хвост. Использовать рекурсию я ЯП которые не умееют в хвостовую оптимизацию - так себе идея. Особенно на абстрактной задаче на обход дерева. Особенно если сразу сказали что дерево "сильно несбалансированное". Потому легким движением ваше решение превращается в тыкву.

    root1 = Node(1)
    cur_node = root1
    for i in range (0, 1000):
        cur_node.left = Node(i)
        cur_node = cur_node.left


    2) вот эти два дерева у вас выходят одинаковыми. Как графы - да, они одинаковы т.к. симметричны. Как деревья - нет, они разные.
    root1 = Node(1)
    root1.right = Node(2)
    root1.right.right = Node(3)
    
    root2 = Node(3)
    root2.left = Node(2)
    root2.left.left = Node(1)


    Так что сначала нужно пофиксить, а потом уже думать как сделать быстрее
    Ответ написан
  • Как управлять памятью в javascript?

    ayazer
    @ayazer
    Sr. Software Engineer
    это не относится в джаваскрипту, это типичная проблема когда данных слишком много чтоб с ними работать "в лоб".

    так что (если уж хочется ради интереса решить эту задачу через бинарный поиск) распиливайте дерево на несколько мелких. Ведь с каждым шагом область поиска сужается в 2 раза. Если все данные занимают 60Гб (как написал Сергей Соколов), то после первых 5 шагов искать нужно будет уже только в 3.25Гб. Как вариант - используйте 1 дерево чтоб сузить область поиска до того размера который уже влазит в память, и потом уже загружайте второе дерево и ищите в нем
    Ответ написан
    5 комментариев
  • Когда использовать try и catch?

    ayazer
    @ayazer
    Sr. Software Engineer
    странно что никто не сказал что try-catch еще следует использовать когда мы не знаем как обрабатывать возникшую ситуацию, и нам надо просто вернуть управление выше по стеку.
    Ответ написан
    Комментировать