Перебор подмножеств и перестановок

{ X4 }
// (0010) -> { X3 }
// (0011) ->

{ X3 X4}
// (0100) -> { X2 }
// (0101) -> { X2 X4 }
// (0110) -> { X2 X3 }
// (0111) -> { X2 X3 X4
// (1000) -> { X1 }
// (1001) -> { X1 X4 }
// (1010) -> { X1 X3 }
// (1011) -> { X1 X3 X4}
// (1100) -> { X1 X2 }
// (1101) -> { X1 X2 X4 }
// (1110) -> { X1 X2 X3 }
// (1111) -> { X1 X2 X3 X4

cin >> n;
do {
// печать множества

cout << '(';
for (i=0; i cout << p[i] << ' ';
cout << ' ) -> { ';
for (i=1; i<=n; i++)
if (p[i-1]) cout <<‘X’ << i << ' ';
cout << '}\n';

// переход к след. подмнож-ву
j=n-1;
while (p[j] && j>0) {
p[j]=0;
j--;
}
if (j) \\ новый элемент
p[j]=1;
}
while (j>0);
}

v3 …
Максимальная возможная загрузка ранца Т.
Описание переменных
var
x, {массив индексов

для перебора подмножеств}
max,{массив для максимума}
v:array[0..10] of integer;{массив весов}
max_v, {максимальный вес найденной загрузки}
n,j,i,t:integer;{t – предел ранца}

for i:=1 to n do write(x[i],' ');
s:=0;

write(') <-> { ');
for i:=1 to n do begin
if x[i]=1 then write('X[',i,'](',v[i],') ');
s+=v[i]*x[i];
end;
if s<=t then begin
writeln('}=',s,' +');
if s>max_v then begin // фиксация максимального подмножества
max_v:=s;
max:=x
end
end
else writeln('} – недопустимая загрузка')
end;

read(v[i]); // вес i-го товара
x[i]:=0

// первое множество пустое
end;
max:=x; max_v:=0; // параметры пустого множества
repeat
print;
j:=n;
while (x[j]=1) and (j>0) do begin
x[j]:=0;
j-=1
end;
if j>0 then begin x[j]:=1
until j=0;
// печать варианта максимальной загрузки
writeln('MAX');
x:=max;
print
end.

 1e-8
2^20=1048576  4.9e-7
2^25=33554432  2e-5
2^30=1e9  7.5e-4 – секунда!
2^35=34e9

 0.028
2^40=101e10  1.02 – день!
2^45=35e12  36.8
2^50=1.1e15  1309

 (X1,X2,X4,X3)
// (1,3,2,4)  (X1,X3,X2,X4)
// (1,3,4,2)  (X1,X3,X4,X2)
// (1,4,2,3) 

(X1,X4,X2,X3)
// (1,4,3,2)  (X1,X4,X3,X2)
// (2,1,3,4)  (X2,X1,X3,X4)
// (2,1,4,3)  (X1,X2,X3,X4)
// (2,3,1,4)  (X2,X3,X1,X4)
// (2,3,4,1)  (X2,X3,X4,X1)
// (2,4,1,3)  (X2,X4,X1,X3)
// (2,4,3,1)  (X2,X4,X3,X1)
// (3,1,2,4)  (X3,X1,X2,X4)
// (3,1,4,2)  (X3,X1,X4,X2)
// (3,2,1,4)  (X3,X2,X1,X4)

// (3,2,4,1)  (X3,X2,X4,X1)
// (3,4,1,2)  (X3,X4,X1,X2)
// (3,4,2,1)  (X3,X4,X2,X1)
// (4,1,2,3)  (X4,X1,X2,X3)
// (4,1,3,2)  (X4,X1,X3,X2)
// (4,2,1,3)  (X4,X2,X1,X3)
// (4,2,3,1)  (X4,X2,X3,X1)
// (4,3,1,2)  (X4,X3,X1,X2)
// (4,3,2,1)  (X4,X3,X2,X1)

1) // (1, 3, 5, 7, 6, 4, 2) – поиск элементов перестановки
2) // (1, 3, 6, 7, 5, 4, 2) – перестановка элементов
3) // (1, 3, 6, 2, 4, 5, 7) – транспонирование

i, j, k, r:integer;
Function sort:boolean; // проверка упорядоченности перестановки

Var ch:boolean;
Begin
ch:=true;
for i:=1 to n do
if a[p[i]]>a[p[i+1]] then ch:=false ;
sort:=ch
End;
Procedure print; // печать упорядоченной последовательности
Begin
for i:=1 to n do
write(a[pi]],’ ‘)
End;

n do begin
a[i]:=random(100);
p[i]:=i
end;

if sort then begin print; halt end;

j:=n; // 1) (1,3,5,7,6,4,2) – поиск элементов перестановки
while (j>0) and (p[j] if j>0 then begin
k:=n;
while a[p[k]] // 2) (1,3,6,7,5,4,2) – перестановка элементов
r:=a[p[k]]; a[p[k]]:=a[p[j]]; a[p[j]]:=r;
k:=(n-j) div 2; // 3) (1,3,6,2,4,5,7) – транспонирование
while k>0 do begin
r:=a[p[k+j]]; a[p[k+j]]:=a[p[n-k+1]]; a[p[n-k+1]]:=r;
к-=1
end
end
until j=0 // условие завершения
End.

040  2e-8
8!=40 320  1.6e-7
9!=362 880  1.6e-6
10!=3 628

800  1.8e-5 – секунда!
11!=39 916 800  2e-4
12!=479 001 600  0.002
13!=6 227 020 800  0.04
14!=87 178 291 200  0.59 – пол дня!
15!=1307 674 468 000  9.4
16!=2e12  160.6
17!=36e14  2895