Поиск  Пользователи  Правила  Войти
Форумы "Планета Excel" » Вопросы по Microsoft Excel (архив)
Страницы: 1 2 След.
RSS
посчитать число комбинаций
 
#1
18.02.2012 21:16:05
всем привет :)  
не знаю, то ли после пятницы плохо соображается мне, то ли плохое знание математики сказывается :)  
короче, выяснилось - мне нужна помощь в следующем вопросе:  
 
дано:    
N натуральных чисел, каждое - от 1 до M, каждое следующее должно быть больше предыдущего.  
например, для N=10 и M=90 получаем следующие варианты:  
1 2 3 4 5 6 7 8 9 10  
1 2 3 4 5 6 7 8 9 11  
...  
80 81 82 83 84 85 86 87 88 89    
80 81 82 83 84 85 86 87 88 90    
81 82 83 84 85 86 87 88 89 90  
 
требуется:  
1) определить общее количество комбинаций для заданных N и M  
2) если предположить, что формирование таких комбинаций идет в указанном выше порядке, то как определить кол-во комбинаций для заданных первых трех чисел, полученных к этому моменту, т.е.  
имеем 1 2 3 .... - столько-то, 7 8 24 - эстолько-то.  
 
первую задачку ручками для конкретных N=10 и M=90, я решил, но как-то по-дурацки - можно посмотреть приложенный файл, но там мало интересного :(  
у меня получилось 5.720.645.481.903 комбинации  
 
за вторую ума не приложу как взяться :(  
для 1 2 3 у меня вышло 5.843.355.957 вариантов,  
для 1 2 4 = 11.216.556.837...  
общую же идею никак не моху "ухватить".  
 
наверное, слишком много я прогуливал лекций по комбинаторике.  
плиз, хелп ми.
фрилансер Excel, VBA - контакты в профиле
"Совершенствоваться не обязательно. Выживание — дело добровольное." Э.Деминг
 
 
 
#2
18.02.2012 21:42:53
Это что, что-то типа, сколько вариантов в спортлото?
 
 
 
#3
18.02.2012 21:51:04
наверное, типа того.  
но вообще-то изначально имеется M разных прессформ и N литьевых машин.  
нужно перебрать все варианты использования разных прессформ (оснастки) на ограниченном парке оборудования.  
есс-но, кроме перебора и общего количества у меня каждый набор оценивается на "попадание", некоторые сразу отбраковываются, другие попадают в предварительную выборку, ну и так далее.  
 
я не вижу смысла ставить перед форумом задачу в полном объеме.  
имхо, это наглость :)  
 
но вот в этом моменте у меня загвоздка.  
и, кстати, еще в одном, но с тем я пока не оставляю надежд разобраться самому.
фрилансер Excel, VBA - контакты в профиле
"Совершенствоваться не обязательно. Выживание — дело добровольное." Э.Деминг
 
 
 
#4
18.02.2012 22:02:41
Число 5.720.645.481.903 получается одной формулой =ЧИСЛКОМБ(90;10)  
Если в 2003 такой функции нет, то есть формула посложнее  
=ФАКТР(90)/(ФАКТР(10)*ФАКТР(90-10))  
По второму вопросу пока не очень понял, что нужно, но там тоже просто
 
 
 
#5
18.02.2012 22:17:35
есть! есть такая функция в эксель 2003!  
Михаил, Вы оч. похожи на моего спасителя.  
спасибо.  
 
по второму вопросу. наверное, я плохо объяснил.  
 
имеем вложенные циклы:  
for i1=1 to 81  
for i2=i1+1 to 82  
for i3=i2+1 to 83  
...  
next i3  
next i2  
next i1  
 
внутри - еще матрешка из 7 циклов  
нужно перед оператором next i3 вывести (в статусбар) кол-во комбинаций, которые ТЕОРЕТИЧЕСКИ обработаны к этому времени.  
вариант прибавлять счетчик на единичку внутри цикла самого нижнего уровня не подходит, так как далеко не все комбинации "имеют продолжение".    
к примеру, при расчетах я могу определить, что комбинация 1 3 4 УЖЕ не походит, неважно, что там будет дальше.    
соответственно, я сразу перейду к варианту 1 3 5.  
но мне нужно общее кол-во теоретических вариантов для каждого этапа. под этапом я здесь подразумеваю комбинацию первых трех чисел.  
 
в принципе, мысль мою Вы уже направили... чуть попозже (после ужина) постараюсь додумать сам. но готовый вариант было бы тоже хорошо получить :)  
 
спасибо.
фрилансер Excel, VBA - контакты в профиле
"Совершенствоваться не обязательно. Выживание — дело добровольное." Э.Деминг
 
 
 
#6
18.02.2012 22:36:41
для 1,2,3 ...    
=ФАКТР(87)/ФАКТР(80)/ФАКТР(7)    
=ЧИСЛКОМБ(90-3;7)    
5 843 355 957  
 
для 1,2,4 ...  
=ФАКТР(86)/ФАКТР(79)/ФАКТР(7)    
=ЧИСЛКОМБ(90-4;7)  
5 373 200 880  
 
вроде както так
 
 
 
#7
18.02.2012 22:41:47
Ну, общее число возможных троек в этих 5.720.645.481.903 по той же формуле, только вместо десяти - три: =ЧИСЛКОМБ(90;3) = 117.480.  
Но все равно пока не врубаюсь, что нужно
 
 
 
#8
18.02.2012 22:46:12
7,8,24  
=ЧИСЛКОМБ(90-24;10-3)  
778 789 440  
 
специально проверил кодом:  
Sub ikki()  
Dim k, i1, i2, i3, i4, i5, i6, i7, i8, i9, i10, n  
n = 90  
For i1 = 7 To 7  
For i2 = i1 + 1 To 8  
 For i3 = i2 + 16 To 24  
  For i4 = i3 + 1 To n - 6  
   For i5 = i4 + 1 To n - 5  
    For i6 = i5 + 1 To n - 4  
     For i7 = i6 + 1 To n - 3  
      For i8 = i7 + 1 To n - 2  
       For i9 = i8 + 1 To n - 1  
        'For i10 = i9 + 1 To n  
           'k = k + 1  
           k = k + n - i9  
        'Next i10  
Next i9, i8, i7, i6, i5, i4, i3, i2, i1  
Debug.Print k  
End Sub  
 
результат совпал
 
 
 
#9
18.02.2012 22:46:46
Не, Миш, любая тройка в этих вариантах встречается 117.480 раз - все одинаково.
 
 
 
#10
18.02.2012 22:55:34
я исходил из постановки задачи:  
 
"2) если предположить, что формирование таких комбинаций идет в указанном выше порядке, то как определить кол-во комбинаций для заданных первых трех чисел, полученных к этому моменту, т.е.  
имеем 1 2 3 .... - столько-то, 7 8 24 - эстолько-то.  
...  
для 1 2 3 у меня вышло 5.843.355.957 вариантов..."  
 
т.е. первые три цифры из перебора известны, нужно подсчитать, сколько осталось комбинаций:  
1,2,3,4,5,6,7,8,9,10  
1,2,3,4,5,6,7,8,9,11  
...  
1,2,3,83,84,85,86,87,88,89  
1,2,3,83,84,85,86,87,88,90  
1,2,3,84,85,86,87,88,89,90  
 
я именно так понял задачу, если не правильно, пусть Александр разъяснит
 
 
 
#11
18.02.2012 23:04:16
МСН, нет, немного не то (это про пост, где приведен код)  
с формулой я разобрался (с помощью форума, в смысле :).  
учили ж в институте.  
но - забыл напрочь, ибо 15 лет нафиг не нужно было :(  
 
насчет же 7 8 24 нужно так:  
работают циклы  
for i1=1 to 81  
for i2=i1+1 to 82  
for i3=i2+1 to 83  
...  
next i3  
next i2  
next i1  
 
в какой-то момент, перед next i3, переменные циклов i1, i2, i3 равны соответственно 7, 8 и 24.  
нужно посчитать - а сколько комбинаций мы "обработали" к этому моменту? "обработали" в кавычках, потому что много пропускали, но все равно они должны войти в общее кол-во.  
 
думаю, проще всего завести переменную и после каждого прогона цикла по i3 подсчитывать, сколько комбинаций для данного сочетания i1, i2, i3 и прибавлять это значение к общему итогу.  
 
в общем, задача решена. всем спасибо.  
(а математику мне надо подучить, мдааа. глядишь, не было бы дурацких вопросов. :)
фрилансер Excel, VBA - контакты в профиле
"Совершенствоваться не обязательно. Выживание — дело добровольное." Э.Деминг
 
 
 
#12
18.02.2012 23:31:03
Саш, маленький пример, покажи на пальцах, что нужно...
 
 
 
#13
18.02.2012 23:35:14
может так?  
Sub ikki()  
Dim k, i1, i2, i3, n, m  
n = 90  
m = 10  
For i1 = 1 To 7  
For i2 = i1 + 1 To 8  
For i3 = i2 + 1 To 24  
k = k + Application.Fact(n - i3) / Application.Fact(n - i3 - m + 3) / Application.Fact(m - 3)  
Next i3, i2, i1  
Debug.Print k  
End Sub  
 
1,2,3 - 5 843 355 957    
1,2,4 - 11 216 556 837    
7,8,24 - 1 076 128 517 673
 
 
 
#14
18.02.2012 23:40:18
Михаилу С. возвращаю пример :)  
 
МСН, именно это я и имел в виду.  
наращиваем переменную после каждого цикла.  
вообще-то мне нужен процент от общего кол-ва - для оценки ожидаемого времени работы макроса.  
но, ес-но, это уже мелочи.
фрилансер Excel, VBA - контакты в профиле
"Совершенствоваться не обязательно. Выживание — дело добровольное." Э.Деминг
 
 
 
#15
18.02.2012 23:53:12
Теперь понял.    
В принципе, тоже легко решается формулой. И когда-то я эту задачу решал на бумаге (когда увлекался спротлото, а машина была спектрум), но дело было давно и записей не осталось.  
:)
 
 
 
#16
18.02.2012 23:53:32
Саш, ну тогда так:  
 
Sub ikki()  
Dim k, i1, i2, i3, n, m, kn  
n = 10  
m = 5  
kn = Application.Fact(n) / Application.Fact(n - m) / Application.Fact(m)  
For i1 = 1 To n - m + 1  
 For i2 = i1 + 1 To n - m + 2  
   For i3 = i2 + 1 To n - m + 3  
       k = k + Application.Fact(n - i3) / Application.Fact(n - i3 - m + 3) / Application.Fact(m - 3)  
       Debug.Print i1; i2; i3, k, Format(k / kn, "0.0%")  
Next i3, i2, i1  
End Sub
 
 
 
#17
19.02.2012 00:00:07
Михаил С., да я понимаю, ьчто я был несколько косноязычен. хорошо, что форумчане у нас трпеливые :)  
 
МСН, огромное спасибо!!!  
 
пс. я, конечно, порой притормаживаю, но уж не надо за меня каждую строчку разжевывать :)))))))))))))  
 
ппс. но все равно спасибо.
фрилансер Excel, VBA - контакты в профиле
"Совершенствоваться не обязательно. Выживание — дело добровольное." Э.Деминг
 
 
 
#18
19.02.2012 00:00:32
...  
kn = Application.Combin(n, m)  
...  
k = k + Application.Combin(n - i3, m - 3)  
...
 
 
 
#19
19.02.2012 00:09:39
{quote}{login=Михаил С.}{date=18.02.2012 11:53}{thema=}{post}В принципе, тоже легко решается формулой.{/post}{/quote}Счас вспомнил - нет, конкретно эта задача формулами не решается (во всяком случае "легко"). Там получатся одно уравнение с тремя неизвестными. Я тоже решал эту задачу с помощью циклов.
 
 
 
#20
19.02.2012 20:44:54
Александр, для подсчета числа комбинаций можно использовать функцию:  
Function MyCombin#(ByVal n&, ByVal m&)  
Dim i&  
MyCombin = n  
For i = 2 To m  
   n = n - 1  
   MyCombin = MyCombin * n / i  
Next i  
End Function  
 
Она раза в 4-5 быстрее чем WorksheetFunction.Combin (для n=90 m=10) и раз в 8-10 чем Application.Combin  
думаю, что для большого пересчета данных это существенно
 
 
 
#21
19.02.2012 21:12:05
Даже лучше так (отсекаем лишние вычисления):  
Function MyCombin#(ByVal n&, ByVal m&)  
Dim i&  
MyCombin = n  
If m > n - m Then m = n - m  
For i = 2 To m  
   n = n - 1  
   MyCombin = MyCombin * n / i  
Next i  
End Function
 
 
 
#22
19.02.2012 21:18:58
МСН, вот хотел я понять эту функцию без копирования в VBE, и не понял :(  
 
это рекурсивная функция? судя по наличию MyCombin после знака "=" ?  
тогда почему без параметров?  
 
все-таки придется копировать... иначе не понять. :)  
 
спасибо.
фрилансер Excel, VBA - контакты в профиле
"Совершенствоваться не обязательно. Выживание — дело добровольное." Э.Деминг
 
 
 
#23
19.02.2012 21:30:30
рекурсии нет, просто MyCombin вычисляется не сразу, а постепенно в цикле  
Еще вариант, с проверкой на входные параметры:  
 
Function MyCombin#(ByVal n&, ByVal m&)  
Dim i&  
If m > n Or m < 1 Or n < 1 Then Exit Function  
If m > n - m Then m = n - m  
MyCombin = 1  
For i = 1 To m  
   MyCombin = MyCombin * n / i  
   n = n - 1  
Next i  
End Function
 
 
 
#24
19.02.2012 21:45:09
{quote}{login=MCH}{date=19.02.2012 08:44}{thema=}{post}... раз в 8-10 чем Application.Combin  
думаю, что для большого пересчета данных это существенно{/post}{/quote}  
 
у меня вот такой код:  
 
Sub test()  
 Const j = 2  
 Dim i1%, i2%, i3%, n&, m&, ws As Worksheet  
   
 Set ws = ThisWorkbook.Sheets(1)  
 n = 90: m = 10: t = Timer  
 For i1 = 1 To n - m + 1  
 For i2 = i1 + 1 To n - m + 2  
 For i3 = i2 + 1 To n - m + 3  
'    k = k + Application.Combin(n - i3, m - 3)  
   k = k + MyCombin(n - i3, m - 3)  
 Next i3, i2, i1  
 ws.Cells(j, 1) = Timer - t: ws.Cells(j, 2) = k  
End Sub  
 
(соответственно меняю закомментированную строку и константу j) даёт разницу в 26-30 раз.  
ещё как существенно!!!  
правда, в абсолютном выражении это примерно 1,03 сек.  
а всё остальное работает несколько часов :(
фрилансер Excel, VBA - контакты в профиле
"Совершенствоваться не обязательно. Выживание — дело добровольное." Э.Деминг
 
 
 
#25
19.02.2012 21:58:33
перечитал свой предыдущий пост, понял, что его можно воспринять как иронию.  
МСН, это не так ни в коем случае!!!  
это лишнее подтверждение избитой истины, что пределов совершенству нет.  
будем думать над "несколько часов" для всего остального.  
есть, есть там резервы :)
фрилансер Excel, VBA - контакты в профиле
"Совершенствоваться не обязательно. Выживание — дело добровольное." Э.Деминг
 
 
 
#26
20.02.2012 00:26:33
Почитал все посты, и опять потерял понятие...    
Вот есть три цифры - 2; 35; 68, что нужно?  
Первая позиция этих чисел из десятка, и и сколько их до первой позиции 2; 35; 69,  
или когда первый  и последний раз встречается эта тройка...
 
 
 
#27
20.02.2012 00:40:59
Михаил, мне нужно было буквально то, что сделал МСН в посте от 18.02.2012, 23:53  
просто сейчас он предложил более быстрый вариант.
фрилансер Excel, VBA - контакты в профиле
"Совершенствоваться не обязательно. Выживание — дело добровольное." Э.Деминг
 
 
 
#28
20.02.2012 01:29:29
Ладно, возможно завтра я обдумаю.... чет мне кажется, что можно проще... одной формулой... просто сейчас с Кареном (К61) четыре часа общались...,и я не в состоянии задачи решать....  
Короче, если задача именно как в посте post_309946.xls , то она решается формулой, правда длинной...
 
 
 
#29
20.02.2012 07:55:17
Леонов - Обо мне трёп был?  
Басилашвили - Был. Сказали что ты портвейн с водкой мешаешь  
Леонов – А им какое дело!?  
:)
 
 
 
#30
20.02.2012 09:19:41
На базе данной задачи родилось еще пара функций:  
определяющая по порядковому номеру значения чисел в счетчике и обратное преобразование из значений счетчика в порядковый номер  
 
PS: Может Михаил С. предложит какую нибудь математическую формулу, у меня не получилось решить формульно, только с помощью циклов
 
 
 
Страницы: 1 2 След.
Читают тему
Наверх