Домашняя страница Undo Do New Save Карта сайта Обратная связь Поиск по форуму
МИР MS EXCEL - Гость.xls

Вход

Регистрация

Напомнить пароль

 

= Мир MS Excel/Самая длинная цепочка совпадений - Мир MS Excel

Регистрация · Логин: · Пароль: · · Забыли пароль?
  • Страница 1 из 1
  • 1
Модератор форума: _Boroda_, Pelena, китин  
Мир MS Excel » Работа и общение » Мозговой штурм » Самая длинная цепочка совпадений (В столбце формулами найти максимальную длину и два начала)
Самая длинная цепочка совпадений
Понравилось?
Светлый Дата: Пятница, 25.09.2020, 09:04 | Сообщение № 1
Группа: Друзья
Ранг: Старожил
Сообщений: 1485
Репутация: 387 ±
Замечаний: 0% ±

Excel 2010, 2013
Всеобщий привет!
Какой-то долгий штиль образовался. Поштормим? Поштурмуем?
Подобная тема уже была, но там образец задавался конкретный. Здесь образца нет.
Задан массив из 300 элементов (может быть неполный).
Формулой найти максимальную длину совпадающих последовательных элементов из разных мест этого массива. Также найти начало первой цепочки и второй.
Итого, три формулы.
Файл использовал из раздела вопросов.
У меня получились непротягиваемые формулы 158+183+187=528 символов.
С дополнительной ячейкой 158+172+13+17=360 символов.
С использованием умной таблицы из этого файла 227+238+28+51=544 символа.
Вскрываться предлагаю 05.10.2020
К сообщению приложен файл: SovpVopr.xlsx(22.9 Kb)


Программировать проще, чем писать стихи.
 
Ответить
СообщениеВсеобщий привет!
Какой-то долгий штиль образовался. Поштормим? Поштурмуем?
Подобная тема уже была, но там образец задавался конкретный. Здесь образца нет.
Задан массив из 300 элементов (может быть неполный).
Формулой найти максимальную длину совпадающих последовательных элементов из разных мест этого массива. Также найти начало первой цепочки и второй.
Итого, три формулы.
Файл использовал из раздела вопросов.
У меня получились непротягиваемые формулы 158+183+187=528 символов.
С дополнительной ячейкой 158+172+13+17=360 символов.
С использованием умной таблицы из этого файла 227+238+28+51=544 символа.
Вскрываться предлагаю 05.10.2020

Автор - Светлый
Дата добавления - 25.09.2020 в 09:04
Каракулькин Дата: Пятница, 25.09.2020, 18:40 | Сообщение № 2
Группа: Пользователи
Ранг: Прохожий
Сообщений: 3
Репутация: 0 ±
Замечаний: 0% ±

Excel 2003
Цитата Светлый, 25.09.2020 в 09:04, в сообщении № 1 ()
совпадающих последовательных элементов из разных мест этого массива

Какая-то туманная формулировка. Два последовательных элемента не могут быть в разных местах.
 
Ответить
Сообщение
Цитата Светлый, 25.09.2020 в 09:04, в сообщении № 1 ()
совпадающих последовательных элементов из разных мест этого массива

Какая-то туманная формулировка. Два последовательных элемента не могут быть в разных местах.

Автор - Каракулькин
Дата добавления - 25.09.2020 в 18:40
Светлый Дата: Суббота, 26.09.2020, 23:08 | Сообщение № 3
Группа: Друзья
Ранг: Старожил
Сообщений: 1485
Репутация: 387 ±
Замечаний: 0% ±

Excel 2010, 2013
Цитата Каракулькин, 25.09.2020 в 18:40, в сообщении № 2 ()
Два последовательных элемента не могут быть в разных местах
Надо было вставить слово "цепочек".
Одинаковые последовательности вполне могут начинаться в разных местах массива. В файле возле массива жёлтым и синим отмечены примеры таких последовательностей.


Программировать проще, чем писать стихи.

Сообщение отредактировал Светлый - Суббота, 26.09.2020, 23:14
 
Ответить
Сообщение
Цитата Каракулькин, 25.09.2020 в 18:40, в сообщении № 2 ()
Два последовательных элемента не могут быть в разных местах
Надо было вставить слово "цепочек".
Одинаковые последовательности вполне могут начинаться в разных местах массива. В файле возле массива жёлтым и синим отмечены примеры таких последовательностей.

Автор - Светлый
Дата добавления - 26.09.2020 в 23:08
Светлый Дата: Понедельник, 05.10.2020, 14:42 | Сообщение № 4
Группа: Друзья
Ранг: Старожил
Сообщений: 1485
Репутация: 387 ±
Замечаний: 0% ±

Excel 2010, 2013
Или задача очень трудная, или лучшие умы заняты более насущными проблемами, остался я в гордом одиночестве. Или это мой прокол при постановке задачи? Офис 2003 поддерживает 256 столбцов, а я задал 300 элементов. Давайте ограничимся массивом в 200 элементов и продлим ещё на неделю.
Виноват, исправлюсь.


Программировать проще, чем писать стихи.
 
Ответить
СообщениеИли задача очень трудная, или лучшие умы заняты более насущными проблемами, остался я в гордом одиночестве. Или это мой прокол при постановке задачи? Офис 2003 поддерживает 256 столбцов, а я задал 300 элементов. Давайте ограничимся массивом в 200 элементов и продлим ещё на неделю.
Виноват, исправлюсь.

Автор - Светлый
Дата добавления - 05.10.2020 в 14:42
MCH Дата: Понедельник, 05.10.2020, 19:49 | Сообщение № 5
Группа: Админы
Ранг: Старожил
Сообщений: 1953
Репутация: 723 ±
Замечаний: ±

Сейчас в отпуске, приеду к концу недели. Если других участников не будет,подомаю над задачей чуть позже.
Пока с ходу алгоритма нет
 
Ответить
СообщениеСейчас в отпуске, приеду к концу недели. Если других участников не будет,подомаю над задачей чуть позже.
Пока с ходу алгоритма нет

Автор - MCH
Дата добавления - 05.10.2020 в 19:49
Светлый Дата: Понедельник, 12.10.2020, 07:59 | Сообщение № 6
Группа: Друзья
Ранг: Старожил
Сообщений: 1485
Репутация: 387 ±
Замечаний: 0% ±

Excel 2010, 2013
Ну что? Вскрываться?


Программировать проще, чем писать стихи.
 
Ответить
СообщениеНу что? Вскрываться?

Автор - Светлый
Дата добавления - 12.10.2020 в 07:59
MCH Дата: Понедельник, 12.10.2020, 08:33 | Сообщение № 7
Группа: Админы
Ранг: Старожил
Сообщений: 1953
Репутация: 723 ±
Замечаний: ±

Пока нет, не было времени подумать над задачей, да и остальные участники не обозначились
 
Ответить
СообщениеПока нет, не было времени подумать над задачей, да и остальные участники не обозначились

Автор - MCH
Дата добавления - 12.10.2020 в 08:33
MCH Дата: Понедельник, 12.10.2020, 11:53 | Сообщение № 8
Группа: Админы
Ранг: Старожил
Сообщений: 1953
Репутация: 723 ±
Замечаний: ±

Исходя из поставленной задачи:
Цитата Светлый, 25.09.2020 в 09:04, в сообщении № 1 ()
Формулой найти максимальную длину совпадающих последовательных элементов из разных мест этого массива. Также найти начало первой цепочки и второй.

пока нет решения

по набору данных в последовательность из 5ти элементов у меня нашлись следующие цепочки (без учета последовательно расположенных цепочек):
Длина Нач. 1 Нач. 2
5 3 18
5 18 101
5 30 67
5 37 102
5 43 85
5 56 74
5 65 80
 
Ответить
СообщениеИсходя из поставленной задачи:
Цитата Светлый, 25.09.2020 в 09:04, в сообщении № 1 ()
Формулой найти максимальную длину совпадающих последовательных элементов из разных мест этого массива. Также найти начало первой цепочки и второй.

пока нет решения

по набору данных в последовательность из 5ти элементов у меня нашлись следующие цепочки (без учета последовательно расположенных цепочек):
Длина Нач. 1 Нач. 2
5 3 18
5 18 101
5 30 67
5 37 102
5 43 85
5 56 74
5 65 80

Автор - MCH
Дата добавления - 12.10.2020 в 11:53
MCH Дата: Вторник, 13.10.2020, 08:53 | Сообщение № 9
Группа: Админы
Ранг: Старожил
Сообщений: 1953
Репутация: 723 ±
Замечаний: ±

Что то я застрял на этой задаче
Хочу вначале найти эффективное решение на макросах из серии: Алгоритм Кнута-Морриса-Пратта
а затем переводить его (либо тривиальное и неоптимальное решение) на формулы.
 
Ответить
СообщениеЧто то я застрял на этой задаче
Хочу вначале найти эффективное решение на макросах из серии: Алгоритм Кнута-Морриса-Пратта
а затем переводить его (либо тривиальное и неоптимальное решение) на формулы.

Автор - MCH
Дата добавления - 13.10.2020 в 08:53
MCH Дата: Вторник, 13.10.2020, 10:53 | Сообщение № 10
Группа: Админы
Ранг: Старожил
Сообщений: 1953
Репутация: 723 ±
Замечаний: ±

Формульного решения нет, есть решение на макросах со сложностью O(n^2)
на 10 тыс. данных находит максимальную повторяющуюся последовательность менее чем за 10 секунд

Выкладывать решение на макросах?
 
Ответить
СообщениеФормульного решения нет, есть решение на макросах со сложностью O(n^2)
на 10 тыс. данных находит максимальную повторяющуюся последовательность менее чем за 10 секунд

Выкладывать решение на макросах?

Автор - MCH
Дата добавления - 13.10.2020 в 10:53
Светлый Дата: Вторник, 13.10.2020, 12:59 | Сообщение № 11
Группа: Друзья
Ранг: Старожил
Сообщений: 1485
Репутация: 387 ±
Замечаний: 0% ±

Excel 2010, 2013
Или задача очень трудная, или лучшие умы заняты более насущными проблемами. Но наши не сдаются. Не получается формулами, решим макросами, зато большие массивы. Придётся вскрываться. Вот три массивные формулы. Длина цепочки, начало первой цепочки и начало второй цепочки (526 символов):
Код
=МАКС(ЧАСТОТА(СТРОКА(1:40001);ЕСЛИ(ЧАСТОТА((D1:D200=ТРАНСП(D2:D201))*(D1:D200>0)*(200*СТОЛБЕЦ(A:GR)-199*СТРОКА(1:200));СТРОКА(1:40000))=1;;СТРОКА(1:40001))))-1
Код
=ОСТАТ(ПОИСКПОЗ(L2+1;ЧАСТОТА(СТРОКА(1:40001);ЕСЛИ(ЧАСТОТА((D1:D200=ТРАНСП(D2:D201))*(D1:D200>0)*(200*СТОЛБЕЦ(A:GR)-199*СТРОКА(1:200));СТРОКА(1:40000))=1;;СТРОКА(1:40001)));)-L2-1;200)
Код
=(ПОИСКПОЗ(L2+1;ЧАСТОТА(СТРОКА(1:40001);ЕСЛИ(ЧАСТОТА((D1:D200=ТРАНСП(D2:D201))*(D1:D200>0)*(200*СТОЛБЕЦ(A:GR)-199*СТРОКА(1:200));СТРОКА(1:40000))=1;;СТРОКА(1:40001)));)-L2-1+199*M2)/200+1
Остальные формулы в файле.
Принцип: сквозная нумерация сдвигов массивов (два способа: вертикальный, используя СМЕЩ() и диагональный, ТРАНСП() ), чтобы последовательные совпадения отличались на 1. Функцией ЧАСТОТА находим все значения, отличающиеся на 1 и ещё раз функцией ЧАСТОТА находим самую длинную цепочку 1 (для функции это будут 0). Находим его номер, ПОИСКПОЗ(). Из этого номера вычисляем начало первой цепочки, а затем начало второй.
Жалко. Надеялся, что у асов родятся какие-нибудь хитроумные решения. Тогда пусть от моего решения кому-то польза будет.
Выкладывать решение на макросах?
Конечно. Как бонус. Кому-нибудь пригодится.

А ведь первая формула уже была опубликована в Вопросах с месяц пару месяцев назад. Но вопрос темы уже был решен и никто не посмотрел.
К сообщению приложен файл: SovpOtv.xlsx(24.0 Kb)


Программировать проще, чем писать стихи.

Сообщение отредактировал Светлый - Вторник, 13.10.2020, 13:17
 
Ответить
СообщениеИли задача очень трудная, или лучшие умы заняты более насущными проблемами. Но наши не сдаются. Не получается формулами, решим макросами, зато большие массивы. Придётся вскрываться. Вот три массивные формулы. Длина цепочки, начало первой цепочки и начало второй цепочки (526 символов):
Код
=МАКС(ЧАСТОТА(СТРОКА(1:40001);ЕСЛИ(ЧАСТОТА((D1:D200=ТРАНСП(D2:D201))*(D1:D200>0)*(200*СТОЛБЕЦ(A:GR)-199*СТРОКА(1:200));СТРОКА(1:40000))=1;;СТРОКА(1:40001))))-1
Код
=ОСТАТ(ПОИСКПОЗ(L2+1;ЧАСТОТА(СТРОКА(1:40001);ЕСЛИ(ЧАСТОТА((D1:D200=ТРАНСП(D2:D201))*(D1:D200>0)*(200*СТОЛБЕЦ(A:GR)-199*СТРОКА(1:200));СТРОКА(1:40000))=1;;СТРОКА(1:40001)));)-L2-1;200)
Код
=(ПОИСКПОЗ(L2+1;ЧАСТОТА(СТРОКА(1:40001);ЕСЛИ(ЧАСТОТА((D1:D200=ТРАНСП(D2:D201))*(D1:D200>0)*(200*СТОЛБЕЦ(A:GR)-199*СТРОКА(1:200));СТРОКА(1:40000))=1;;СТРОКА(1:40001)));)-L2-1+199*M2)/200+1
Остальные формулы в файле.
Принцип: сквозная нумерация сдвигов массивов (два способа: вертикальный, используя СМЕЩ() и диагональный, ТРАНСП() ), чтобы последовательные совпадения отличались на 1. Функцией ЧАСТОТА находим все значения, отличающиеся на 1 и ещё раз функцией ЧАСТОТА находим самую длинную цепочку 1 (для функции это будут 0). Находим его номер, ПОИСКПОЗ(). Из этого номера вычисляем начало первой цепочки, а затем начало второй.
Жалко. Надеялся, что у асов родятся какие-нибудь хитроумные решения. Тогда пусть от моего решения кому-то польза будет.
Выкладывать решение на макросах?
Конечно. Как бонус. Кому-нибудь пригодится.

А ведь первая формула уже была опубликована в Вопросах с месяц пару месяцев назад. Но вопрос темы уже был решен и никто не посмотрел.

Автор - Светлый
Дата добавления - 13.10.2020 в 12:59
MCH Дата: Вторник, 13.10.2020, 13:13 | Сообщение № 12
Группа: Админы
Ранг: Старожил
Сообщений: 1953
Репутация: 723 ±
Замечаний: ±

Решение на макросах
Применимо для наборов данных в несколько десятков тысяч значений
К сообщению приложен файл: SovpVopr2.xlsb(285.7 Kb)
 
Ответить
СообщениеРешение на макросах
Применимо для наборов данных в несколько десятков тысяч значений

Автор - MCH
Дата добавления - 13.10.2020 в 13:13
MCH Дата: Вторник, 13.10.2020, 15:47 | Сообщение № 13
Группа: Админы
Ранг: Старожил
Сообщений: 1953
Репутация: 723 ±
Замечаний: ±

Мои формульные попытки решения через вспомогательные вычисления
не находит ответ - максимальная длина цепочки, но позволяет вывести все цепочки заданной длины
К сообщению приложен файл: SovpVopr1.xlsx(38.6 Kb)
 
Ответить
СообщениеМои формульные попытки решения через вспомогательные вычисления
не находит ответ - максимальная длина цепочки, но позволяет вывести все цепочки заданной длины

Автор - MCH
Дата добавления - 13.10.2020 в 15:47
Светлый Дата: Среда, 14.10.2020, 00:38 | Сообщение № 14
Группа: Друзья
Ранг: Старожил
Сообщений: 1485
Репутация: 387 ±
Замечаний: 0% ±

Excel 2010, 2013
но позволяет вывести все цепочки заданной длины
Переделал свои формулы. Сейчас при протягивании выводит расположение всех цепочек, даже одинаковой длины:
Код
=НАИБОЛЬШИЙ(ЧАСТОТА(СТРОКА($1:$40001);ЕСЛИ(ЧАСТОТА((D$1:D$200=ТРАНСП(D$2:D$201))*(D$1:D$200>0)*(200*СТОЛБЕЦ(A:GR)-199*СТРОКА($1:$200));СТРОКА($1:$40000))=1;;СТРОКА($1:$40001)));СТРОКА(L1))-1
Код
=ОСТАТ(НАИМЕНЬШИЙ(ЕСЛИ(L2+1=ЧАСТОТА(СТРОКА($1:$40001);ЕСЛИ(ЧАСТОТА((D$1:D$200=ТРАНСП(D$2:D$201))*(D$1:D$200>0)*(200*СТОЛБЕЦ(A:GR)-199*СТРОКА($1:$200));СТРОКА($1:$40000))=1;;СТРОКА($1:$40001)));СТРОКА($1:$40001));СЧЁТЕСЛИ(L$2:L2;L2))-L2-1;200)
Код
=(НАИМЕНЬШИЙ(ЕСЛИ(L2+1=ЧАСТОТА(СТРОКА($1:$40001);ЕСЛИ(ЧАСТОТА((D$1:D$200=ТРАНСП(D$2:D$201))*(D$1:D$200>0)*(200*СТОЛБЕЦ(A:GR)-199*СТРОКА($1:$200));СТРОКА($1:$40000))=1;;СТРОКА($1:$40001)));СТРОКА($1:$40001));СЧЁТЕСЛИ(L$2:L2;L2))-L2-1+199*M2)/200+1

MCH, в сообщении 8 ошибка. Там должны быть решения 6-65-80 вместо 5-65-80, а 5-4-37 не найдено.
К сообщению приложен файл: SovpOtvMult.xlsx(25.7 Kb)


Программировать проще, чем писать стихи.
 
Ответить
Сообщение
но позволяет вывести все цепочки заданной длины
Переделал свои формулы. Сейчас при протягивании выводит расположение всех цепочек, даже одинаковой длины:
Код
=НАИБОЛЬШИЙ(ЧАСТОТА(СТРОКА($1:$40001);ЕСЛИ(ЧАСТОТА((D$1:D$200=ТРАНСП(D$2:D$201))*(D$1:D$200>0)*(200*СТОЛБЕЦ(A:GR)-199*СТРОКА($1:$200));СТРОКА($1:$40000))=1;;СТРОКА($1:$40001)));СТРОКА(L1))-1
Код
=ОСТАТ(НАИМЕНЬШИЙ(ЕСЛИ(L2+1=ЧАСТОТА(СТРОКА($1:$40001);ЕСЛИ(ЧАСТОТА((D$1:D$200=ТРАНСП(D$2:D$201))*(D$1:D$200>0)*(200*СТОЛБЕЦ(A:GR)-199*СТРОКА($1:$200));СТРОКА($1:$40000))=1;;СТРОКА($1:$40001)));СТРОКА($1:$40001));СЧЁТЕСЛИ(L$2:L2;L2))-L2-1;200)
Код
=(НАИМЕНЬШИЙ(ЕСЛИ(L2+1=ЧАСТОТА(СТРОКА($1:$40001);ЕСЛИ(ЧАСТОТА((D$1:D$200=ТРАНСП(D$2:D$201))*(D$1:D$200>0)*(200*СТОЛБЕЦ(A:GR)-199*СТРОКА($1:$200));СТРОКА($1:$40000))=1;;СТРОКА($1:$40001)));СТРОКА($1:$40001));СЧЁТЕСЛИ(L$2:L2;L2))-L2-1+199*M2)/200+1

MCH, в сообщении 8 ошибка. Там должны быть решения 6-65-80 вместо 5-65-80, а 5-4-37 не найдено.

Автор - Светлый
Дата добавления - 14.10.2020 в 00:38
MCH Дата: Среда, 14.10.2020, 08:21 | Сообщение № 15
Группа: Админы
Ранг: Старожил
Сообщений: 1953
Репутация: 723 ±
Замечаний: ±

Цитата Светлый, 14.10.2020 в 00:38, в сообщении № 14 ()
Там должны быть решения 6-65-80 вместо 5-65-80

наличие 6-65-80 не отменяет 5-65-80 (поэтому есть еще 5-66-81)
5-4-37 также 5-4-102 и 5-37-102 дают последовательность: 3 3 1 2 1


Я же написал, что не решил задачу формулами, а только немного приблизился к решению - получил перечень совпадающих цепочек заданной длины

И да, Ваше решение очень интересное и заслуживает детального изучения.
Думаю отсутствие других участников обусловлено сложностью задачи (для решения ее формулами)
 
Ответить
Сообщение
Цитата Светлый, 14.10.2020 в 00:38, в сообщении № 14 ()
Там должны быть решения 6-65-80 вместо 5-65-80

наличие 6-65-80 не отменяет 5-65-80 (поэтому есть еще 5-66-81)
5-4-37 также 5-4-102 и 5-37-102 дают последовательность: 3 3 1 2 1


Я же написал, что не решил задачу формулами, а только немного приблизился к решению - получил перечень совпадающих цепочек заданной длины

И да, Ваше решение очень интересное и заслуживает детального изучения.
Думаю отсутствие других участников обусловлено сложностью задачи (для решения ее формулами)

Автор - MCH
Дата добавления - 14.10.2020 в 08:21
Мир MS Excel » Работа и общение » Мозговой штурм » Самая длинная цепочка совпадений (В столбце формулами найти максимальную длину и два начала)
  • Страница 1 из 1
  • 1
Поиск:

Яндекс цитирования
© 2010-2020 · Дизайн: MichaelCH · Хостинг от uCoz · При использовании материалов сайта, ссылка на www.excelworld.ru обязательна!