Алгоритмический вопрос по комбинаторике

← →
net_daemon (2006-11-15 10:33) [0]

День добрый, Мастера!
Есть алгоритмическая задача следующего плана:
Существует некое множество А (в моем случае - неповторяющихся целых чисел) и
некое подмножество В множества А.
Задача: итерационно выдывать множества C[i], которые представляют собой
множество А минус i элементов подмножества B во всех возможных вариантах
(тут, видимо, элементы комбинаторики).
Для пояснения приведу пример:
А = (a, b, c, d, e);
B = (a, b, c);
шаг 1: i:=0
C[1, 1] := (a, b, c, d, e);
шаг 2: i:=1
C[2, 1] := (b, c, d, e);
C[2, 2] := (a, c, d, e);
C[2, 3] := (a, b, d, e);
шаг 3: i:=2
C[3, 1] := (c, d, e);
C[3, 2] := (b, d, e);
C[3, 3] := (a, d, e);
шаг 4: i:=3
C[4, 1] := (d, e);

Структура множеств может быть любая: массивы, списки. Я использую списки (TList).
для частного случая, когда из множества А исключается по 1 элементу подмножества
В все вроде бы понятно:
type // запись элементов a, b, ... TUsed_Struct = packed record Element : integer; // остаьные поля end; TpUsed_Struct = ^TUsedStruct; var A : TList; // основное множество B : TList; // подмножество С : TList; // множество для вывода результата procedure SortOut; var pMainStruct : TpUsedStruct; // указатель для работы со списком осн. множества А pSubStuuct ; TpUsedStruct; // указатель для работы со списком подмножества В i, j : WORD; begin // предполагается, что списки A и В криэйтнуты и заполнены С := TList.Create; // создаем список вывода необходимых множеств for i:=0 to (B.Count -1) do begin // выделяем память под указатель new(pSubStruct); // берем элемент из подмножества pSubStruct := B.Items[i]; for j:=0 to (A.Count-1) do begin // выделяем память под указатель new(pMainStruct); // берем элемент из основного множества pMainStruct := A.Items[j]; // сравниваем элементы множеств if pSubStruct^.Element <> pMainStruct^.Element then C.Add(pMainElement); end; // здесь идет работа с получившимся множеством С, обнуление этого множества и т.д. end; // освобождение памяти и пр. end;
Так вот - для ситуации, когда подключается комбинаторика и надо исключать из
первоначального множества более 1 элемента - ничего придумать не могу!
Помогите кто чем может, плиз!

← →
Vlad Oshin © (2006-11-15 11:14) [1]

не очень вникал, но может Set поможет?

var
a:set of byte;
b:set of byte;
bb:byte;
begin
bb:=6;
a:=a+[bb]; //множество a содержит 1 элемент = 6
a:=a+[7]; //a=6,7
b:=b+[7]; // b=7
a:=a-b; //a=6 (вычитается из мнва А мнво В)

← →
Anatoly Podgoretsky © (2006-11-15 11:48) [2]

> net_daemon (15.11.2006 10:33:00) [0]

> Так вот - для ситуации, когда подключается комбинаторика и надо исключать из
первоначального множества более 1 элемента - ничего придумать не могу!

Что ты хочешь сделать и в чем проблема, если возникает ошибка, то у тебя не тот цикл, надо удалять обратным циклом.

← →
MBo © (2006-11-15 13:40) [3]

Пусть множество B содержит N элементов. Существует 2^N подмножеств этого множества, и их нетрудно получить, пройдя цикл по K от 0 до (1 shl N) -1
Установленные в 1 биты очередного K соответствуют наличию элемента в множестве, так получаем подмножество Bk, и складываем его с постоянной частью (A - B)

← →
net_daemon (2006-11-15 14:58) [4]

> Vlad Oshin
Т.е. Set позволяет удалять элементы вне зависимости от их положения в наборе?

>Anatoly Podgoretsky
Задача по рассчету вероятности, это - один из моментов необходимых для вычисления формулы.
Циклов еще нет - не могу придумать алгоритм перебора всех комбинаций элементов подмножества, учитывая, что (a, b) = (b, a) и такую комбинацию нужно использовать один и только один раз.

>MBo
Не очень понятно :-( Как я получу в К искомые подмножества? И с чем мне сравнивать биты полученного результата?

← →
Vlad Oshin © (2006-11-15 15:09) [5]

> Т.е. Set позволяет удалять элементы вне зависимости от их
> положения в наборе?

да
если они совпадают - вычитает. Там, правда есть ограничение на кол-во, и скорость работы с set ниже

но, видимо, тебе надо немного другое,
смотри мбо - изяшная мысль

← →
MBo © (2006-11-15 15:09) [6]

На твоем примере
A = (a,b,c,d,e)
B = (a,b,c)
A-B = (d,e)
мощность множества B - 3, так что у него 8 подмножеств
for k = 0 to 7
на первом шаге k=0, или в двоичном представлении 000b - все биты нулевые, Bk - пустое множество
на втором шаге k = 1 = 001b - Bk = (c)
...
k =7 = 111b - Bk = (a,b,c)
Проверку на установленные биты можно в цикле делать с помошью логического and, или Odd со сдвигом shr

← →
net_daemon (2006-11-16 12:47) [7]

> MBo

Очень изящная мысль, сейчас буду пробовать.

← →
novill © (2006-11-16 13:42) [8]

> Так вот - для ситуации, когда подключается комбинаторика
> и надо исключать из
> первоначального множества более 1 элемента - ничего придумать
> не могу!
> Помогите кто чем может, плиз!

Чем могу :)

простой вариант, но при большом количестве элементов в базовом множестве (>10) будет тормозить.

Вот эта процедура выведет все возможные сочетания выбора К элементов из N элементного множества.

на форме 1 кнопка, 1 мемо, 2 spinedit( или любой другой edit возвращающий целое значение)

procedure TForm1.Button1Click(Sender: TObject); var j,i:integer; allc:integer; count:integer; s:string; minc:integer; begin Memo1.Clear; allc:=round(Power(2,N.Value)); minc:=round(Power(2,K.Value)); // for i:=0 to allc do //перебор ВСЕХ ВОЗМОЖНЫХ подмножеств for i:=minc to allc do // исключена часть заведомо неподходящих begin count:=0; for j:=0 to N.Value-1 do if (i and (1 shl j))>0 then inc(count); // подсчет количества элементов данного подмножества if count=K.Value then // Количество элементов (в данном случае установленних битов) совпадает с заданным! Что делать дальше - тебе решать ))) // в числе i будут установлены биты соответствующих номеров // вывод begin // следующие три строчки только потому что я забыл название функции перевода десятичное в бинарную строку s:=stringofchar("0",n.Value); for j:=0 to N.Value-1 do if (i and (1 shl j))>0 then s[n.Value-j]:="1"; Memo1.Lines.Add(s); end; end; end;

Есть еще быстрый рекурсивный вариант, но это гуглить надо хорошо.

> [9] novill © (16.11.06 14:30)

Ты каждое решение гуглишь что ль? И [8] нагуглил? С чего ты взял, что в диапазоне

> for i:=minc to allc do // исключена часть заведомо неподходящих

останутся только подходящие? Здесь allc надо сдвигать вправо, от 0 до него перебирать и результаты перебора двигать влево. Или цикл сделать while и шаг инкремента будет minc. Тогда вообще двигать ничего не надо. В том и другом случае в результате получишь набор искомых множеств. Останется только отобразить. И что такое N.Value и K.Value?

> Ты каждое решение гуглишь что ль? И [8] нагуглил?
[8] написал сам, просто подумал немного. А гуглить реализацию непростых алгоритмов - первое дело.

> С чего ты взял, что в диапазоне
>
> > for i:=minc to allc do // исключена часть заведомо неподходящих
>
> останутся только подходящие?

Разжевывать не буду, рекомендую посмотреть на примерах. что есть 2^k при переборе сочитаний от 0 до 2^n.

> Здесь allc надо сдвигать вправо, от 0 до него перебирать
> и результаты перебора двигать влево. Или цикл сделать while
> и шаг инкремента будет minc. Тогда вообще двигать ничего
> не надо. В том и другом случае в результате получишь набор
> искомых множеств.

Что здесь надо делать можешь мне не указывать. Есть предложение - напиши реализацию.

> И что такое N.Value и K.Value?

А читать внимательно???

> Вот эта процедура выведет все возможные сочетания выбора
> К элементов из N элементного множества.

> 2 spinedit( или любой другой edit возвращающий целое значение)

Алгоритмический вопрос по комбинаторике Найти похожие ветки