можно помогите для комбинаторской задаче?

[niakoisitam]

Извините что у меня русский плохой,но я из Болгарии.Я надеюсь, что это форум именно тот, который мне необходим. Мне нужна помощь в решении следующей комбинаторской задачи. Желательно решение задачи в среде PASCAL или C++.
Необходимо создать программу, которая бы выводила минимальный брой(n) У-сочетания из Х элементов таким образом, чтобы по крайней мере одно из этих У-сочетании будет подмножеством произвольно выбранного Z-сочетание из Х элементов. где ХЄ(3;30), УЄ(2;Z) и ZЄ(2;Х).
Необходимое дополнительное условие: на экран монитора должно выводится сколько У-сочетания из Х элементов будут подмножеством Z-сочетания из Х элементов; Z+1-сочетания из Х элементов; .... Х-сочетания из Х элементов

Результаты программы на экране монитора должны выглядеть примерно так:
Пример:
Введите Х=8
Введите У=4
Введите Z=6
n=6
1. 1 2 3 4

2. 1 4 5 8

3. 1 5 6 7

4. 2 3 5 8

5. 2 3 6 7

6. 4 6 7 8

Если шестое сочетание из 8 элементов было выбрано случайным образом, то у вас получатся от 1 до 3 четырехзначных сочетания из 8 элементов,которые будут принадлежать данному 6-сочетанию из 8 элементов.
Если вы выбрали наугад 7-сочетание из 8 элементов,то у вас будет 3 4-сочетания из
8 элементов,которые принадлежать данному 7-сочетание из 8 элементов.
Если вы выбрали наугад 8-сочетание из 8 элементов,то у вас будет 6 4-сочетания из
8 элементов,которые принадлежать данному 8-сочетание из 8 элементов.

[Артем]

А что такое

минимальный брой(n) У-сочетания из Х элементов .

?
Просто я уже который раз встречаю это словосочетание, но так никто и не сказал что оно значит
 

[niakoisitam]

минимальный брой(n) У-сочетания из Х элементов таким образом, чтобы по крайней мере одно из этих У-сочетании будет подмножеством произвольно выбранного Z-сочетание из Х элементов. где ХЄ(3;30), УЄ(2;Z) и ZЄ(2;Х).
   Надо понял это в целом,не только минимальный брой(n) У-сочетания из Х элементов,потому что это ничего не означает.
    Вот в примере минимальный брой 4-сочетания из 8 элементов,чтобы по крайней
мере одно из этих 4-сочетания будет подмножеством произвольно выбранного 6-сочетание из 8 элементов,будет 6,как и показано в примере.(значит n=6)

[Dimka]

вчера небольшой группкой разбирали задачу...

1. Поискав слово "брой" в инете обнаружили, что это либо фамилия , либо оно встречается в болгарских текстах. Судя по смыслу, видимо, "брой" означает "уровень" или "срез". Но в контексте данной задачи не совсем понятно.

2. Были попытки понять условие, получилось следующее.
а) Множества чего берутся. Если X - мощность множества, то из каких элементов оно берётся? Если это натуральные числа, то каким числом они ограничены сверху?
б) Множество из X элементов выбирается случайно из некоего другого непонятного множества (см. пункт а).
в) Берётся случайный порядок множества X, в нём выбираются первые Z элементов (можно сказать иначе, из исходного множества (см. пункт б) случайно выбирается Z элементов).
г) Получается множество всех возможных сочетаний длиной Y чисел множества X.
д) Из этого множества исключаются все те сочетания, которые не являются подмножествами того множества чисел, которое записано в сочетании длиной Z (см. пункт в).
е) нужно вывести число сочетаний, полученных в пункте д, и сами эти сочетания.

Если это правильное понимание задачи, то остаётся выяснить, из каких элементов состоит множество мощности X, являющееся основой всего решения.

[Артем]

. Если X - мощность множества, то из каких элементов оно берётся?

Насколько я понял, Х -это не мощность, а как раз множество. В первом постинге было

где ХЄ(3;30), УЄ(2;Z) и ZЄ(2;Х).

т.е., насколько я понял х может принимать значение от 3 до 30 (целые ) , z - могут принимать значение от 2 до х, и у--от 2 до z.
 Тогда вроде становиться понятней.

У меня просьба к niakoisitam--ответить, правильно ли я понял задачу:

 Есть множества целых чисел ХЄ(3;30)

Необходимо создать программу, которая бы выводила минимальный набор (было--брой(n) )
 У-сочетания из элементов множества Х, таким образом, чтобы по крайней мере одно из этих
 У-сочетании будет подмножеством произвольно выбранного Z-сочетание элементов множества
 Х.

где ХЄ(3;30), УЄ(2;Z) и ZЄ(2;Х).


Если же  я и dimka не правильно поняли условие задачи, то приведи условие на английском (если в оригинале оно было на английском).

[Dimka]

Артем, мы тоже сначала думали, что это множества, но

Пример:
Введите Х=8
Введите У=4
Введите Z=6

говорит, что это более похоже на мощности множеств.

[niakoisitam]

Так точно,Артем праильно понял задачу.Х,У и Z-множества из натуральньiх чисел.Введите Х=8,У=4 и Z=6,значит Х из 8 елементов,У из 4,Z из 6.Но и тут я самьi ошибаюсь думаю,потому что у меня русский плохой,и попробую объяснит как можно скорее все.   Благодарю вам всех,которьiе пьiтаетесь помочь

[niakoisitam]

примерно завтра я буду ответить етих вопросов!

[Dimka]

niakoisitam, тогда советую такие обозначения. Например, X - множество целых чисел от 3 до 30, |X| - мощность множества, например, 8. x - элемент множества X (если понадобится). (Под мощностью понимается размер.)

В таком случае
X = [3; 30], |X| принадлежит [?; ?] (тоже [3; 30]? максимально большое [2; 27]) (в примере = 8 )
Z принадлежит X, |Z| принадлежит [2; |X|] (в примере = 6)
Y принадлежит X, |Y| принадлежит [2; |Z|] (в примере = 4)

Т.е. прошу не путать сами множества чисел и множества мощностей (размеров) множеств. По-прежнему прошу пояснения о множестве X и его размере.

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

попытка понять фразу:

Есть множество X, из него выбираются случайные подмножества мощности |Y| некие Yk, такие, что для всякого Yi, Yj : Yi <> Yj, если i <> j, i, j, k = 1 ... N, но их пересечение может быть непустым. Есть подмножество Z из X мощности |Z|.

Положим, что у нас какое-то Yi является подмножеством Z. Тогда что есть минимальный набор? Все полученные Yi (на эту мысль наводит фраза "по крайней мере одно из", т.к. среди всех возможно найдётся нужное)? Мне казалось, что лишь те Yi, которые являются подмножеством Z, тогда фраза будет "каждое из". Иными словами, из приведённой цитаты я не понял критерий минимизации набора.