Hello! The second day I can not find a solution to this seemingly simple task. There is a number of cells f and a certain number of coins c . You can put only one coin in each cell, the task is to calculate the number of possible combinations (I coped with this quickly, there are formulas for this) and write all possible combinations into a text file. To make it clearer, this is how the file with combinations looks like (the case with 5 cells and 2 coins, the first line is the cell numbers):

  • 1 2 3 4 5
  • 1 1 0 0 0
  • 1 0 1 0 0
  • 1 0 0 1 0
  • 1 0 0 0 1
  • 0 1 1 0 0
  • 0 1 0 1 0
  • 0 1 0 0 1
  • 0 0 1 1 0
  • 0 0 1 0 1
  • 0 0 0 1 1

To write the whole thing into a text file, you need to build some kind of array, here I have difficulties. Tell me, please, how can you solve this problem? I tend most to the solution with recursion, but I can not figure out how to do it.

    2 answers 2

    You can take c coins (indicated by ones) and add between them ( c+1 gap, including left and right on the edge) f - c zeros to fill all f cells.

    For example, in the case of two coins and five cells, you can add zeros to three places (indicated by an asterisk * ):

     kmn *1*1*

    In each place you can add from 0 to (fc) zeros:

     <?php $Z = 5 - 2; // (f - c) == number of Zeros for ($k = 0; $k <= $Z; $k++) { for ($m = 0; $m <= ($Z-$k); $m++) { $n = $Z - $k - $m; echo str_repeat("0", $k); echo 1; echo str_repeat("0", $m); echo 1; echo str_repeat("0", $n); echo "\n"; } } ?>

    This prints exactly f!/(c! * (fc)!) Strings ( f C c ), which can be much better than filtering all possible 2 f bit strings.

    Result

     11000 10100 10010 10001 01100 01010 01001 00110 00101 00011

    In this formulation, the problem reduces to splitting (fc) numbers into (c+1) parts :

     11000 <=> 0 0 3 10100 <=> 0 1 2 10010 <=> 0 2 1 10001 <=> 0 3 0 01100 <=> 1 0 2 01010 <=> 1 1 1 01001 <=> 1 2 0 00110 <=> 2 0 1 00101 <=> 2 1 0 00011 <=> 3 0 0

    Example

     <?php function weak_compositions($nboxes, $nballs, $parent="", $nested=0) { $one = $nested ? "1" : ""; if ($nboxes > 1) { for ($i = 0; $i <= $nballs; $i++) { weak_compositions($nboxes - 1, $i, $parent . $one . str_repeat("0", $nballs - $i), 1); } } else { echo $parent . $one . str_repeat("0", $nballs) . "\n"; } } $f=5; $c=2; weak_compositions($c+1, $f-$c); ?>

      I will describe the algorithm, perhaps not perfect, but working.

      1) We start a cycle with a counter from 0 to c ^ f, in your case from 0 to 32.

      2) At each iteration, we convert the counter into the c-th system, getting in your case all the numbers from 00000 to 11111. These will be all possible variants of the presence of coins in the cells.

      3) Since in your case, there are only 2 coins, then at each iteration the “bad” options should be discarded, i.e. where the sum of the cells with coins is not equal to 2. The "good" options to save.