Разложение числа на повторяющиеся слагаемые

Question

Помогите, пожалуйста, разложить число на всевозможные комбинации из чисел 2 и 3 с повторениями, вот набросок для простого разбиения без повторений.

program Razbieniya;
    type Razb=array [byte] of byte;
    var N,i,L:byte;
    X:Razb;
    procedure Next(var X:Razb;var L:byte);
      var i,j:byte;
      s:word;
    begin
      i:=L-1;s:=X[L];
      {поиск i}
      while (i>1)and(X[i-1]<=X[i]) do begin s:=s+X[i];dec(i) end;
      inc(X[i]);
      L:=i+s-1;
      for j:=i+1 to L do X[j]:=1
    end;
  begin
    write('N=');readln(N);
    L:=N; for i:=1 to L do X[i]:=1;
    for i:=1 to L do write(X[i]);writeln;
    repeat
      Next(X,L);
      for i:=1 to L do write(X[i]);writeln
    until L=1
  end.

Answer 1

Задача эквивалентна генерации всех битовых слов длиной K, где количество установленных битов равно N (комбинаций N троек и K-N двоек). Поэтому можно использовать алгоритмы генерации сочетаний, в том числе алгоритм next_permutation. В данном случае я использовал битовую арифметику.

function nextwithsameonebits(n: Integer): Integer;
var
  rightbit, nextbit, rightseries: Integer;
begin
  rightbit := n and (-n);
  nextbit := n + rightbit;
  rightseries := n xor nextbit;
  rightseries := (rightseries div rightbit) shr 2;
  Result := nextbit or rightseries;
end;

var
  summ, len, threes, twos, n, nend, t, i: integer;
  s: string;
begin
  summ := 12;
  threes := summ and 1;
  while threes * 3 <= summ do begin
    if threes = 0 then
      Memo1.Lines.Add(StringOfChar('2',summ div 2))
    else begin
      twos := (summ - threes * 3) div 2;
      len := twos + threes;
      SetLength(s, len);
      n := (1 shl threes) - 1;
      nend := n shl twos;
      while n <= nend do begin //перечисляем все слова с three единичными битами
        t := n;
        for i := len downto 1 do begin
          s[i] := Chr(Ord('2') + (t and 1));
          t := t shr 1;
        end;
        Memo1.Lines.Add(s);
        n := nextwithsameonebits(n);
      end;

    end;
    Inc(threes, 2);
  end;

222222
22233
22323
22332
23223
23232
23322
32223
32232
32322
33222
3333

Как работает получение следующей комбинации единиц:
(похожее, прямо оно)

10011100   n
    rightbit := n and (-n);
00000100  выделили самый правый единичный
    nextbit := n + rightbit;
10100000   включили вспомогательный бит левее правой серии единиц 
    rightseries := n xor nextbit;
00111100   выделена правая серия и бит левее
    rightseries := (rightseries div rightbit) shr 2;
00000011   серия сдвинута вправо так, что пропали два бита
 (как бы укоротили правую серию, величина сдвига известна благодаря rightbit)
  Result := nextbit or rightseries;
10100011  скомбинировали старшие биты, которые были установлены левее    правой серии, 
           вспомогательный бит левее её, и подрезанную серию, сдвинутую вправо

Теперь использование: нужно получить summ. Количество троек threes зависит от чётности summ и пробегает с шагом два ряды 0,2,4,6.. или 1,3,5... Количество двоек twos вычисляется из остатка, про длину len понятно.

Начальная комбинация состоит из twos нулей в начале и threes младших единичных битов - например, для threes=3 2^3 - 1 = 0001000 - 1 = 0000111.

Далее перебираем слова с таким количеством битов, пока не дойдём до последней комбинации nend 1110000. А во внутреннем цикле проверяем биты слова, начиная с младшего, устанавливая соответственно символы 2 или 3 в строке.

БЛОГ НА HUSL

Разложение числа на повторяющиеся слагаемые

Ответы (1 шт):