ReSQL.ru
     
powered by simpleCommunicator - 2.0.61     © 2026 Programmizd 02
Мобильная версия    Контакт    Правила    FAQ    Помощь
Целевая тема:
Создать новую тему:
Автор:
Закрыть
Цитировать
Доб. в избранное | Игнор. тему | Прикреп. тему | Пометить прочит. / непрочит. | Фильтр
Форумы / Программирование [игнор отключен] [закрыт для гостей] / все комбинации из 3-х элементов: алгоритм поиска
25 сообщений из 57, страница 1 из 3
  1  все
все комбинации из 3-х элементов: алгоритм поиска
    #39383142
mini.weblab
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mini.weblab
Участник
имеется последовательность чисел, из последовательности нужно выбрать все возможные комбинации из 3х элементов

существует ли более эффективное решение, чем O(n^3) ?

O(n^3) решение

Код: python
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
def get_triplets(sqc):
    """ Sequence sqc is a char string: sqc = str(12345) """
    l = len(sqc)
    triplets = []
    for i in range(l-2):
        for j in range(i+1, l-1):
            for k in range(j+1, l):
                triplet = (sqc[i],sqc[j],sqc[k])
                triplets.append(triplet)
    return triplets
...
Рейтинг: 0 / 0
12.01.2017, 13:50
| Ответить | Цитировать | Написать  
все комбинации из 3-х элементов: алгоритм поиска
    #39383167
Dima T
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Dima T
Участник
Тут нет поиска. Результирующая таблица будет n^3 строк.
Разве что как-то append() оптимизировать, питон не знаю, в других ЯП тормозит выделение памяти, поэтому по хорошему надо сразу создать массив нужного размера, затем заполнять.
...
Рейтинг: 0 / 0
12.01.2017, 14:09
| Ответить | Цитировать | Написать  
все комбинации из 3-х элементов: алгоритм поиска
    #39383177
mini.weblab
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mini.weblab
Участник
Dima T,
спасибо, да ты прав по n^3.
попробую поэкспериментировать с выделением памяти
...
Рейтинг: 0 / 0
12.01.2017, 14:24
| Ответить | Цитировать | Написать  
все комбинации из 3-х элементов: алгоритм поиска
    #39383334
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
mini.weblab,

Я не специалист в Питоне но как мне кажется здесь очень удобно применить генераторы последовательности

Возможно что в предлагаемой мной реализации код станет красивее и необходимость в формировании толстых
Строк отпадает.
...
Рейтинг: 0 / 0
12.01.2017, 16:20
| Ответить | Цитировать | Написать  
все комбинации из 3-х элементов: алгоритм поиска
    #39383633
mini.weblab
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mini.weblab
Участник
mayton,

основная проблема в том, что алгоритм O(n^3) в задаче не прокатывает, и решение через триплеты не работает :(
(я запустила тесты с пустым циклом, и они отвалились по тайм ауту)
...
Рейтинг: 0 / 0
12.01.2017, 22:52
| Ответить | Цитировать | Написать  
все комбинации из 3-х элементов: алгоритм поиска
    #39383666
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
Решение существует если вы просто неверно описали нам постановку.

Возможно речь идет о перестановках? Или permutations?

https://ru.wikipedia.org/wiki/Перестановка
...
Рейтинг: 0 / 0
13.01.2017, 00:32
| Ответить | Цитировать | Написать  
все комбинации из 3-х элементов: алгоритм поиска
    #39383678
mini.weblab
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mini.weblab
Участник
я решила задачу, используя триплет-комбинации O(n^3), но существует лучшее решение O(n)
задача

 

рабочий брутфорс (чтобы было понятно, что есть правильно по условию)
Код: python
1.
2.
3.
4.
5.
6.
7.
def test_num_of_subsequences(s):    
    l = len(s)
    cnt = 0
    for i in range(1, l+1):
        c = sum(1 for item in combinations(s, i) if  int("".join(item)) % 8 == 0) 
        cnt = cnt + c
    return cnt % (pow(10,9)+7)

...
Рейтинг: 0 / 0
13.01.2017, 01:36
| Ответить | Цитировать | Написать  
все комбинации из 3-х элементов: алгоритм поиска
    #39383781
Фотография S.G.
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
S.G.
Участник
mini.weblab задача



автор404

We could not find the page you were looking for, so we found something to make you laugh to make up for it.
...
Рейтинг: 0 / 0
13.01.2017, 09:33
| Ответить | Цитировать | Написать  
все комбинации из 3-х элементов: алгоритм поиска
    #39383809
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
Я тоже вижу 404
...
Рейтинг: 0 / 0
13.01.2017, 10:12
| Ответить | Цитировать | Написать  
все комбинации из 3-х элементов: алгоритм поиска
    #39383895
kealon(Ruslan)
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
kealon(Ruslan)
Участник
mini.weblabимеется последовательность чисел, из последовательности нужно выбрать все возможные комбинации из 3х элементов

существует ли более эффективное решение, чем O(n^3) ?

O(n^3) решение

Код: python
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
def get_triplets(sqc):
    """ Sequence sqc is a char string: sqc = str(12345) """
    l = len(sqc)
    triplets = []
    for i in range(l-2):
        for j in range(i+1, l-1):
            for k in range(j+1, l):
                triplet = (sqc[i],sqc[j],sqc[k])
                triplets.append(triplet)
    return triplets


такое впечатление что условие задачи неполное. Это стало бы ЗАДАЧЕЙ если бы нужно было, например, выбрать уникальные комбинации или подсчитать их.
...
Рейтинг: 0 / 0
13.01.2017, 11:12
| Ответить | Цитировать | Написать  
все комбинации из 3-х элементов: алгоритм поиска
    #39384077
просто я
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
просто я
Гость
https://www.hackerrank.com/contests/w28/challenges
...
Рейтинг: 0 / 0
13.01.2017, 13:12
| Ответить | Цитировать | Написать  
все комбинации из 3-х элементов: алгоритм поиска
    #39384207
mini.weblab
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mini.weblab
Участник
1.
раньше можно было смотреть задачи без регистрации =)
условие задачиGiven an n-digit positive integer, count and print the number of subsequences formed by concatenating the given number's digits that are divisible by 8. As the result can be large, print the result modulo 10^9 + 7

Ограничение: 1 <= n <= 2*10^5

2.
есть проблемы с условием, поэтому я выложила брутфорс, который делает, то что требуется по тестам и по условию
3.
у меня было решение через триплеты сложностью O(n^3), оно не сработало и улучшить его не получится. (о чем DimaT ответил в самом первом посте. )
4.
сложность проходного решения должна быть O(n). O(n*log(n)) - отваливается по тайм-ауту
...
Рейтинг: 0 / 0
13.01.2017, 14:38
| Ответить | Цитировать | Написать  
все комбинации из 3-х элементов: алгоритм поиска
    #39384266
Dima T
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Dima T
Участник
Не надо все 2*10^5 разрядов перебирать, 8*10^15 если даже по миллиарду в секунду - 3 месяца перебора :)

Цифр всего 10. В худшем случае, если каждая трижды встречается будет всего 1000 комбинаций.
Выкидываем то что не делится на 8, остается 125.

Дальше обработка каждой комбинации: убираем эти 3 числа и считаем скольки способами можно перетасовать оставшиеся, комбинаторику вспоминай, тут главное учесть повторы, т.е. например из 123 получается 6 комбинаций, а из 112 только 3 (112, 121, 211).
...
Рейтинг: 0 / 0
13.01.2017, 15:24
| Ответить | Цитировать | Написать  
все комбинации из 3-х элементов: алгоритм поиска
    #39384293
mini.weblab
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mini.weblab
Участник
Dima T,

спасибо, буду пробовать

последовательности которые получаются по условию задачи из 112:
[1, 1, 2, 11, 12, 12, 112]

Код для получения последовательностей
 
Код: python
1.
2.
3.
4.
5.
6.
def all_subsequences(s):    
    l = len(s)
    subs = []
    for i in range(1, l+1):        
        subs.extend([int("".join(item)) for item in combinations(s, i)])
    return subs

...
Рейтинг: 0 / 0
13.01.2017, 15:49
| Ответить | Цитировать | Написать  
все комбинации из 3-х элементов: алгоритм поиска
    #39384310
Dima T
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Dima T
Участник
mini.weblabпоследовательности которые получаются по условию задачи из 112:
[1, 1, 2, 11, 12, 12, 112]
С английским у меня не очень, если я правильно это понял
subsequences formed by concatenating the given number's digits
то из 3-хзначного числа могут только 3-хзначные получаться
...
Рейтинг: 0 / 0
13.01.2017, 16:07
| Ответить | Цитировать | Написать  
все комбинации из 3-х элементов: алгоритм поиска
    #39384321
ermak.nn
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
ermak.nn
Участник
Dima TНе надо все 2*10^5 разрядов перебирать, 8*10^15 если даже по миллиарду в секунду - 3 месяца перебора :)

Цифр всего 10. В худшем случае, если каждая трижды встречается будет всего 1000 комбинаций.
Выкидываем то что не делится на 8, остается 125.

Дальше обработка каждой комбинации: убираем эти 3 числа и считаем скольки способами можно перетасовать оставшиеся, комбинаторику вспоминай, тут главное учесть повторы, т.е. например из 123 получается 6 комбинаций, а из 112 только 3 (112, 121, 211).

Не совсем понял про худший случай (трижды встречается), поясните, пожалуйста.

Мне кажется, что условие задачи достаточно запутанно:
count and print the number of subsequences formed by concatenating the given number's digits that are divisible by 8
Тут либо не хватает разъяснений, либо запятых. Потому что непонятно, что должно делиться на 8: составленные числа или цифры из n. А также, как применяется subsequences.
Судя по примеру #0 можно додумать, что имеется ввиду, что мы формируем комбинации не переставляя цифры из n, т.е. если n = 123456789, то 987654321 составить нельзя .
...
Рейтинг: 0 / 0
13.01.2017, 16:13
| Ответить | Цитировать | Написать  
все комбинации из 3-х элементов: алгоритм поиска
    #39384329
ermak.nn
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
ermak.nn
Участник
mini.weblabDima T,

спасибо, буду пробовать

последовательности которые получаются по условию задачи из 112:
[1, 1, 2, 11, 12, 12, 112]

Код для получения последовательностей
 
Код: python
1.
2.
3.
4.
5.
6.
def all_subsequences(s):    
    l = len(s)
    subs = []
    for i in range(1, l+1):        
        subs.extend([int("".join(item)) for item in combinations(s, i)])
    return subs



Как мне кажется, тут перебор нужен умный, например, числа с нечетной цифрой в конце однозначно не будут делится на 8. И я бы строил решение с конца числа n, т.е. находил четное число, а дальше находил бы все комбинации, которые делятся на 8.
Например,

n=59649301

1. 1 - нечетное, пропускаем
2. 0 - четное, формируем все числа, которые делятся на 8
2.1. 2 цифры:
2.1.1. 30 не делится на 8
2.1.2. 90 не делится на 8
2.1.3. 40 делится на 8
...
2.2. 3 цифры
2.2.1. 930 не делится на 8
и т.д.
Решение влоб. Дальше надо оптмизировать.
...
Рейтинг: 0 / 0
13.01.2017, 16:20
| Ответить | Цитировать | Написать  
все комбинации из 3-х элементов: алгоритм поиска
    #39384331
mini.weblab
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mini.weblab
Участник
пример:

пусть число n = 9680

нам нужно получить все последовательности дающие остаток 0 при делении на 8

1) Все возможные последовательности
[9, 6, 8, 0, 96, 98, 90, 68, 60, 80, 968, 960, 980, 680, 9680]

2) Последовательности, удовлетворящие условию задачи
[8, 0, 96, 80, 968, 960, 680, 9680]

3) Ответ: 8
...
Рейтинг: 0 / 0
13.01.2017, 16:20
| Ответить | Цитировать | Написать  
все комбинации из 3-х элементов: алгоритм поиска
    #39384337
Dima T
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Dima T
Участник
ermak.nn,

число делится на 8 если его последние три разряда делятся на 8. т.е. надо составить все возможные комбинации из 3-х цифр. Например 888 моно составить только если 8-ка повторяется 3 и более раз в исходном.
...
Рейтинг: 0 / 0
13.01.2017, 16:27
| Ответить | Цитировать | Написать  
все комбинации из 3-х элементов: алгоритм поиска
    #39384340
Dima T
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Dima T
Участник
mini.weblabпример:

пусть число n = 9680
ermak.nnНапример,

n=59649301
Вы условия внимательно читали?
Given an n-digit positive integer ... Ограничение: 1 <= n <= 2*10^5
2*10^5 это не максимум 200000, а 10^200000, т.е. 200000 разрядов.
...
Рейтинг: 0 / 0
13.01.2017, 16:32
| Ответить | Цитировать | Написать  
все комбинации из 3-х элементов: алгоритм поиска
    #39384341
ermak.nn
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
ermak.nn
Участник
Dima T,
Спасибо, не знал и забыл я загуглить.

Тогда вы верно все написали. Только там не комбинации надо искать, ибо порядок исходный надо сохранять, как я понял.
...
Рейтинг: 0 / 0
13.01.2017, 16:36
| Ответить | Цитировать | Написать  
все комбинации из 3-х элементов: алгоритм поиска
    #39384345
ermak.nn
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
ermak.nn
Участник
Dima T,
Условие то я правильно прочитал, перепутал в посте. Не n, а вторая строка, которая есть последовательность цифр.
...
Рейтинг: 0 / 0
13.01.2017, 16:40
| Ответить | Цитировать | Написать  
все комбинации из 3-х элементов: алгоритм поиска
    #39384354
mini.weblab
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mini.weblab
Участник
Dima T,

все правильно говоришь, n - это число разрядов.
если мой пример переписать в точности по требованиям HR:

Input:
4
9680

Output:
8
...
Рейтинг: 0 / 0
13.01.2017, 16:44
| Ответить | Цитировать | Написать  
все комбинации из 3-х элементов: алгоритм поиска
    #39384417
Dima T
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Dima T
Участник
mini.weblabпример:

пусть число n = 9680

нам нужно получить все последовательности дающие остаток 0 при делении на 8

1) Все возможные последовательности
[9, 6, 8, 0, 96, 98, 90, 68, 60, 80, 968, 960, 980, 680, 9680]

2) Последовательности, удовлетворящие условию задачи
[8, 0, 96, 80, 968, 960, 680, 9680]

3) Ответ: 8
Еще есть [896, 8096, 8960, 9608] т.е. ответ 12.

У меня получилось 6 [896, 968, 8096, 8960, 9608, 9680]
...
Рейтинг: 0 / 0
13.01.2017, 17:39
| Ответить | Цитировать | Написать  
все комбинации из 3-х элементов: алгоритм поиска
    #39384474
Фотография softwarer
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
softwarer
Участник
mini.weblabсуществует ли более эффективное решение, чем O(n^3) ?
Не стоит путать O(n) и O(n^3)
...
Рейтинг: 0 / 0
13.01.2017, 19:06
| Ответить | Цитировать | Написать  
25 сообщений из 57, страница 1 из 3
  1  все
Форумы / Программирование [игнор отключен] [закрыт для гостей] / все комбинации из 3-х элементов: алгоритм поиска
Найденые пользователи ...
Разблокировать пользователей ...
Читали тему (0):
Читали форум (0):
Пользователи онлайн (0):
Польз. соглашение   Полит. конфиден.  
NoSQL.ru       Кролег: Проекты, Новости, Чат       РЕД ФОРУМ       Фотоальбом: Участники, Встречи
Закрыть
start [/forum/topic.php?fid=16&msg=39384341&tid=1340510]:
 0ms
get settings:
 9ms
get forum list:
 19ms
check forum access:
 4ms
check topic access:
 4ms
track hit:
 152ms
get topic data:
 10ms
get forum data:
 2ms
get page messages:
 85ms
get tp. blocked users:
 1ms
others: 240ms
total:  526ms
созд. / загр.: 526ms
x
x
Закрыть


Просмотр
0 / 0
Close
Debug Console [Select Text]