Помощь - Поиск - Пользователи - Календарь
Полная версия: генерация всех k-элементных подмножеств множества из n элементов
Форум «Всё о Паскале» > Pascal, Object Pascal > Задачи
demidrolll
Помогите хотя бы разработать алгоритм. Вот задача:
Разработать программу, которая генерирует все k-элементные подмножества множества из n элементов таким образом, что каждое последующее подмножество образуется из предыдущего удалением одного элемента и добавлением другого.
klem4
unsure.gif Пример чтоли приведите ...

123
132
213
231
312
321

?
amega
Цитата
1 2 3
1 3 2

эт скорей всего 1 и тоже множество может так
1 2 3
1 2 4
...
demidrolll
Sorry unsure.gif , нужно было сразу пояснить

Например, если n=5 a=3

тогда будет (это в лексикографическом порядке, но мне он не важен)

1 2 3
1 2 4
1 2 5
1 3 4
1 3 5
1 4 5
2 3 4
2 3 5
2 4 5
3 4 5

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

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

(4,5) (1,2,3)

Затем меняем 1 на 4 и 4 на 1 и получаем

(1,5) (4,2,3)

Затем 1 на 2 и 2 на 1

(2,5) (4,1,3)

Затем 3 на 2 и 2 на 3 и т.д.

(3,5) (4,1,2)

В результате получились подмножества

1 2 3
4 2 3
4 1 3
4 1 2 и т.д

Все бы хорошо, но в предпоследнем множестве получается

(4,2) (5,1,3) ==> если я меняю 4 на 5 и 5 на 4 то получается (5,2) (4,1,3) , а такое уже есть.

Может быть я думаю не в правильном направлении?



klem4
Так ?

{$mode tp}
{$r-}
uses crt;
type
plist = ^list;
list = array [1..1] of integer;

procedure dump( const p: plist; const n: integer );
var i: integer;
begin for i := 1 to n do write(p^[i], ' '); writeln end;

function posmax( const ps, size, max: integer): integer;
begin posmax := max - size + ps end;

function next( var u: plist; const size, max: integer ): boolean;
var
i, j, max_: integer;
flag: boolean;
begin
i := size;
repeat
while (i > 0) and (u^[i] = posmax(i, size, max)) do dec(i);
if i > 0 then begin
inc(u^[i]);
for j := i + 1 to size do u^[j] := u^[j - 1] + 1;
flag := true
end
until (i = 0) or flag;
next := flag and (i > 0)
end;

var
size, max, i: integer;
lst: plist;
begin
{ readln(size, max); }
size := 3;
max := 5;
getmem(lst, size * sizeof(list));
for i := 1 to size do lst^[i] := i;
repeat dump(lst, size) until not next( lst, size, max );
freemem(lst, size * sizeof(list))
end.


Код

1 2 3
1 2 4
1 2 5
1 3 4
1 3 5
1 4 5
2 3 4
2 3 5
2 4 5
3 4 5
TarasBer
Цитата(klem4 @ 11.03.2009 23:58) *

Так ?
Код

1 2 3
1 2 4
1 2 5
1 3 4
1 3 5
[b]1 4 5
2 3 4[/b]
2 3 5
2 4 5
3 4 5


нет
klem4
dry.gif
Цитата(автор)
тогда будет (это в лексикографическом порядке, но мне он не важен)
1 2 3
1 2 4
1 2 5
1 3 4
1 3 5
1 4 5
2 3 4

2 3 5
2 4 5
3 4 5
demidrolll
Большое спасибо
Это текстовая версия — только основной контент. Для просмотра полной версии этой страницы, пожалуйста, нажмите сюда.