IPB
ЛогинПароль:

> Прочтите прежде чем задавать вопрос!

1. Заголовок темы должен быть информативным. В противном случае тема удаляется ...
2. Все тексты программ должны помещаться в теги [code=pas] ... [/code], либо быть опубликованы на нашем PasteBin в режиме вечного хранения.
3. Прежде чем задавать вопрос, см. "FAQ", если там не нашли ответа, воспользуйтесь ПОИСКОМ, возможно такую задачу уже решали!
4. Не предлагайте свои решения на других языках, кроме Паскаля (исключение - только с согласия модератора).
5. НЕ используйте форум для личного общения, все что не относится к обсуждению темы - на PM!
6. Одна тема - один вопрос (задача)
7. Проверяйте программы перед тем, как разместить их на форуме!!!
8. Спрашивайте и отвечайте четко и по существу!!!

 
 Ответить  Открыть новую тему 
> генерация всех k-элементных подмножеств множества из n элементов
сообщение
Сообщение #1





Группа: Пользователи
Сообщений: 4
Пол: Мужской

Репутация: -  0  +


Помогите хотя бы разработать алгоритм. Вот задача:
Разработать программу, которая генерирует все k-элементные подмножества множества из n элементов таким образом, что каждое последующее подмножество образуется из предыдущего удалением одного элемента и добавлением другого.
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #2


Perl. Just code it!
******

Группа: Пользователи
Сообщений: 4 100
Пол: Мужской
Реальное имя: Андрей

Репутация: -  44  +


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

123
132
213
231
312
321

?


--------------------
perl -e 'print for (map{chr(hex)}("4861707079204E6577205965617221"=~/(.{2})/g)), "\n";'
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #3


?
***

Группа: Пользователи
Сообщений: 283
Пол: Мужской

Репутация: -  4  +


Цитата
1 2 3
1 3 2

эт скорей всего 1 и тоже множество может так
1 2 3
1 2 4
...
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #4





Группа: Пользователи
Сообщений: 4
Пол: Мужской

Репутация: -  0  +


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) , а такое уже есть.

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



 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #5


Perl. Just code it!
******

Группа: Пользователи
Сообщений: 4 100
Пол: Мужской
Реальное имя: Андрей

Репутация: -  44  +


Так ?

{$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


--------------------
perl -e 'print for (map{chr(hex)}("4861707079204E6577205965617221"=~/(.{2})/g)), "\n";'
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #6


Злостный любитель
*****

Группа: Пользователи
Сообщений: 1 755
Пол: Мужской

Репутация: -  62  +


Цитата(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


нет


--------------------
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #7


Perl. Just code it!
******

Группа: Пользователи
Сообщений: 4 100
Пол: Мужской
Реальное имя: Андрей

Репутация: -  44  +


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


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


--------------------
perl -e 'print for (map{chr(hex)}("4861707079204E6577205965617221"=~/(.{2})/g)), "\n";'
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #8





Группа: Пользователи
Сообщений: 4
Пол: Мужской

Репутация: -  0  +


Большое спасибо
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 

 Ответить  Открыть новую тему 
1 чел. читают эту тему (гостей: 1, скрытых пользователей: 0)
Пользователей: 0

 





- Текстовая версия 22.10.2020 19:32
500Gb HDD, 6Gb RAM, 2 Cores, 7 EUR в месяц — такие хостинги правда бывают
Связь с администрацией: bu_gen в домене octagram.name