powered by simpleCommunicator - 2.0.59     © 2026 Programmizd 02
Целевая тема:
Создать новую тему:
Автор:
Закрыть
Цитировать
Форумы / Программирование [игнор отключен] [закрыт для гостей] / Как решить задачу по комбинаторике?
25 сообщений из 450, страница 6 из 18
Как решить задачу по комбинаторике?
    #39765331
Dima T
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
maytonТы уже опубликовал это где-то в гитхабе? Я хотел сделать несколько changes.
Залил. Экспериментируй
...
Рейтинг: 0 / 0
Как решить задачу по комбинаторике?
    #39765337
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Gennadiy UsovА если совсем углубиться (ударение на втором у), то можно ещё ввести соотношения между объектами (окружность, диагональ).

А если и ...., то можно вообще рисовать произвольные картинки, только успевай выстраивать новые схемы, которые будут похожи на 21794700

Так что, вариантов обобщения и углубления много.
Я именно про это и говорю. Есть граф. У него есть подграфы. Есть вершины с весами.
Часть вершин - предопределены. Часть - неизвестны. Подграфы связаны констрейнтами.
Например - где-то масса подграфа должна быть константой. (К началу задачи еще и эта
константа - неизвестна). Имеется также порождающий генератор (или набор генераторов)
которые выдают на выходе поток чисел которыми надо заполнять вершины.
Имеется цель - заполнить все вершины значениями из генератора при условии
выполнения всех кострейнтов.

И я имел в виду именно такую постановку.

Дано: G - множество графов. V - множество вершин. E - множество ребер.
Vс - подмножество вершин с весами. A - порождающий алгоритм(ы) заполнения
вершин. С - множество констрейнтов (ограничений) на множество графов.


И на меньшее я в топике не соглашусь.
...
Рейтинг: 0 / 0
Как решить задачу по комбинаторике?
    #39765341
Gennadiy Usov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Гость
Можно ещё один цикл убирать. Получаем:

Шаг 1. цикл по х15 - определяем а1

Шаг 2. циклs по х12 и х16
Здесь определяем в следующей последовательности: х14 (х14 + х16 = 20 или 19)( 21793947 ),
х13, а2, а3, х8, х9, х10, х11.

Далее
- есть две внутренние окружности, где можно проверить соотношение: х12, х13, а2, а3, х8, х9, х10, х11.
- есть средняя окружность, где можно проверить соотношение х8, х9, х10, х11

Шаг 3. Цикл по х2 в а1 - определяем х5

Шаг 4. Цикл по х3 в а2 – определяем х6

Шаг 5. Цикл по х4 в а3 – определяем х7

Всего 6 циклов.
3 основных и 3 вспомогательных (попарные перестановки 6 чисел)
...
Рейтинг: 0 / 0
Как решить задачу по комбинаторике?
    #39765342
Gennadiy Usov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Гость
maytonGennadiy UsovА если совсем углубиться (ударение на втором у), то можно ещё ввести соотношения между объектами (окружность, диагональ).
А если и ...., то можно вообще рисовать произвольные картинки, только успевай выстраивать новые схемы, которые будут похожи на 21794700 Так что, вариантов обобщения и углубления много.
Я именно про это и говорю. Есть граф. У него есть подграфы. Есть вершины с весами.
Часть вершин - предопределены. Часть - неизвестны. Подграфы связаны констрейнтами.
Например - где-то масса подграфа должна быть константой. (К началу задачи еще и эта
константа - неизвестна). Имеется также порождающий генератор (или набор генераторов)
которые выдают на выходе поток чисел которыми надо заполнять вершины.
Имеется цель - заполнить все вершины значениями из генератора при условии
выполнения всех кострейнтов.

И я имел в виду именно такую постановку.

Дано: G - множество графов. V - множество вершин. E - множество ребер.
Vс - подмножество вершин с весами. A - порождающий алгоритм(ы) заполнения
вершин. С - множество констрейнтов (ограничений) на множество графов.


И на меньшее я в топике не соглашусь.И что этому мешает?

Надо с чего-то начать...
...
Рейтинг: 0 / 0
Как решить задачу по комбинаторике?
    #39765346
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
С языка описания. Описать граф. Потом по этому описанию сгенерировать алгоритм.
...
Рейтинг: 0 / 0
Как решить задачу по комбинаторике?
    #39765347
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
alex55555maytonДоказательством корректнсти программы является ее работа и ее результат.
Но программисты же получают не просто результат, а оптимальный результат. Так вот по оптимальности решения полным перебором возможны большие вопросы.
А где вы увидели полный перебор?
...
Рейтинг: 0 / 0
Как решить задачу по комбинаторике?
    #39765348
Gennadiy Usov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Гость
maytonС языка описания. Описать граф. Потом по этому описанию сгенерировать алгоритм.Для этого нужен новый топик или достаточно существующего?
Будем использовать опыт этого топика?

Жду начала описания.

Далее - развитие этого описания.

Или сначала для тренировки обобщим имеющуюся задачку? 21794705
...
Рейтинг: 0 / 0
Как решить задачу по комбинаторике?
    #39765350
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Вам очень надо новый топик?
...
Рейтинг: 0 / 0
Как решить задачу по комбинаторике?
    #39765351
Gennadiy Usov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Гость
maytonВам очень надо новый топик?Можно и в существующем.

Я имею в виду название топика, если оно соответствует новой проблеме.
...
Рейтинг: 0 / 0
Как решить задачу по комбинаторике?
    #39765353
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Да нет никакой проблемы. Есть "игры разума". И мы в них играем. Просто я говорю что в этих играх я бы не стал
кодить конкретно данную задачу. Она мне неинтересна. Но мне интересны различные обобщения.

Кроме того в каждом топике у меня есть скрытый интерес. Например здесь скрытый интерес - графы и Resouce Definition
Language.
...
Рейтинг: 0 / 0
Как решить задачу по комбинаторике?
    #39765372
Gennadiy Usov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Гость
Сообщение 21794898 можно немножко поправить:

Шаг 1. цикл по х15 - определяем а1

Шаг 2. цикл по х16 - определяем х14 (х14 + х16 = 20 или 19)( 21793947),

Шаг 3. цикл по х12
Здесь определяем в следующей последовательности: х13, а2, а3, х8, х9, х10, х11.

Далее
- есть две внутренние окружности (которые ранее не "использовались"), где можно проверить соотношение: х12, х13, а2, а3, х8, х9, х10, х11.
- есть средняя окружность (ранее не "использовалась"), где можно проверить соотношение х8, х9, х10, х11

Шаг 4. Цикл по х2 - определяем х5 из а1

Шаг 5. Цикл по х3 – определяем х6 из а2

Шаг 6. Цикл по х4 – определяем х7 из а3

Всего 6 циклов.
3 основных и 3 вспомогательных (попарные перестановки 6 чисел)
...
Рейтинг: 0 / 0
Как решить задачу по комбинаторике?
    #39765381
Gennadiy Usov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Гость
Теперь попробуем разобраться с а1, а2, и а3, для которых имеем 6 "свободных" чисел (если есть такое решение).

Допустим, для каждого а1,а2,а3 получаем только одну пару чисел - один вариант разбивки чисел для а1, а2, а3.

Тогда для а1 имеем 2 варианта решения,
для а1 и а2 имеем 4 варианта решения,
для а1, а2 и а3 имеем 8 вариантов решений.

Если взглянуть на решения 21794557 , то получается, что
- имеется одно решение для х1, х8, х9, ...., х17,
- имеется два варианта разбивки 6 чисел для а1, а2, а3.

То есть, всего 16 решений.
...
Рейтинг: 0 / 0
Как решить задачу по комбинаторике?
    #39765387
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Dima TmaytonТы уже опубликовал это где-то в гитхабе? Я хотел сделать несколько changes.
Залил. Экспериментируй
Я пока в коде ничего не менял. Просто посмотрел под Valgrind/Callgrind.
Из за того что основное тело алгоритма представляет собой колбасу без вызвов подпрограмм
то callgrind не разбивает репорт в разрезе каждой функции.

Грубо говоря в отчоте callgrind видно 85 вызовов буст-овского nextpermutation. А это неинтересно
с точки зрения анализа реализации

Если ее зарефакторить так чтобы каждый цикл был функцией тогда калгринд дал-бы более материальный отчот.

Конечно это можно все эмулировать счетчиками и логгированием но как-то хотелось доверять технологии.

Trust to technology bro... :)
...
Рейтинг: 0 / 0
Как решить задачу по комбинаторике?
    #39765388
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
85 миллионов вызовов.
...
Рейтинг: 0 / 0
Как решить задачу по комбинаторике?
    #39765390
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Картинка с профилированием.
...
Рейтинг: 0 / 0
Как решить задачу по комбинаторике?
    #39765391
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Глупый codeblocks. Где в нём рефакторинг? Где extract procedure...
...
Рейтинг: 0 / 0
Как решить задачу по комбинаторике?
    #39765392
Gennadiy Usov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Гость
Gennadiy UsovЕсли взглянуть на решения 21794557 , то получается, что
- имеется одно решение для х1, х8, х9, ...., х17,
- имеется два варианта разбивки 6 чисел для а1, а2, а3.

То есть, всего 16 решений.Только сейчас до меня дошло, что только одно основное решение!

Раньше у нас было 12 уравнений и 15 неизвестных.

Если вводятся а1, а2 и а3 вместо х2, х3, х4, х5, х6, х7, то имеем:

12 уравнений и 12 неизвестных

1 решение!!!


Завтра попробую расписать формулы.

А кто-то поторопился написать программу.
...
Рейтинг: 0 / 0
Как решить задачу по комбинаторике?
    #39765398
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
В таком случае отчот Димы содержит некорректные расстановки.
Можете их указать?
...
Рейтинг: 0 / 0
Как решить задачу по комбинаторике?
    #39765403
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Зарефакторил один внутренний цикл. Пока не сильно помогает понять картину вызвов. К компилляции
добавил опцию -pg. Теперь можно смотреть gprof. Пока такая картинка.

Код: plaintext
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
Flat profile:

Each sample counts as 0.01 seconds.
  %   cumulative   self              self     total           
 time   seconds   seconds    calls  ns/call  ns/call  name    
 78.30      1.04     1.04 183968784     5.66     5.66  frame_dummy
 21.08      1.32     0.28                             start(int, int, int)
  0.75      1.33     0.01   416256    24.05   159.90  loop1(int, int*, int*, int*, int*, int*, int*, int*, int*, int*, int*, int*, int*, int*, int*, int*, int*, int, int*)
  0.00      1.33     0.00    50778     0.00     0.00  next_combination(unsigned long*, unsigned long, unsigned long)
  0.00      1.33     0.00     2103     0.00     0.00  copy_arr(int const*, unsigned long, int*, int, int, int, int, int, int)
...
Рейтинг: 0 / 0
Как решить задачу по комбинаторике?
    #39765428
Gennadiy Usov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Гость
Gennadiy UsovРаньше у нас было 12 уравнений и 15 неизвестных.
Если вводятся а1, а2 и а3 вместо х2, х3, х4, х5, х6, х7, то имеем:
12 уравнений и 12 неизвестных
1 решение!!!
Завтра попробую расписать формулы.
А кто-то поторопился написать программу. Не получилось!
Уравнения превращаются в тождества


Остаётся только все переменные выразить через х12,х15,х16

х1= К / 3
х14 = 20 – х16
Из большой окружности
х13 = К – 32 – х15 – х12
Из диагоналей:
а1 = К – х15 – 12 – х1
а2 = 32 + х15 + х12 – х16 – х1
а3 = К – х1 – 20 + х16 – х12

Далее проверка – малая окружность.

Аналогично находим х8,х9,х19,х11 из внутренних окружностей, где они встречаются по одному.
далее проверка, где они по два,
далее проверка на средней окружности.maytonВ таком случае отчот Димы содержит некорректные расстановки.
Можете их указать?Указать не могу. Остаётся перебор.

Просто приведенные расчеты позволяют несколько сократить количество циклов.
...
Рейтинг: 0 / 0
Как решить задачу по комбинаторике?
    #39765429
Gennadiy Usov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Гость
В предыдущем сообщении получено уравнение из суммы все диагоналей:Gennadiy Usovх1= К / 3Получается, что из двух вариантов для х1 и х17
Gennadiy UsovА именно:
1)выкидываем 10, в центре 20, сумма круга (диаметра) 60
2)выкидываем 20, в центре 19, сумма круга (диаметра) 57.остаётся первый: 20 и 10.
...
Рейтинг: 0 / 0
Как решить задачу по комбинаторике?
    #39765430
Dima T
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
maytonDima Tпропущено...

Залил. Экспериментируй
Я пока в коде ничего не менял. Просто посмотрел под Valgrind/Callgrind.
Из за того что основное тело алгоритма представляет собой колбасу без вызвов подпрограмм
то callgrind не разбивает репорт в разрезе каждой функции.

Грубо говоря в отчоте callgrind видно 85 вызовов буст-овского nextpermutation. А это неинтересно
с точки зрения анализа реализации

Если ее зарефакторить так чтобы каждый цикл был функцией тогда калгринд дал-бы более материальный отчот.

Конечно это можно все эмулировать счетчиками и логгированием но как-то хотелось доверять технологии.

Trust to technology bro... :)
next_combination() это сочетания, по-другому это
Код: plaintext
1.
2.
3.
4.
	size_t ic[4] = { 0, 1, 2, 3 }; // Индексы выбранных элементов
	do { // Перебор по 4 из 15
...
	} while (next_combination(ic, 4, 15));


можно написать так
Код: plaintext
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
size_t ic[4];
for(ic[0] = 0; ic[0] < 15; ic[0]++) {
	for(ic[1] = ic[0] + 1; ic[1] < 15; ic[1]++) {
		for(ic[2] = ic[1] + 1; ic[2] < 15; ic[2]++) {
			for(ic[3] = ic[2] + 1; ic[3] < 15; ic[3]++) {
...
			}
		}
	}
}



std::next_permutation() это размещения. Можно так через циклы написать
Код: plaintext
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
size_t ic[4];
for(ic[0] = 0; ic[0] < 15; ic[0]++) {
	for(ic[1] = 0; ic[1] < 15; ic[1]++) {
		if(ic[1] == ic[0]) break;
		for(ic[2] = 0; ic[2] < 15; ic[2]++) {
			if(ic[2] == ic[0] || ic[2] == ic[1]) break;
			for(ic[3] = 0; ic[3] < 15; ic[3]++) {
				if(ic[3] == ic[0] || ic[3] == ic[1] || ic[3] == ic[0]) break;
...
			}
		}
	}
}



Если в код заглянешь - все циклы вложенные, заменив next_combination() получим 9 циклов вместо 2, заменив std::next_permutation() - 11 циклов вместо двух. Итого +16 вложенных циклов. ИМХО это будет не код, а фарш какой-то.
...
Рейтинг: 0 / 0
Как решить задачу по комбинаторике?
    #39765438
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Что тебя смущает? Следуй советам Фаулера.
Делай функции как можно меньшего размера.

Его рекомендации относились ко всем языкам включая C++.

О преждевременной оптимизации не парься. О ней надо думать тогда, когда точно известен bottleneck.
...
Рейтинг: 0 / 0
Как решить задачу по комбинаторике?
    #39765440
Gennadiy Usov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Гость
Gennadiy UsovОстаётся только все переменные выразить через х12,х15,х16

Из большой окружности
х13 = К – 32 – х15 – х12 Здесь можно организовать выборку сочетаний по 3 из 15 для определения х12,х15,х16.
При этом будут отсеиваться те сочетания, для которых не подходит х13.
Получаем 245 вариантов без учета отсеянных.

Если сочетания для варианта найдены, то имеем перестановки из 3-х элементов - всего 6 подвариантов для варианта.
И для каждого подварианта определяются формулы из 21795083 с проверками.
Всего 6 подвариантов для одного варианта.

И не нужны циклы по каждому неизвестному. Есть один цикл для варианта и один цикл для подварианта.

Для определения составляющих х2,х3,х4.х5,х6,х7 из оставшихся 6 чисел:

Имеем сочетания 3 из 6 для каждой пары. Всего 20 сочетаний.

И перестановки для этих пар из оставшихся 3-х чисел. Всего 6 перестановок.
Итого 120 вариантов.

Всё перемножать не следует, так как при работе с подвариантами будет очень большой отсев.
В частности, в нашей задачке останется только один вариант, один подвариант, 2 сочетания и 8 перестановок для каждого сочетания. maytonВ таком случае отчот Димы содержит некорректные расстановки.
Можете их указать?Продолжаются упрощения процесса вычислений:

1) Остаётся только 4 цикла: для варианта, для подварианта, для сочетания, для расстановки.
2) Идет работа не с объектами графа (окружности, диагонали), а с конкретными формулами вычисления неизвестных.
...
Рейтинг: 0 / 0
Как решить задачу по комбинаторике?
    #39765442
Gennadiy Usov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Гость
Кстати, все формулы по определению неизвестных можно будет "загнать" в одну процедуру, из которой может быть несколько "аварийных выходов" в случае нарушения правила "свободного" числа или в случае выхода за границу массива чисел.
...
Рейтинг: 0 / 0
25 сообщений из 450, страница 6 из 18
Форумы / Программирование [игнор отключен] [закрыт для гостей] / Как решить задачу по комбинаторике?
Найденые пользователи ...
Разблокировать пользователей ...
Читали форум (0):
Пользователи онлайн (0):
x
x
Закрыть


Просмотр
0 / 0
Close
Debug Console [Select Text]