Алгоритм перебора комбинаций (нужна помощь)

[Rakshas]

Задача стоит такая: необходимо выбрать все двоичные комбинации заданной длины с заданным весом.
Например:
длина задана 7, т.е. 0000000
вес - 3
надо выбрать комбинации

Код: Выделить всё

0000111
0001011
0001101
0001110
0010011
...

Пока реализовал это перебором всех комбинаций заданной длины, и подсчетом веса каждой комбинации.

Подскажите, есть ли другой, более быстрый, алгоритм.

[Vadim]

Rakshas
А если не перебирать всю длину, а создавать заданный вес в этой длине? Например сдвигом сначала одной единички, потом двух, потом всех трёх...

[Putnick]

Уважаемый Rakshas,
Поддерживаю Вадима

А если не перебирать всю длину, а создавать заданный вес в этой длине? Например сдвигом сначала одной единички, потом двух, потом всех трёх

и всё это — рекурсивно. Например, так:

Код: Выделить всё

program p9;
var
  Dlina, Ves:Integer;
procedure GenStr(s:string; dl, v:integer);
var
  i, j:integer;
  s1:string;
begin
  if V>dl then begin
    WriteLn('Вес не может быть больше длины');
    exit
  end;
  for i:=1 to dl-v+1 do begin
    s1:='';
    for j:=1 to i-1 do s1:=s1+'0';
    s1:=s1+'1';
    if V=1 then begin
      for j:=i+1 to dl do s1:=s1+'0';
      WriteLn(s+s1);
    end else GenStr(s+s1, dl-i, v-1)
  end;
end;
begin
  Write('Укажите длину двоичной последовательности: ');
  ReadLn(Dlina);
  Write('Укажите вес двоичной последовательности: ');
  ReadLn(Ves);
  GenStr('',Dlina,Ves)
end.

С уважением, Алексей.

[Rakshas]

Алексей, Вадим.
Спасибо вам огромное.

Попробую модифицировать Ваш код для применения в своей программе.

С уважением, Сергей.

[Timid]

Этот метод будет очень медленным при большой длине числа.

Если длина не превышает 64, то лучше использовать числовое преобразование. Тип cardinal - целое без знака.

Код: Выделить всё

var
  l,s:string;
  n,m,r,k,i,sm:cardinal;
begin
  readln(l,s); // ввод   длина,вес
  n:=strtoint(l);
  m:=Math.IntPower(2,n)-1; // теперь в m - максимальное число в двоичном представлении, вроде 1111111 для 7
  r:=strtoint(s);
  k:=Math.IntPower(2,r)-1; // теперь в k - минимальное число в двоичном представлении, вроде 111 для 3;  
  for i:=k to m do begin
     sm:=0;
     // можно сделать цикл, но будет работать медленно, поэтому лучше "ручками" прописать 64 раза
     sm:=sm+(i and 1); // накладываем маску на i, узнаем, есть ли бит в последней позиции
     sm:=sm+((i shr 1) and 1); // сдвигаем вправо и накладываем маску - проверяем второй бит (справа)
     sm:=sm+((i shr 2) and 2); // проверяем третий бит
     .... // <-- здесь продолжаем проверки по образцу выше
     if (sm=r) then begin // <-- вес подходит
       writeln(IntToBin(i,r)); // <-- функция inttobin выводит целое i как двоичное число с r разрядами, погугли Delphi+IntToBin
     end;
  end;