генерация всех k-элементных подмножеств множества из n элементов Опции

[demidrolll]

Помогите хотя бы разработать алгоритм. Вот задача:
Разработать программу, которая генерирует все k-элементные подмножества множества из n элементов таким образом, что каждое последующее подмножество образуется из предыдущего удалением одного элемента и добавлением другого.

[klem4]

Пример чтоли приведите ...

123
132
213
231
312
321

?

[amega]

1 2 3
1 3 2

эт скорей всего 1 и тоже множество может так
1 2 3
1 2 4
...

[demidrolll]

Sorry , нужно было сразу пояснить

Например, если 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]

Так ?

Код

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]

тогда будет (это в лексикографическом порядке, но мне он не важен)
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

Сообщение отредактировано: klem4 - 12.03.2009 7:43

[demidrolll]

Большое спасибо