Поиск  Пользователи  Правила  Войти
Форумы "Планета Excel" » Вопросы по Microsoft Excel
Страницы: 1 2 След.
RSS
Как найти минимальное количество общих цифр в массиве данных, Как найти минимальное количество общих цифр в массиве данных
 
#1
27.04.2019 16:50:07

Добрый день. Есть массив данных. Как в нем найти минимальное количество цифр, с условием что хотя бы одна из них будет в каждой строке. Для примера в представленном массиве это будут: 1, 8 и 10 но возможно ли их как-то найти автоматически посредством формул или макроса? Спасибо.
 
 
 
#2
27.04.2019 20:02:18
Цитата
хотя бы одна из них будет в каждой строке
уточните условия, в вашем примере число 10 в 6 строках (максимум)
 
 
 
#3
27.04.2019 22:49:48
хотя бы одна из нескольких (желательно минимально возможного набора) цифр то есть не конкретно одной в данном случае это набор 1, 8 и 10. Условно для данного массива выполняется условия что в нем будет цифра 1 или 8 или 10. Но как автоматически найти такой "комплект цифр" не могу сообразить.  
 
 
 
#4
27.04.2019 23:00:51
mayer4,  боюсь, вас даже медведь не поймёт, а уж на что крутой спец по распознаванию.
Опишите шаг шаг шагом, как задаётся тот самый набор цифр? Почему именно этот? Почему в примере число 10 встречается 6 раз, что больше чем встречается число два (2 раза). Тогда почему 6 < 2? Или вы используете некоторое своё собственное определение меньше/больше? Переведите...
 
 
 
#5
27.04.2019 23:03:05
Цитата
mayer4 написал:
с условием что хотя бы одна из них будет в каждой строке.
В каждой? У Вас в примере ни 1, ни 8, ни 10 не удовлетворяют этому условию. Переформулируйте условие.
 
 
 
#6
28.04.2019 00:04:41

Если рассмотреть первый ряд «Цикл1» то в нем из комбинации цифр "1, 8, 10" присутствует цифра «10». Второй ряд «Цикл2» есть 1 и 10 и так далее. Если взять например комбинацию "1, 2, 10" то получается что в ряде «Цикл7» нет не одной из этих цифр то есть нет ни 1 не 2 не 10. Нужно найти такой набор цифр хотя бы одна из которых встречается во всех рядах.

 
 
 
#7
28.04.2019 00:07:54
Цитата
Андрей VG написал:
Опишите шаг шаг шагом, как задаётся тот самый набор цифр? Почему именно этот?
Мне как раз и нужно найти этот набор цифр, здесь я его указал для примера.
 
 
 
#8
28.04.2019 00:56:57
Вариант, как понял.
 
 
 
#9
28.04.2019 08:49:43
Включил BeearRecogniserSystem . После прочтения пояснений, фраза
Цитата
mayer4 написал:
Как в нем найти минимальное количество цифр, с условием что хотя бы одна из них будет в каждой строке.
приобрела окраску и стало понятно чего хочется, однако теперь меня интересует , каков ответ ожидается, ибо количество для примеров будет число 3 например.

Если кто не понял условия, то  ищется минимальная по количеству комбинация чисел от 1 до 10,которая удовлетворяет условию, что во всех строках должно присутствовать, хотя бы одно  число из этой комбинации.

Думаю формулы бессильны, так как нужно включить комбинаторику, и

, При этом K меняется от 1 до 10 что получим в районе 1000 комбинаций, что не так страшно, и если б не сложность генерации этого формулой, то не проблема, а так нужен макрос.
Проверить на наличие в строке одного числа или комбинации и далее проверить что б по всем строкам было хоть одно вхождение - не проблема.
Изменено: БМВ - 28.04.2019 09:01:47
По вопросам из тем форума, личку не читаю.
 
 
 
#10
28.04.2019 09:52:15
Цитата
БМВ написал:
найти минимальное количество цифр, с условием что хотя бы одна из них будет в каждой строке.
Привет, Михаил.
Возьмём первый файл ТС. Какое число от 1 до 10 есть в каждой строке? 10 есть только Цикл 1-Цикл 5, Цикл 10. Аналогично и с остальными. Тогда условие
Цитата
хотя бы одна из них будет в каждой строке
не выполняется.
Второе. Пусть 10 есть в каждой строке Цикл 1- Цикл 10, тогда все числа, которые попадаются в любой из строк удовлетворяют условию и для первого файла имеем минимальный набор из 1-9.
Почему тогда у ТС только 1, 8, 10?
Цитата
БМВ написал:
хотя бы одно  число из этой комбинации.
Эта комбинация чем/кем задана и где?
Изменено: Андрей VG - 28.04.2019 09:53:33
 
 
 
#11
28.04.2019 11:10:07
Я вот до сих пор не могу понять задачу ))
 
 
 
#12
28.04.2019 11:24:23
Андрей, в каждой строке есть одно из трех, например так  10,1,10,10,10,1,8,1,1,10 по строкам. От сюда список уникальных 1,8,10.  
проверка простая,
=SUM(--(MMULT(($B$3:$K$12=B13:K13)*(B13:K13<>0);ROW(A1:A10)^0)>0))=10
А вот подбор значений, или макросом, а возможно Solver поможет.                                                            
По вопросам из тем форума, личку не читаю.
 
 
 
#13
28.04.2019 13:25:31
Михаил, спасибо за перевод на человеческий язык.
Цитата
БМВ написал:
или макросом
Макросом, так макросом. Отображаемый набор по примеру 10; 1; 4.
P. S. Крайне не рекомендуется запускать на сильно заполненной таблице. Алгоритм строит все пути, на сильно заполненном будет 10^10 вариантов путей. Можно несколько оптимизировать, на каждом шаге отбирая пути по минимальному количеству узлов предыдущего шага. Оставлю это ТС - ему тоже надо чем то в своей задаче поделать, а то будет скучно. :)
Изменено: Андрей VG - 28.04.2019 13:33:37
 
 
 
#14
28.04.2019 14:12:56
Андрей VG, а от куда 10^10 ? . 2^10 должно быть  фактически 10 бит, каждым кодируется то или иное значение от 1 до 10.
Изменено: БМВ - 28.04.2019 14:28:57
По вопросам из тем форума, личку не читаю.
 
 
 
#15
28.04.2019 14:34:07
Цитата
БМВ написал:
а от куда 10^10
Михаил, это исходя из алгоритма. Алгоритм строит путь из каждого числового узла строки во все числовые узлы другой строки (числа большие 0).
Соответственно, пусть в первой строке 10 чисел и во второй 10 чисел. Тогда для каждого числа из первой строки есть 10 путей во вторую строку. Всего 10^2, где 2 число строк. Отсюда в пределе для 10 строк 10^10.
А уж отбираем в пути с 1 по 10 строку только уникальные числа. То есть если дважды/трижды и так далее в пути от первой строки к десятой встретилась 1, то учитываем её один раз. Таким образом в пути останутся только уникальные числа. Построив все пути, отберём такой, у которого наименьшее количество чисел и выведем его.
Изменено: Андрей VG - 28.04.2019 14:34:47
 
 
 
#16
28.04.2019 15:16:58
Понятно, я б конечно пошел по тому пути что пошел.
К слову, если о количестве говорить, то можно и формулами попробовать, Но пока ТС не сказал, что нужно получить 3 или комбинацию ( а их в примере 2), делать не хочется.
Изменено: БМВ - 28.04.2019 15:30:24
По вопросам из тем форума, личку не читаю.
 
 
 
#17
28.04.2019 15:47:22
Здравствуйте, коллеги! #16 - впечатляющий пример возможностей формул.
Задачу можно сформулировать так. Есть матрица (не обязательно квадратная) из нулей и единиц, причем в каждой строке и каждом столбце есть хотя бы одна единица. Выделить минимальное множество столбцов так, чтобы для каждой строки нашелся выделенный столбец, на пересечении с которым стоит единица. Что-то знакомое из линейного программирования...
Можно решать рекурсивно перебором, начиная со строк с минимальным числом единиц. Варианты хуже ранее найденного можно сразу отбрасывать.
Изменено: sokol92 - 28.04.2019 15:47:38
Владимир
 
 
 
#18
28.04.2019 16:50:17
Михаил, спасибо. Отличное решение. Только вот фантомные истины присутствуют.
 
 
 
#19
28.04.2019 17:03:33
sokol92, Владимир, нет предела
=SMALL(IF(MMULT(TRANSPOSE(--(BITAND(MMULT(($B$3:$K$12>0)*2^(10-COLUMN($B$2:$K$2)+1);ROW($A$1:$A$10)^0);TRANSPOSE(ROW($A$1:$A$1024)))>0));ROW($A$1:$A$10)^0)=10;ROW($A$1:$A$1024));ROW(A1))
Находит десятичные числа, которые удовлетворяют, осталось только найти единички и минимальное их количество. В процессе :-)
По вопросам из тем форума, личку не читаю.
 
 
 
#20
28.04.2019 22:58:51
Здравствуйте. Спасибо всем огромное за помощь в решении моей проблемы!!!! Извините если не смог совсем корректно сформулировать требуемую задачу. Андрей VG Ваш макрос работает идеально но возможно ли его оптимизировать если увеличится количество данных до 20 и более строк и столбцов? Просто ответить на вопрос "Можно несколько оптимизировать, на каждом шаге отбирая пути по минимальному количеству узлов предыдущего шага. Оставлю это ТС - ему тоже надо чем то в своей задаче поделать, а то будет скучно. "для сеня с моими познаниями в программировании нереально. Также Спасибо БМВ за ваше решение но его также возможно изменить для поиска значений например в таблице 20х20? Еще хочу всех поздравить с пращником пасхи - Христос Воскрес!!!
 
 
 
#21
29.04.2019 00:23:12

Чисто Формульное решение для 10x10.  Для краткости в имена пришлось кое что спрятать, ну и без промежуточного решения не получилось

Цитата
mayer4 написал:
его также возможно изменить для поиска значений например в таблице 20х20?
Вы не ответили на вопрос, вам нужна комбинация или именно количество ваших цифирок? , хотя для 20x20 надо перебрать 2^20 вариантов, а это 1048576 - максимальное количество строк на листе. С учетом использования некоторых, не простых для расчетов функций, на этом объеме расчет может оказаться весьма задумчивым, если досчитает вовсе.

По вопросам из тем форума, личку не читаю.
 
 
 
#22
29.04.2019 00:27:55
Нужна именно минимально возможная комбинация при этом количество цифр в ней может быть любой не обязательно три.
Изменено: mayer4 - 29.04.2019 00:30:33
 
 
 
#23
29.04.2019 01:06:43
ну тогда, я б использовал свой алгоритм перебора 2^N значений, где N - количество Ваших столбцов, но конечно макросом. Может посмотрю потом.
По вопросам из тем форума, личку не читаю.
 
 
 
#24
29.04.2019 01:08:41
Спасибо!!!
 
 
 
#25
29.04.2019 09:38:02
"Темная сторона силы" помогла с UDF.
1. для 10x10 считает почти мгновенно, а вот 20x20  задумывается
2. для примера 10x10 выдает 1,4,10, а не 1,8,10, что не ошибка, просто это второй набор.

Цитата
Андрей VG написал:
Только вот фантомные истины присутствуют.
Андрей, ну так задача была минимальный набор, под нее и делал.
Сравнил варианты, ну что могу сказать, с учетом того что я не макрушник, результат по скорости меня радует и сильно.
По вопросам из тем форума, личку не читаю.
 
 
 
#26
29.04.2019 10:17:35
Цитата
БМВ написал:
вот 20x20  задумывается
Есть места, где стоило бы отполировать. :)  Будет быстрее.
Чуть подполировал свой вариант на графах. Ему без разницы, квадратная ли матрица на входе или нет. Главное чтобы выделение было прямоугольным.
 
 
 
#27
29.04.2019 10:26:05
Цитата
Андрей VG написал:
Есть места, где стоило бы отполировать.
Андрей, готов выслушать. Хотя один цикл уже убрал, маленький , но совершенно не нужный, был как архаизм,
о, убрал еже обработку заведомо ненужных вариантов, время получил равное тому что у Вас в последней версии.
Изменено: БМВ - 29.04.2019 11:18:13
По вопросам из тем форума, личку не читаю.
 
 
 
#28
29.04.2019 11:20:02
Цитата
БМВ написал:
готов выслушать
Например, количество бит в двоичном представлении числа считал бы так.
Код
Function CountBits2(ByVal lngDec As Long) As Long
    Dim bitCount As Long
    bitCount = 0
    Do Until lngDec = 0
        bitCount = bitCount + lngDec Mod 2
        lngDec = lngDec \ 2
    Loop
    CountBits2 = bitCount
End Function

Выигрыш на на цикле 2 ^ 20 - 0,36 секунды против 2,30 секунды.
Перевёл бы все 2 ^ (j - 1) в однократно вычисленные массивы констант. Операция возведения в степень одна из самых дорогих. Хуже только тригонометрия.
 
 
 
#29
29.04.2019 11:26:14
Андрей VG и БМВ спасибо Вам огромное, это то что мне было нужно. А возможно ли добавить что-то на подобии статус-бара или индикатора который будет показывать сколько времени осталось до завершения выполнения расчетов? Но в любом случае спасибо за ваше участие!!!
 
 
 
#30
29.04.2019 11:31:09
Андрей VG,  Спасибо, сейчас 20x20 считает на моем компе  примерно 1 сек. ранее было почти 5 ,  а до этого было совсем грустно.
Возведение в степень свел к минимуму, там и до этого было не много, разово массив заполнялся, и финальная комбинация бралась, - это гроши но всеж.
Изменено: БМВ - 29.04.2019 11:43:21
По вопросам из тем форума, личку не читаю.
 
 
 
Страницы: 1 2 След.
Наверх