It is required to go through all combinations of a group of characters from A to X where X can be any other letter.

Example: the ABCD sequence is given, the function should output AB, AC, AD, BC, BD, CD, ABC, BCD, CDA, ABD (like I forgot nothing), i.e. the position of the symbol in the group is not important - only the uniqueness of the group itself is important.

Google in the direction of placements and combinations. But I did not understand what exactly this is required of me. Sinner - did not learn mathematics. Clever people, explain on fingers or a code, I will be grateful.

Update: Usually they say - and the year has not passed. But I just passed. It took again, this time it went over in detail - here is the PHP code:

function gen_comb ($rest, $current = "", $container = []) { // Если пустой Ρ‚Π΅ΠΊΡƒΡ‰ΠΈΠΉ ΠΈ Π΅ΡΡ‚ΡŒ остаток if(!$current and $rest) { // Π’Π΅ΠΊΡƒΡ‰Π΅ΠΌΡƒ Π΄Π°Π΅ΠΌ ΠΏΠ΅Ρ€Π²Ρ‹ΠΉ символ остатка $current = substr($rest, 0, 1); // ΠŸΠΎΡ‚ΠΎΠΌ для ΠΊΠ°ΠΆΠ΄ΠΎΠ³ΠΎ Π² остаткС for($i=strlen($rest); $i > 0; $i--) // Ρ„ΠΎΡ€ΠΌΠΈΡ€ΡƒΠ΅ΠΌ ΠΏΠ°Ρ€Ρƒ с Ρ‚Π΅ΠΊΡƒΡ‰ΠΈΠΌ ΠΈ записываСм Π² Π²Ρ‹Π²ΠΎΠ΄ $container[] = $current . substr($rest, $i, strlen($rest)); // ΠΏΡ€ΠΈ этом провСряСм - Ссли Π² остаткС ΠΎΠ΄ΠΈΠ½ if(strlen($rest) == 1 and $current) // Π²ΠΎΠ·Π²Ρ€Π°Ρ‰Π°Π΅ΠΌ Ρ€Π΅Π·ΡƒΠ»ΡŒΡ‚Π°Ρ‚ return $container; // Ссли Π² остаткС большС ΠΎΠ΄Π½ΠΎΠ³ΠΎ ΠΈ ΠΏΡ€ΠΈ Π²Ρ‹Ρ‡Π΅Ρ‚Π΅ Π΅Ρ‰Π΅ останСтся if(strlen($rest) - 1) // Π²ΠΎΠ·Π²Ρ€Π°Ρ‰Π°Π΅ΠΌ рСкурсивный Ρ€Π΅Π·ΡƒΠ»ΡŒΡ‚Π°Ρ‚ с ΡƒΠΌΠ΅Π½ΡŒΡˆΠ΅Π½Π½Ρ‹ΠΌ Π½Π° 1 остатком return gen_comb(substr($rest, 1, strlen($rest)), "", $container); } }
  • forgot the band - BD - Igor
  • I don’t know how in Russian, but in English the stack of questions about the combination simply unmeasured, look through it, you’ll definitely find it - splash58
  • @AlexShawnee In general, you have forgotten a lot or made a mistake with CDA. If you have the letter A at the end, i.e. the letters do not always increase, then you should have plenty of any DA DA CA DBA DAB DAC, etc. - Mike
  • And single A, B, C, D? Do not be offended? - LEQADA
  • @Mike, it seems to me that the author needs a combination, not a placement. Well, yes, there must be ACD, not CDA. - LEQADA

2 answers 2

Foreword

I love the following algorithm because of its childlike simplicity. He does not claim to be the fastest algorithm, but is the easiest to understand from all that I have met.

Algorithm

If one takes into account single combinations (A, B, C, D), then there are only 2 n - 1 such combinations, where n is the number of characters in the source string.

Suppose we have a string of n characters. That is, we have n positions in a row.

 ABCDEFGH ... n-1 n // ^ ^ ^ ^ ^ ^ ^ ^ ... ^ ^ 1 2 3 4 5 6 7 8 ... n-1 n // порядковый Π½ΠΎΠΌΠ΅Ρ€ ΠΊΠ°ΠΆΠ΄ΠΎΠΉ ΠΏΠΎΠ·ΠΈΡ†ΠΈΠΈ

Consider each position zero (0) or one (1). We agree to put 1 on the position in which we want to see the symbol, and 0 on the position on which we do not want.

The result is approximately the next line of n zeros and ones.

 0 1 0 0 1 0 0 0 ... 0 0 // получСнная закодированная строка ^ ^ ^ ^ ^ ^ ^ ^ ... ^ ^ 1 2 3 4 5 6 7 8 ... n-1 n // порядковый Π½ΠΎΠΌΠ΅Ρ€ ΠΊΠ°ΠΆΠ΄ΠΎΠΉ ΠΏΠΎΠ·ΠΈΡ†ΠΈΠΈ

This string encodes a combination.

 _ B _ _ E _ _ _ ... _ _ // комбинация строка ^ ^ ^ ^ ^ ^ ^ ^ ... ^ ^ 1 2 3 4 5 6 7 8 ... n-1 n // порядковый Π½ΠΎΠΌΠ΅Ρ€ ΠΊΠ°ΠΆΠ΄ΠΎΠΉ ΠΏΠΎΠ·ΠΈΡ†ΠΈΠΈ

And now let's write down the binary set with a length of n elements.

 0 0 0 0 0 0 0 0 ... 0 0|_ _ _ _ _ _ _ _ ... _ _ 0 0 0 0 0 0 0 0 ... 0 1|_ _ _ _ _ _ _ _ ... _ n 0 0 0 0 0 0 0 0 ... 1 0|_ _ _ _ _ _ _ _ ... n-1 _ 0 0 0 0 0 0 0 0 ... 1 1|_ _ _ _ _ _ _ _ ... n-1 n .......................|......................... 1 1 1 1 1 1 1 1 ... 1 0|ABCDEFGH ... n-1 _ 1 1 1 1 1 1 1 1 ... 1 1|ABCDEFGH ... n-1 n

This set is written out quite simply. If it is simple, then on each new line one is added to the last element. And if the result is a number greater than one, then the position is reset and the unit is added to the adjacent left position, etc.

This set (without the first) will describe all possible combinations of the source string.

Example

Take the line ABCD. It has 4 characters, which means we will have 2 4 - 1 = 15 combinations.

We write the binary set of 4 elements

 0 0 0 0|_ _ _ _ 0 0 0 1|_ _ _ D 0 0 1 0|_ _ C _ 0 0 1 1|_ _ CD 0 1 0 0|_ B _ _ 0 1 0 1|_ B _ D 0 1 1 0|_ BC _ 0 1 1 1|_ BCD 1 0 0 0|A _ _ _ 1 0 0 1|A _ _ D 1 0 1 0|A _ C _ 1 0 1 1|A _ CD 1 1 0 0|AB _ _ 1 1 0 1|AB _ D 1 1 1 0|ABC _ 1 1 1 1|ABCD

And we get the following options

 1) D 2) C 3) CD 4) B 5) BD 6) BC 7) BCD 8) A 9) AD 10) AC 11) ACD 12) AB 13) ABD 14) ABC 15) ABCD

If you do not need single combinations, you can throw them away :)

    For starters - about the terms.
    Take for example New Year's gifts. which N pieces in the bag.
    Permutations - when these gifts are laid out on N shelves (order is important).
    Options: N! .
    Placements - when they are trying to decompose into M shelves (not all fall, order is important).
    Options: N! / M! N! / M! .
    Combinations - when they are trying to shift to another bag (order is not important), which includes only M pieces.
    Options: N! / (M!(Nm)!) N! / (M!(Nm)!) = C N M.

    Judging by the formulation of the problem (the order is unimportant), we are talking about combinations, and you may need either all of them (M = 1...N) or a range of 2-3 elements.

    A software function is implemented that can be called with a different number of parameters. If the input is only an array of characters, the output is all possible combinations. But you can also specify M (one additional parameter) or range M (parameters from, to ).

    PHP program:

     function placing($chars, $from=0, $to = 0){ $cnt = count($chars); if(($from == 0) && ($to == 0)){ $from = 1; $to = $cnt; } if($from == 0) $from = 1; if($to == 0) $to = $from; if($from < $to){ $plac = []; for($num = $from; $num <= $to; $num++){ $plac = array_merge($plac, placing(["A","B","C","D"], $num)); } }else{ $plac = [""]; for($n = 0; $n < $from; $n++){ $plac_old = $plac; $plac = []; foreach($plac_old as $item){ $last = strlen($item)-1; for($m = $n; $m < $cnt; $m++){ if($chars[$m] > $item[$last]){ $plac[] = $item.$chars[$m]; } } } } } return $plac; } $plac = placing(["A","B","C","D"]); var_dump($plac); $plac = placing(["A","B","C","D"],2); var_dump($plac); $plac = placing(["A","B","C","D"],2,3); var_dump($plac);

    Results:

     array (size = 15)
   0 => string 'A' (length = 1)
   1 => string 'B' (length = 1)
   2 => string 'C' (length = 1)
   3 => string 'D' (length = 1)
   4 => string 'AB' (length = 2)
   5 => string 'AC' (length = 2)
   6 => string 'AD' (length = 2)
   7 => string 'BC' (length = 2)
   8 => string 'BD' (length = 2)
   9 => string 'CD' (length = 2)
   10 => string 'ABC' (length = 3)
   11 => string 'ABD' (length = 3)
   12 => string 'ACD' (length = 3)
   13 => string 'BCD' (length = 3)
   14 => string 'ABCD' (length = 4)
 array (size = 6)
   0 => string 'AB' (length = 2)
   1 => string 'AC' (length = 2)
   2 => string 'AD' (length = 2)
   3 => string 'BC' (length = 2)
   4 => string 'BD' (length = 2)
   5 => string 'CD' (length = 2)
 array (size = 10)
   0 => string 'AB' (length = 2)
   1 => string 'AC' (length = 2)
   2 => string 'AD' (length = 2)
   3 => string 'BC' (length = 2)
   4 => string 'BD' (length = 2)
   5 => string 'CD' (length = 2)
   6 => string 'ABC' (length = 3)
   7 => string 'ABD' (length = 3)
   8 => string 'ACD' (length = 3)
   9 => string 'BCD' (length = 3)

    Note that, in accordance with the Newton's binomial formula, the total number of all permutations symbolizes the number (1 + 1) N. With N = 4, this is 16, but the program in the first variant yields 15. In order for the balance to converge, you need to add an empty line to the permutations.