0

I've searched now for more than two days around the web for any working solution. But maybe I just need the right "word" to google for. Let me explain, what I want. Just found lot of articles of combinations and permutations, but they're not covering my requirements (or I don't understand how to do this).

Let's assume, that I'll have a list of numbers: [1, 2, 3]

Now, I want all possible combinations of them. I need that kind of result (for the given example):

1 2 3
1 2+3
1+2+3
2 1+3
3 1+2

Those are all available combinations (hope so). I don't need repetition, so 1 2+3 is the same as 1 3+2.

Is there any Math genius who may help me with it? Is there any formula I can calculate the result count?

Trying to solve it in PHP but it oftens end in endless recursive executions and a memory limit exception.

Sascha
  • 3
  • 1

2 Answers2

0

You want to generate set partitions. There is Bell number of such partitions (1,2,5,15,52...).

It is not hard (arbitrary example) to generate partitions recursively (adding n to every part of list of (n-1) partition and to separate part).

But there exist effective iterative ways. For example, the next Delphi code implements this article (Efficient Generation of Set Partitions. Michael Orlov) approach. (PartitionToString is quite ineffective quick-made routine)

Output

1/2/3/4/
1/2/3,4/
1/2,4/3/
1,4/2/3/
1/2,3/4/
1/2,3,4/
1,4/2,3/
1,3/2/4/
1,3/2,4/
1,3,4/2/
1,2/3/4/
1,2/3,4/
1,2,4/3/
1,2,3/4/
1,2,3,4/

  procedure GeneratePlusCombs(n: Integer; List: TStrings);
  var
    K, M: array of Integer;
    i, j: Integer;

    function Prev: Boolean;
    var
       i, j: Integer;
    begin
    Result  := False;
    for i := n - 1 downto 1 do

      if K[i] > K[0] then begin
        K[i] := K[i] - 1;
        M[i] := M[i - 1];
        for j := i + 1 to n - 1 do begin
          M[j] := M[i] + j - i;
          K[j] := M[j];
        end;
        Exit(True);
      end;
    end;

    function PartitionToString: string;
    var
      j, cnt, d: Integer;
      s: string;
    begin
      s := '';
      for j := 0 to n - 1 do begin
        cnt := 0;
        for d := 0 to n - 1 do
          if K[d] = j then begin  ///digit d belongs to j-th part of current partition
            s := s + Format('%d,', [d + 1]);
            cnt := cnt + 1;
          end;
        if cnt > 0 then
          s[Length(s)] := '/';
      end;
      Result := s;

    end;

  begin
    SetLength(K, n);
    SetLength(M, n);

    for i := 0 to n - 1 do begin
      K[i] := i;
      M[i] := i;
    end;

    List.Add(PartitionToString);
    while Prev do
      List.Add(PartitionToString);

  end;
MBo
  • 77,366
  • 5
  • 53
  • 86
  • Thanks for that. That helped me a lot, especially the keywords "set variation". I did not success converting the given delphi code to PHP, but I found a python script, which does something similar. If anyone is interested, have a look in here: https://stackoverflow.com/questions/19368375/set-partitions-in-python – Sascha Nov 14 '17 at 08:14
0

As already mentioned in the comment above, I found a solution for this problem.

A helpful (Python) script is posted in here: Set partitions in Python

For those, who need it in PHP, in here my conversion:

// recursive function
function partition($collection) {
    if (count($collection) == 1) {
        yield array($collection);
        return;
    }

    $first = $collection[0];

    foreach (partition(array_slice($collection, 1)) as $smaller) {
      foreach ($smaller as $n => $subset) {
        yield array_merge(
            array_slice($smaller, 0, $n),
            array(array_merge(array($first), $subset)),
            array_slice($smaller, $n + 1)
        );
      }

      yield array_merge(array(array($first)), $smaller);
    }
}

// set up an array
$something = array(1, 2, 3, 4);

// loop all the variants
foreach (partition($something) as $n => $p) {
    var_dump($p);
}
Sascha
  • 3
  • 1