| Новости | Поиск | FAQ | Статьи | Книги | Новости VCL | | Форумы ЧАТ | Орешник | KOL и MCK |
Форумы -» Основная («Начинающим»)/ Базы / WinAPI / Компоненты / Сети / Media / Игры / Corba и COM / KOL / FreePascal / .Net / Прочее / RSDN.ORG

	« предыдущая ветвь | форум | следующая ветвь »

Вывод всех перестановок k элементов из множества N имеющихся [D7]

Страницы:   < 1 2 3 >

ННН ©   (2012-10-28 23:00:00) 

Всем привет нужен алгоритм (любой на словах или кодом) выводящий все перестановки k элементов (не повторяющихся) из множества N имеющихся.
т.е. Пусть N=6, {1,2,3,4,5,6}, k=4
1 2 3 4
1 2 3 5
1 2 3 6
1 2 4 5
1 2 4 6
1 2 5 6
1 3 4 5
и т.д.

---

ННН   (2012-10-29 00:23:00) [41]

Program perms;
var
 i, j, h, n, k: integer;
 a:array[0 .. 100] of integer;  { массив для хранения перестановки }

{процедура вывода полученной перестановки}
procedure output;
var i: integer;
begin
 writeln;
 for i:=1 to n do write(a[i],' ');
end;

begin
 write('количество элементов перестановки: '); readln(n);
 fillchar(a, sizeof(a), 0);

 { ввод элементов начальной перестановки }
 for i:=1 to n do a[i]:=i;

 repeat
   output;  { вывод текущей перестановки }
   i:=n;
   while a[i-1]>a[i] do dec(i); { поиск скачка }
   j:=i-1;
   h:=a[j];
   while a[i+1]>h do inc(i); { поиск первого меньшего элемента }
   a[j]:=a[i];  a[i]:=h;
   i:=j+1; k:=n;
   while i<k do begin { перестановка ”хвоста” }
      h:=a[i]; a[i]:=a[k]; a[k]:=h;
      inc(i); dec(k)              
   end
 until j=0;
end.

а как тут реализовать ?

---

Sha   (2012-10-29 00:10:00) [42]

Псевдокод
 
 A: array of integer; //перестановки элементов [0..k-1]
 P: array of integer; //перестановки k элементов твоего множества
 C: array of array of integer; //все сочетания из n по k элементов твоего множества
......
 while NextPermutation(A) do begin;
   for i:=0 to Length(C)-1 do begin;
     for j:=0 to Length(C[0])-1 do P[j]:=C[i,A[j]];
     //Show P here
     end;
   end;


---

Sha   (2012-10-28 23:41:00) [43]

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

---

Sha   (2012-10-28 23:31:00) [44]

Если на пальцах:
в цикле генерируешь перестановки элементов abcd
и во вложенном выбираешь цифры и заменяешь ими буквы.

Ну или наоборот, если надо поменять вложенность циклов.

---

Страницы:   < 1 2 3 >

Наверх