Поиск  Пользователи  Правила  Войти
Форумы "Планета Excel" » Вопросы по Microsoft Excel
Страницы: 1
RSS
Неповторяющиеся комбинации значения переменных
 
#1
14.11.2017 14:04:19
Добрый день!
Помогите пожалуйста.
есть формула a+b+c+d=m
нужно найти m для значений a,b,c,d от 1 до 100.значения в уравнении должны быть унимальными, не повторяться. Решил методом перебора попробовать.
часть кода:
Код
for a=1 to 100
 for b=1 to 100
  for c= 1 to 100
   for d=1 to 100

m=a+b+c+d

Next d
Next c
Next b
Next a

Как не считать m если две переменные будут равны( например 1 2 3 3) я понимаю.
Но я не понимаю как избежать повторения значений типа : 1 2 3 4 и 1 2 4 3, и 1 3 2 4 и.т.д.
Тоесть надо один раз посчитать такую комбинацию и далее пропускать.

помогите пожалуйста
 
 
 
#2
14.11.2017 14:14:59
Вариант 1, простой
делаем 4 вложенных цикла, как вы показали, до вычислений делаем проверки на уникальность значений a, b, c, d
Вариантов для перебора: 100*100*100*100 = 100 млн комбинаций
либо так, если a<b<c<d:
Код
for a=1 to 97
 for b=a+1 to 98 
  for c= b+1 to 99 
   for d=c+1 to 100 
...



Вариант 2, делаем генерацию сочетаний 4 чисел из 100, если нужно то с перестановками или без перестановок
Кол-во вариантов без перестановок: 100!/96!/4! = 3921225 вариантов
с перестановками: 100!/96! = 94109400 вариантов
 
 
 
#3
14.11.2017 14:25:12
я так понимаю всё равно будут миллион комбинаций начиная с 5 6 7 8, 5 6 8 7, 5 7 6 8 и тд и до 90 91 92  93, 90 91 93 92, 90 92 91 93
как раз и хочу исключить повторяющиеся вычисления и результаты.
 
 
 
#4
14.11.2017 14:28:05
Не получится ли в цикле проверить переменные на то, было ли сочитание до этого?)
 
 
 
#5
14.11.2017 14:29:19
Всё равно не выиграете... Иначе их бы не существовало :)
 
 
 
#6
14.11.2017 14:33:35
если комбинации 1 2 3 4 идентична 4 3 2 1, при этом не должно быть повторяющихся данных, типа 1 1 1 1 или 99 99 99 99, то всего возможно 3921225 вариантов различных сочетаний, сгенерировать из можно 4мя циклами, как показано в сообщении #2
перебрать 4 млн комбинаций не долго, но если задача будет более сложной, то нужно решать ее иначе.

Какова итоговая задача, обязательно нужно решать перебором?
 
 
 
#7
14.11.2017 14:46:13
Цитата
Hugo написал: Всё равно не выиграете... Иначе их бы не существовало
тссссс)))))))

Цитата
MCH написал: Какова итоговая задача, обязательно нужно решать перебором?
Перебором. В подобных задачах производится в 16 раз лишних подсчётов (4*4=16), и соответственно в 16 раз раздувается массив с результатами. А если 5 или 6 параметров(((
Изменено: ArtemSkudalov - 16.11.2017 14:00:41
 
 
 
#8
14.11.2017 14:52:42
Офф. Вас вежливости не научили? В своих ранних темах отписываться желательно.
Согласие есть продукт при полном непротивлении сторон
 
 
 
#9
14.11.2017 15:06:32
Простите если обидел. Спасибо за помощь!  Голова кругом. Думал в личном кабинете найду свои темы, а там они не отображаются, я уж думал потерял их.
 
 
 
#10
14.11.2017 15:08:01
Цитата
ArtemSkudalov написал: если обидел
Дело не в 'обидел', просто нам не меньше Вашего интересно подошло/не подошло решение  ;)  
Согласие есть продукт при полном непротивлении сторон
 
 
 
#11
14.11.2017 15:09:07
А над данной проблемой думал думал и надумал. При каждой итерации сохранять переменные в виде текста в одномерный массив. И при следующей итерации проверять нет ли в массиве текущих параметров.
 
 
 
#12
14.11.2017 15:52:17
Цитата
ArtemSkudalov написал:
сохранять переменные в виде текста в одномерный массив. И при следующей итерации проверять нет ли в массиве текущих параметров
А почему не словарём? Быстрее же будет.
Изменено: Андрей VG - 14.11.2017 15:52:30
 
 
 
#13
14.11.2017 16:03:51
Сочетания можно построить такими циклами
Код
Public Sub test()
    Dim a As Long, b As Long, c As Long, d As Long
    Dim m As Long, pDict As Object
    Set pDict = CreateObject("Scripting.Dictionary")
    For a = 1 To 97
        For b = a + 1 To 98
            For c = b + 1 To 99
                For d = c + 1 To 100
                    m = a + b + c + d
                    pDict(m) = Empty
                Next
            Next
        Next
    Next
    Debug.Print pDict.Count
End Sub

Хотя может и ошибаюсь. Уникальных сумм получилось всего 385
 
 
 
#14
14.11.2017 19:36:50
Цитата
Андрей VG написал:
Хотя может и ошибаюсь. Уникальных сумм получилось всего 385
Спасибо! Но не совсем то. Нужно, чтоб не результаты были уникальны, нужно, чтоб набор переменных был уникален. 1+2+9+8 =20 и 3+4+6+7=20.  Мне мешает, то что при прогоне циклов всплывает
10+11+12+13=46
10+11+13+12=46
10+12+11+13
10+12+13+11
10+13+11+12
10+13+12+11
11+10+12+13
11+10+13+12
11+12+10+13
11+12+13+10
11+13+12+10
и т.д.
Всего 16 . От перестановки мест слагаемых сумма не меняется. Но перебирая циклом вместо одного подсчёта, делается 16. И массив с результатами переполнен.
 
 
 
#15
14.11.2017 19:37:56
Цитата
Андрей VG написал:
А почему не словарём? Быстрее же будет.
Можете по-подробнее рассказать?:)
 
 
 
#16
14.11.2017 20:10:11
Цитата
ArtemSkudalov написал:
Можете по-подробнее рассказать
Лекго
 
 
 
#17
14.11.2017 22:28:54
Цитата
ArtemSkudalov написал:
Мне мешает, то что при прогоне циклов всплывает
Если Вы организует циклы как указано в сообщении 2 и сообщении 14, то никаких повторов не будет

PS: Да и количество перестановки из 4х чисел не 16, а 24
 
 
 
#18
15.11.2017 23:15:55
На базе файла из другой темы ТС, сделал выборку наиболее чаще встречающихся сочетаний из четырех чисел:
Скрытый текст

Минимальное число - 1, максимальное число - 90, таким образом число вариантов выборки 4 чисел из 90: 90!/86!/4! = 2 555 190
Умножив данное число на 1008 строк получим 2 575 631 520 проверок.
У меня компьютер считал 1,5 - 2 минуты
Если взять выборку из 5 чисел, то времени будет затрачено в 17 раз больше (т.е. не менее получаса)
выборка из 6 чисел - часов 10 и более
Для ускорения можно все расчеты производить на C++ или другом быстром компилируемом языке, заодно задействовать потоки, ускорить расчеты можно в разы и даже в десятки раз.

Хотелось бы понять, для чего все это нужно (надеюсь не лотерея)
Изменено: MCH - 16.11.2017 11:55:16 (Немного подправил код программы)
 
 
 
#19
16.11.2017 08:59:51
Всем спасибо! Как Менделееву почти во сне приснилось.
Все решается условием a<b<c<d....
Изменено: ArtemSkudalov - 16.11.2017 09:01:19
 
 
 
#20
16.11.2017 09:09:27
Цитата
ArtemSkudalov написал:
Все решается условием a<b<c<d....
Хе, хе, вам дважды пример этого приводили :)
 
 
 
#21
16.11.2017 13:21:20
И вправду. Вот балда, не  понял что каждый раз начало цикла меняется. А показалось, что только один раз меняется. Всем спасибо!  
 
 
 
#22
16.11.2017 13:54:26
ArtemSkudalov, код из 19го сообщения не решает Вашу задачу?
 
 
 
Страницы: 1
Читают тему
Наверх