VPF::Вывести все подмножества множества

Innuendo

Дата 6.12.2006, 19:47 (ссылка)

(нет голосов)

Загрузка ...

Опытный

Профиль
Группа: Участник
Сообщений: 745
Регистрация: 24.12.2005
Где: Молдова

Репутация: нет
Всего: 6

Блин, вроде программка простенькая, но я с множествами никогда не работал, и чё-то не получается
есть множество M=['A','B','C','D']
надо вывести все подмножества. Чё-то не получается.. если бы массив, я бы сделал, а с множествами как-то не особо работается

--------------------

Zero

Дата 6.12.2006, 21:03 (ссылка)

(нет голосов)

Загрузка ...

Эксперт

Профиль
Группа: Завсегдатай
Сообщений: 2169
Регистрация: 23.10.2004
Где: Россия, г. Рязань

Репутация: нет
Всего: 24

Ну общий принцип такой:

Код


var
  M:set of char;
  i:integer;
Begin
  m := ['A','B','C','D'];
  for i:=1 to 255 do
    if chr(i) in m then
      write(chr(i),' ');
end.

volvo877

Дата 6.12.2006, 22:17 (ссылка)

(нет голосов)

Загрузка ...

Эксперт

Профиль
Группа: Комодератор
Сообщений: 2073
Регистрация: 15.11.2004

Репутация: 2
Всего: 116

Цитата(Innuendo @ 6.12.2006, 18:47

)

надо вывести все подмножества

Комбинаторика? Слово "множество", кстати, еще не означает, что тебе надо работать с типом Set ... Вот программа, печатающая все возможные подмножества множества из N элементов:

Код

Var N : Longint;
    Count : Longint;
    I : Longint;

Procedure PrintSet(X : Longint);
Var P : Integer;
Begin
 Write('{ ');
 P:=N;
 While X <> 0 Do
  Begin
   If X Mod 2 = 1 Then Write(P, ' ');
   Dec(P);
   X:=X Div 2;
  End;
 Writeln('}');
End;

Begin
 N:=4;
 Count:=1 Shl N; {2^N}
 For I:=0 To Count - 1 Do
  PrintSet(I);
End.

А уж что именно печатать вместо цифр 1 .. N - это ты и должен брать из своего M... У тебя там символы - значит,

Код


Write(Chr(Ord('A') + P - 1), ' ');

Количество символов во входном множестве тоже можешь посчитать, используя In, а не задавать прямо в программе...

Innuendo

Дата 7.12.2006, 22:47 (ссылка)

(нет голосов)

Загрузка ...

Опытный

Профиль
Группа: Участник
Сообщений: 745
Регистрация: 24.12.2005
Где: Молдова

Репутация: нет
Всего: 6

Zero,
С таким алгоритмом множества по 2, 3, 4 элемента не будут выводится вроде

volvo877, Да, комбинаторика... Множества это что-то типа сочетаний. Я сам как раз и написал без множеств SET.
Но это задание в учебнике было: есть множество M:=['A','B','C','D'] и надо вывести все подмножества... Типа надо работать именно с сетом, а не с массивами, константами и т.д.

--------------------

Kuvaldis

Дата 8.12.2006, 03:15 (ссылка)

(нет голосов)

Загрузка ...

механик-вредитель

Профиль
Группа: Участник Клуба
Сообщений: 1189
Регистрация: 16.6.2006
Где: Минск

Репутация: нет
Всего: 61

volvo877,
Это быстрый в написании вариант, но, к сожалению, медленно работающий. (хотя автор и не уточнял про скорость) smile

Множество представлено вектором наличия. При получении следующего множества нужно стремиться, чтобы оно отличалось от предыдущего как можно меньше, в идеале, в одном месте.
Эта проблема генерации решена так

Код


Коды Грея    
...    
Этот алгоритм позволяет перебирать все наборы Bm так, чтобы каждый следующий набор    
отличался от предыдущего только в одном разряде. Построенная с помощью этого    
алгоритма последовательность наборов называется кодом Грея. Вообще, n-разрядный код    
Грея — это упорядоченная (возможно, циклическая) последовательность, состоящая из    
 2n n-разрядных кодовых слов, каждое из которых отличается от соседнего в одном разряде.    
Будем рассматривать бинарные коды Грея порядка n. Итак, на вход алгоритма подается    
единственное число n, которое указывает порядок кода Грея. По ходу выполнения    
алгоритма мы получим последовательность всех подмножеств n-элементного множества,    
в которой каждое последующее подмножество получается из предыдущего добавлением    
или удалением единственного элемента (наименьшим возможным изменением) — код Грея.    
При этом каждое подмножество будет представляться бинарной последовательностью    
B[1], …, B[n].    
Gray-Generation(n)    
 1  for i := 1 to n do B[i] := 0;    
 2  i := 0;    
 3  repeat    
 4      write (B[i], …, B[n]);    
 5      i := i + 1; p := 1; j := i;    
 6      while j mod 2 = 0 do    
 7          begin    
 8              j := j/2; p := p + 1;  // количество 2 в разложении числа на прост. множители + 1    
 9          end;    
10      if p ≤ n then B[p] := 1 − B[p];    
11  until p > n

Обоснование можно точно посмотреть в книге Новиков "Дискретная математика для программистов".
Да и в Сети думаю, оно есть....

--------------------

Помни - когда ты спишь, враг не дремлет
Спи чаще и дольше, изматывай врага бессоницей

volvo877

Дата 8.12.2006, 20:41 (ссылка)

(нет голосов)

Загрузка ...

Эксперт

Профиль
Группа: Комодератор
Сообщений: 2073
Регистрация: 15.11.2004

Репутация: 2
Всего: 116

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

Автору, как выяснилось, это не подходит...

Innuendo

Дата 9.12.2006, 19:46 (ссылка)

(нет голосов)

Загрузка ...

Опытный

Профиль
Группа: Участник
Сообщений: 745
Регистрация: 24.12.2005
Где: Молдова

Репутация: нет
Всего: 6

volvo877, а вообще реально это как-то делать с множествами? с множествами не так много операций можно делать... вызов элемента по индексу. Задачку не мне задали, это меня попросили. Я им дал вариант с массив и константой стринговой 'ABCD' из которой вынимались элементы, а с множествами не наю =)

Но уже ладно, задание уже не нужно (хотя всё равно интересно, можно ли такое сделать, и если нельзя то почему это задание в конце темы Set и в условии дан set =) )

--------------------

1 Пользователей читают эту тему (1 Гостей и 0 Скрытых Пользователей)
0 Пользователей:
« Предыдущая тема \| Object Pascal: кроссплатформенные технологии \| Следующая тема »