Задача на комбинаторику

Автор IKor, 15.08.2012, 15:55

« назад - далее »

IKor

Коллеги,

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

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

Таким образом, мне нужно сгенерировать таблицу переменной ширины (зависит от количество слагаемых, указанных пользователем), каждая строка которой представляет собой один из вариантов сочетания порядковых номеров указанных векторов:
1-1-1-1
1-1-1-2
1-1-1-3
...
1-1-1-10
1-1-2-1
1-1-2-2
...
10-10-10-10
Количество значений в каждом векторе постоянное и известное (оно меняется в зависимости от задачи: 5...15).

В принципе, у меня есть представления как сгенерировать такую таблицу формулами, зависящими от значений смежных ячеек (фактически методом рекурсии). Но мне бы хотелось получить такую формулу, которая генерировала бы номера вектора в зависимости от двух параметров: номер строки и номер столбца. Т.к. следующим шагом будет генерация собственно значения из вектора по сгенерированным номерам, а сделать это желательно в той же самой таблице.

Есть и усложнение этой задачи:
Т.к. варианты 1-1-1-2, 1-1-2-1, 1-2-1-1 и 2-1-1-1 для получения суммы идентичны, то хочется сразу избавиться от трех из четырех вариантов.

Есть ли у кого-нибудь соображения на этот счёт?

ZORRO2005

IKor,
держи вариант до 9 столбцов.
Формула не моя, но разобраться можно.
Яндекс-деньги: 410011658492153

IKor

Спасибо,
буду разбираться.

Если у кого-нибудь есть еще варианты - приму с благодарностью.

P.S. Пока обнаружена странная вещь: при относительно большом количестве вариантов (больше 8 столбцов по 5 строк) Эксель надолго задумывается и выводит пустую таблицу. Еще более странно то, что формула не работает с частным случаем к=1 (один столбец).

MCH

Варианты на базе UDF

ZORRO2005

#4
Цитата: IKor от 15.08.2012, 18:39
P.S. Пока обнаружена странная вещь: при относительно большом количестве вариантов (больше 8 столбцов по 5 строк) Эксель надолго задумывается и выводит пустую таблицу.
Я видел СПОРТЛОТО "5 из 36", но не "36 из 5".  
Если есть 8 цифр, то комплекты могут быть не больше чем из 8 цифр.
k<=n
k=5, n=8
Цитировать
Еще более странно то, что формула не работает с частным случаем к=1 (один столбец).
Например k=1, n=5.
Какие комплекты и сколько по одной цифре можно сделать?
5 комплектов: 1,2,3,4,5. Выведите формулу для k=1 в отдельном столбце.

IKor, вы попросили решение формулой.
Я дал универсальное решение.
Т.к. не было четких границ, я растянул формулу на 30.000 ячеек, поэтому Excel и задумывается.
Яндекс-деньги: 410011658492153

IKor

2 ZORRO2005
Во-первых, большое спасибо за формулу.

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

Третье, правильно ли я понимаю, что количество строк, заполненных формулой (30 000 шт.), само по себе является важным параметром для работы функции - т.е. при недостаточном количестве строк некорректно отображаются результаты (пустые значения) в существующих строках? Для меня важно это понять и учитывать при составлении своей функции.

Кстати сказать, в моем случае n=5...15 (для разных таблиц) - известно заранее и прямо указывается пользователем перед началом работы. В то время как k=1...K (K - ограничено только производительностью системы) - величина "переменная", т.е. в процессе работы пользователь может менять количество рассматриваемых столбцов.

2 MCN
Тоже большое спасибо.

Возможно [снова] пришло мое время разобраться с макросами :)

В любом случае, два работающих примера позволяют лучше понять сам принцип, а это самое важное.

MCH

Цитата: IKor от 16.08.2012, 10:53
2 MCN
Правильно MCH (mch, Михаил Ч.)
Задачка очень интересная, самому хочется сделать формульное решение.
теоретически думаю, что смогу сделать решение на формулах, где формулы будут зависить от порядкового номера, не ссылаясь на значения предыдущих вычислений (по крайне мере алгоритм намечен):
1,2,3
1,2,4
...
1,2,10
1,3,4
1,3,5
...
8,9,10

по задаче IKor: 1,1,1; 1,1,2 ... ;1,1,10; 1,2,2 ...; 10,10,10 пока не получается формулами решить

ZORRO2005

Цитата: IKor от 16.08.2012, 10:53
2 ZORRO2005
Третье, правильно ли я понимаю, что количество строк, заполненных формулой (30 000 шт.), само по себе является важным параметром для работы функции - т.е. при недостаточном количестве строк некорректно отображаются результаты (пустые значения) в существующих строках? Для меня важно это понять и учитывать при составлении своей функции.
Выше файл  5_8.xlsx , где k=5;n=8 и кол-во вариантов считается по формуле =ФАКТР(n+k-1)/ФАКТР(n-1)/ФАКТР(k)
Получаем 792 варианта.
Это означает, что формулу надо растянуть на 5 ячеек в ширину и 792 в высоту.
30.000 было с запасом + еще условное_форматирование.
Яндекс-деньги: 410011658492153

Михаил С.

IKor
ЦитироватьТаким образом, мне нужно сгенерировать таблицу переменной ширины (зависит от количество слагаемых, указанных пользователем), каждая строка которой представляет собой один из вариантов сочетания порядковых номеров указанных векторов:
А макрос чем не устраивает? эта задача для макроса, формульное решение - только ради спортивного интереса, имхо конечно.
MCH
Цитироватьтеоретически думаю, что смогу сделать решение на формулах, где формулы будут зависить от порядкового номера
Не получится. Порядковый номер вычислить можно, формула не очень сложная, а вот комбинацию из порядкового номера простой арифметикой не вычислишь. Получается система уравнений, где неизвестных больше, чем уравнений. Я эту задачу пытался решить лет двадцать назад, когда спортлото увлекался.
...Впрочем дерзай, может я своё время что-то не учел...

ZORRO2005
ЦитироватьВыше файл  5_8.xlsx , где k=5;n=8 и кол-во вариантов считается по формуле =ФАКТР(n+k-1)/ФАКТР(n-1)/ФАКТР(k)
Мы же все таки в Excel работаем
=ЧИСЛКОМБ(k+n-1;k)
:D
Отдельное спасибо можно на QiWi-кошелек 909-771-53-87 или ЯД 41001136675053

MCH

Цитата: Михаил С. от 16.08.2012, 20:19
Порядковый номер вычислить можно, формула не очень сложная
Михаил, хотелось бы взглянуть на твою несложную формулу, у меня формула для определения порядкового номера из имеющахся чисел порядка 150 символов, построена на ЧИСЛКОМБ
Обратное преобразование хочу построить на алгоритме, таком же как использовал в UDF, там как раз из порядкового номера получаю нужные числа

Михаил С.

Миш, когда я делал эти формулы, у меня был Spektrum и не было Excel. Я не знаю, твоя формула универсальна или как, у меня для каждого варианта (пара-тройка-четверка-пятерка) была своя формула, арифметически несложная.
Если вариант IKor
1 1 1 1
........
........
10 10 10 10
привести к виду
1 2 3 4
........
.......
10 11 12 13

и если принять N=1 (первое число), К=13 (последнее число), a1<a2 (пара чисел), то порядковый номер любой пары
№=(2*K-N-a1)/2*(a1-N+1)*K+a2
первое и последнее число могут быть любыми, например, комбинация пар чисел от 20 до 100, тогда N=20, K=100

Аналогичные формулы у меня были для троек, четверок и пятерок (5 из 36), но тетрадка потерялась, а выводить по-новой мне не интересно. Да и для большого числа вариантов, более пятерок - для каждого варианта своя формула - не очень....

А вот обратный перевод формулой не получился, пришлось использовать циклы, правда короткие.
Отдельное спасибо можно на QiWi-кошелек 909-771-53-87 или ЯД 41001136675053

MCH

Мои расчеты, с помощью UDF и формулами

ZORRO2005

Для ЧИСЛКОМБ(n;k) есть решение, где формулы зависят от порядкового номера.
Яндекс-деньги: 410011658492153

Михаил С.

Цитата: IKor от 15.08.2012, 15:55... Таким образом, мне нужно сгенерировать таблицу переменной ширины (зависит от количество слагаемых, указанных пользователем), каждая строка которой представляет собой один из вариантов сочетания порядковых номеров указанных векторов:
......
Есть ли у кого-нибудь соображения на этот счёт?
Примерно так
Отдельное спасибо можно на QiWi-кошелек 909-771-53-87 или ЯД 41001136675053

MCH