Добро пожаловать в форум, Guest  >>   Войти | Регистрация | Поиск | Правила | В избранное | Подписаться
Все форумы / Программирование Новый топик    Ответить
Топик располагается на нескольких страницах: [1] 2 3 4 5 6 7 8 9 10 .. 18   вперед  Ctrl
 Как решить задачу по комбинаторике?  [new]
Дмитрий Смеркс
Member

Откуда:
Сообщений: 3
Недавно наткнулся на очень на мой взгляд задачку по комбинаторике. Так как в школе комбинаторику плохо преподавали в своё время, никак решить не могу. Второй день мучаюсь. Есть варианты. Буду безумно благодарен, если поможете. Задачу прикрепляю. Изначально решил сделать обычный подбор состоящий из 9 циклов, но кажется есть путь попроще. И с другой стороны как сделать так, чтобы числа не повторялись, то есть уникальный подбор
1 2 3 4 5 6 7 8 9 ...
а не 11111233...

К сообщению приложен файл. Размер - 137Kb
24 янв 19, 04:09    [21792769]     Ответить | Цитировать Сообщить модератору
 Re: Как решить задачу по комбинаторике?  [new]
Dima T
Member

Откуда:
Сообщений: 13634
Дмитрий Смеркс
Изначально решил сделать обычный подбор состоящий из 9 циклов, но кажется есть путь попроще.

Это называется размещения без повторений, гугл в помощь.
24 янв 19, 08:21    [21792827]     Ответить | Цитировать Сообщить модератору
 Re: Как решить задачу по комбинаторике?  [new]
kealon(Ruslan)
Member

Откуда: Нижневартовск
Сообщений: 4487
Dima T,
не так и много вариантов

17! / (4! 5! 6!) = 171 531 360
24 янв 19, 10:12    [21792953]     Ответить | Цитировать Сообщить модератору
 Re: Как решить задачу по комбинаторике?  [new]
Aleksandr Sharahov
Member

Откуда: Москва
Сообщений: 1741
с акцентом Шварца: какие ваши доказательства?
24 янв 19, 10:25    [21792974]     Ответить | Цитировать Сообщить модератору
 Re: Как решить задачу по комбинаторике?  [new]
Dima T
Member

Откуда:
Сообщений: 13634
ИМХО Не обязательно перебор всех вариантов устраивать, можно сначала упростить задачу, например перебрать всевозможные две диагонали - это ((17! / (13! * 4!)) * (13! / (9! * 4!))) всего 1701700 комбинаций. А дальше проверять только те решения, у которых сумма по диагоналям совпала.
24 янв 19, 11:00    [21793039]     Ответить | Цитировать Сообщить модератору
 Re: Как решить задачу по комбинаторике?  [new]
kealon(Ruslan)
Member

Откуда: Нижневартовск
Сообщений: 4487
Dima T,

а если твою формулу с другого круга начать? тоже самое выйдет ;-)?
освежить бы надо комбинаторику
24 янв 19, 11:03    [21793043]     Ответить | Цитировать Сообщить модератору
 Re: Как решить задачу по комбинаторике?  [new]
mayton
Member

Откуда: loopback
Сообщений: 40510
Это - задача на бэктректинг. Думю что решение о том что нельзя поставить данную
расстановку надо принять гораздо раньше. До того как будут перебраны все варианты.
На ходу.

Грубо говоря здесь не совсем чисты факториал - а амортизированный.
24 янв 19, 11:07    [21793045]     Ответить | Цитировать Сообщить модератору
 Re: Как решить задачу по комбинаторике?  [new]
kealon(Ruslan)
Member

Откуда: Нижневартовск
Сообщений: 4487
Dima T, кроме того

((17! / (13! * 4!)) * (13! / (9! * 4!)))

наверное С(4, 17) * С(5, 13) хотел написать?
24 янв 19, 11:08    [21793048]     Ответить | Цитировать Сообщить модератору
 Re: Как решить задачу по комбинаторике?  [new]
Малыхин Сергей
Member

Откуда: г. Курск
Сообщений: 715
Тут пересекающиеся множества тождественные между собой. (система линейных уравнений)

Есть несколько точек не принадлежащих множеству и центральный круг у которого нет собственных свободных точек.
у всех остальных тождественные множеств есть пара точек лежащих вне пересечения.
Суть задачи просто правильно сформулировать систему уравнений упростить ее и решить.
24 янв 19, 11:23    [21793073]     Ответить | Цитировать Сообщить модератору
 Re: Как решить задачу по комбинаторике?  [new]
mayton
Member

Откуда: loopback
Сообщений: 40510
Самые селективные предикаты поднять наверх. Тоесть не решать систему до конца а максимально
быстро принять решение что дальше решать не стоит.
24 янв 19, 11:37    [21793090]     Ответить | Цитировать Сообщить модератору
 Re: Как решить задачу по комбинаторике?  [new]
kealon(Ruslan)
Member

Откуда: Нижневартовск
Сообщений: 4487
Dima T,

и я ошибся всё таки, не увидел что одно число не расставляется, это уменьшает вдвое количество вариантов для полного перебора

17! / (2! 4! 5! 6! ) = 85 765 680


Малыхин Сергей, одно выпадающее число сразу удвацетирит количество систем, его наверное можно с ручкой и бумажкой порешать, но мы же программисты, проще перебрать
24 янв 19, 11:37    [21793092]     Ответить | Цитировать Сообщить модератору
 Re: Как решить задачу по комбинаторике?  [new]
kealon(Ruslan)
Member

Откуда: Нижневартовск
Сообщений: 4487
хотя нет, всё верно

17! / (1! 4! 5! 6!) = 171 531 360 вариантов
24 янв 19, 11:44    [21793102]     Ответить | Цитировать Сообщить модератору
 Re: Как решить задачу по комбинаторике?  [new]
Dima T
Member

Откуда:
Сообщений: 13634
kealon(Ruslan)
Dima T, кроме того

((17! / (13! * 4!)) * (13! / (9! * 4!)))

наверное С(4, 17) * С(5, 13) хотел написать?

Нет, но немного ошибся, на 4 надо было умножить:
1. Берем все сочетания 17 по 4 (17! / (13! * 4!) = 2380) и подставляем их в горизонтальный диаметр 4-мя способами (каждый элемент в центр) - это 9520 комбинаций.
2. Из оставшихся все сочетания 13 по 4 в один диагональный диаметр - 715 комбинации. Если сумма не совпала, то п.1

9520*715 = 6806800
24 янв 19, 11:54    [21793120]     Ответить | Цитировать Сообщить модератору
 Re: Как решить задачу по комбинаторике?  [new]
kealon(Ruslan)
Member

Откуда: Нижневартовск
Сообщений: 4487
Dima T,

если твоим путём идти тебе нужно просуммировать все 4! варианта

по трём основным кругам: в 1-м 5 элементов нужно расставить, во втором - 4, в третьем - 6, центральный -1

будет сумма переборов

C(5, 17) * C(4, 12) * C(6, 8) * С(1, 2) +
C(4, 17) * C(5, 13) * C(6, 8) * С(1, 2) +
+...


т.е. 24 варианта замены порядка
24 янв 19, 12:16    [21793160]     Ответить | Цитировать Сообщить модератору
 Re: Как решить задачу по комбинаторике?  [new]
mayton
Member

Откуда: loopback
Сообщений: 40510
Запилите уже поиск в глубину.
24 янв 19, 12:19    [21793165]     Ответить | Цитировать Сообщить модератору
 Re: Как решить задачу по комбинаторике?  [new]
kealon(Ruslan)
Member

Откуда: Нижневартовск
Сообщений: 4487
Dima T,
блин, вру, не надо их суммировать, везде одинаковое число будет

C(5, 17) * C(4, 12) * C(6, 8) * С(1, 2) = 17!/ 5! / 4! / 6!

C(4, 17) * C(5, 13) * C(6, 8) * С(1, 2) = 17! / 4!/ 5!/ 6!
24 янв 19, 12:25    [21793180]     Ответить | Цитировать Сообщить модератору
 Re: Как решить задачу по комбинаторике?  [new]
Dima T
Member

Откуда:
Сообщений: 13634
kealon(Ruslan)
Dima T,

если твоим путём идти тебе нужно просуммировать все 4! варианта

по трём основным кругам: в 1-м 5 элементов нужно расставить, во втором - 4, в третьем - 6, центральный -1

будет сумма переборов

C(5, 17) * C(4, 12) * C(6, 8) * С(1, 2) +
C(4, 17) * C(5, 13) * C(6, 8) * С(1, 2) +
+...


т.е. 24 варианта замены порядка

Нет. Сначала решаем упрощенную задачу: сумма двух диаметров совпала, поэтому без разницы в каком порядке на горизонтальном диаметре кроме центрального элемента, т.е. каждой комбинации из 17 по 4 есть всего 4 варианта записи (не 4!).
Например для набора 1,2,3,4 будет
12,2,1,3,4
12,1,2,3,4
12,1,3,2,4
12,1,4,2,3
На этом этапе остальные комбинации это повтор этих, например 12,4,2,3,1 тоже самое что и 12,1,2,3,4

Для диагонального диаметра вообще без разницы какой порядок, т.к. центр заполнен горизонтальным.

На следующих шагах решения придется перебрать пропущенные комбинации, но это далеко не все возможные комбинации.
24 янв 19, 12:37    [21793200]     Ответить | Цитировать Сообщить модератору
 Re: Как решить задачу по комбинаторике?  [new]
mayton
Member

Откуда: loopback
Сообщений: 40510
КМК задача связана с Магическими квадратами.
24 янв 19, 12:39    [21793204]     Ответить | Цитировать Сообщить модератору
 Re: Как решить задачу по комбинаторике?  [new]
kealon(Ruslan)
Member

Откуда: Нижневартовск
Сообщений: 4487
Dima T,

зря мы тут по комбинаторике голову ломаем, все элементы связаны, т.е. позиция важна, придётся 17! вариантов перебирать

но
сумма трёх диагоналей 3S = сумме внутреннего и внешнего круга 2S + 3C


S = 3C, т.е. в центре число равное трети от суммы

пусть X выкинутое число
X + C + 3S= 21*20/2 =210

3X + 10 S = 630

Х = 10 | 20
соответственно
S = 60 | 57
С = 30 | 29 ??????????????????? что нереально

или где-то в условие неверно?
24 янв 19, 13:07    [21793256]     Ответить | Цитировать Сообщить модератору
 Re: Как решить задачу по комбинаторике?  [new]
Gennadiy Usov
Member

Откуда:
Сообщений: 1462
На самом деле, всё ещё проще.

Общая сумма от 1 до 20 = 210.

Имеем 3 основных круга по 6 кружков. Всего 19 кружков.
Отнимаем от 210 значения 2-х произвольных кружков и делим оставшееся на 3.

Имеем 3 диаметра + средний круг (итого 4 элемента). Всего 19 кружков.
Отнимаем от 210 значения 1-ого произвольного кружка и добавляем 2 раза значение другого произвольного кружка. Всего 21 кружок. Всю сумму делим на 4.

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

А именно:
1)выкидываем 10, в центре 20, сумма круга (диаметра) 60
2)выкидываем 20, в центре 19, сумма круга (диаметра) 57.

Наверное, дальше, будет проще...
24 янв 19, 13:59    [21793339]     Ответить | Цитировать Сообщить модератору
 Re: Как решить задачу по комбинаторике?  [new]
kealon(Ruslan)
Member

Откуда: Нижневартовск
Сообщений: 4487
Gennadiy Usov,

выкинуть можно только кратное 3-м
24 янв 19, 14:02    [21793347]     Ответить | Цитировать Сообщить модератору
 Re: Как решить задачу по комбинаторике?  [new]
Gennadiy Usov
Member

Откуда:
Сообщений: 1462
kealon(Ruslan)
Gennadiy Usov,

выкинуть можно только кратное 3-м
А где это написано в условии?
24 янв 19, 14:06    [21793351]     Ответить | Цитировать Сообщить модератору
 Re: Как решить задачу по комбинаторике?  [new]
Gennadiy Usov
Member

Откуда:
Сообщений: 1462
Можно по формулам.

а - выкидываем,
в - в центре

(210 - а - в) / 3 = ( 210 - а + 2 х в) / 4

или

210 = а + 10 х в
24 янв 19, 14:22    [21793374]     Ответить | Цитировать Сообщить модератору
 Re: Как решить задачу по комбинаторике?  [new]
Dima T
Member

Откуда:
Сообщений: 13634
+ Посчитал все варианты для трех диаметров
#include <iostream>
#include <cstdio>
#include <string.h>
#include <set>

int total = 0, count = 0, min_sum = 99, max_sum = 0;

std::set<int> sums;

// Перебор 9 по 4
void combination9by4(int* numbers13, size_t j0, size_t j1, size_t j2, size_t j3, int center, int sum) {
	int n0 = numbers13[j0], n1 = numbers13[j1], n2 = numbers13[j2], n3 = numbers13[j3];
	// Оставшиеся 9
	int numbers9[9];
	for (size_t i = 0, j = 0; i < 13; i++) {
		int n = numbers13[i];
		if (n != n0 && n != n1 && n != n2 && n != n3) {
			numbers9[j] = n;
			j++;
		}
	}
	// Сочетания 9 по 4
	for (size_t k0 = 0; k0 < 9; k0++) {
		for (size_t k1 = k0 + 1; k1 < 9; k1++) {
			for (size_t k2 = k1 + 1; k2 < 9; k2++) {
				for (size_t k3 = k2 + 1; k3 < 9; k3++) {
					if (sum == numbers9[k0] + numbers9[k1] + center + numbers9[k2] + numbers9[k3]) {
						if (sums.find(sum) == sums.end()) {
							sums.insert(sum);
							printf("sum = %d\n", sum);
							if (sum < min_sum) min_sum = sum;
							if (sum > max_sum) max_sum = sum;
						}
						count++;
					}
				}
			}
		}
	}

}


// Перебор 13 по 4
void combination13by4(int* numbers17, size_t i0, size_t i1, size_t i2, size_t i3) {
	int n0 = numbers17[i0], n1 = numbers17[i1], n2 = numbers17[i2], n3 = numbers17[i3];
	// Сумма горизонтального диаметра
	int sum = 12 + n0 + n1 + n2 + n3;
	// Оставшиеся 13
	int numbers13[13]; 
	for (size_t i = 0, j = 0; i < 17; i++) {
		int n = numbers17[i];
		if (n != n0 && n != n1 && n != n2 && n != n3) {
			numbers13[j] = n;
			j++;
		}
	}
	// Сочетания 13 по 4
	for (size_t j0 = 0; j0 < 13; j0++) {
		for (size_t j1 = j0 + 1; j1 < 13; j1++) {
			for (size_t j2 = j1 + 1; j2 < 13; j2++) {
				for (size_t j3 = j2 + 1; j3 < 13; j3++) {
					total++;
					if (sum == numbers13[j0] + numbers13[j1] + n1 + numbers13[j2] + numbers13[j3]) {
						combination9by4(numbers13, j0, j1, j2, j3, n1, sum);
					}
				}
			}
		}
	}

}

// Сочетания 17 по 4 (горизонталь)
void combination17by4() {
	// Возможные значения
	int numbers17[17] = { 1, 2, 3, 4 , 5, 7, 8, 9, 10, 11, 13, 14, 15, 16, 17, 19, 20 };

	for (size_t i0 = 0; i0 < 17; i0++) {
		for (size_t i1 = i0+1; i1 < 17; i1++) {
			for (size_t i2 = i1 + 1; i2 < 17; i2++) {
				for (size_t i3 = i2 + 1; i3 < 17; i3++) {
					combination13by4(numbers17, i1, i0, i2, i3);
					combination13by4(numbers17, i0, i1, i2, i3);
					combination13by4(numbers17, i0, i2, i1, i3);
					combination13by4(numbers17, i0, i3, i1, i2);
				}
			}
		}
	}
}

int main(int argc, char** argv[])
{
	combination17by4();
	printf("total %d  count %d  min_sum %d  max_sum %d\n", total, count, min_sum, max_sum);
	system("pause");
	return 0;
}


Результат 533520 комбинаций диаметров.
Дальше заполняем средний круг (6, 18, ... ) 4-мя из оставшихся 5-ти, т.е. комбинаций станет 533520 * 5.

Дальше остается перебрать комбинации в каждом диаметре (3!, 4!, 4!) и среднем круге (4!). Итого 82944.

Всего максимум 533520 * 5 * 82944 = 221`261`414`400. Многовато, но думаю комбинаций после заполнения среднего круга будет поменьше чем 5*533520.


Разбег сумм получился от 34 до 69.
24 янв 19, 14:47    [21793408]     Ответить | Цитировать Сообщить модератору
 Re: Как решить задачу по комбинаторике?  [new]
Dima T
Member

Откуда:
Сообщений: 13634
Добавил заполнение среднего круга, вариантов осталось 41796, для каждого надо допроверить 82944 подварианта.

Итого 41796*82944 = 3`466`727`424. Это реально обсчитать перебором.
24 янв 19, 14:59    [21793429]     Ответить | Цитировать Сообщить модератору
Топик располагается на нескольких страницах: [1] 2 3 4 5 6 7 8 9 10 .. 18   вперед  Ctrl
Все форумы / Программирование Ответить