demonic demonic - 3 months ago 13
PHP Question

How to generate unique, non repeating combinations of letters from a given string in PHP

I read through about 15 other resources and answers related to this subject on Stackoverflow, and only found one code that was close to what I wanted, but I don't know how to refine its generation further.

This is what I have so far:


$combos = array_unique($letters);
$lastres = $letters;
for ($i = 1; $i < count($letters); $i++) {
$newres = array();
foreach ($lastres as $r) {
foreach ($letters as $let) {
$new = $r . $let;
if (!in_array($new, $newres)) {
$newres[] = $new;
// Action
$combos[] = $new;
}
}
}
$lastres = $newres;
}
print_r($combos);
?>


The above code generates 1365 results from the input "apple", but it includes unwanted results.

I will paste here the first 86 results:

[0] => a [1] => p [3] => l [4] => e [5] => aa [6] => ap [7] => al [8] => ae [9] => pa [10] => pp [11] => pl [12] => pe [13] => la [14] => lp [15] => ll [16] => le [17] => ea [18] => ep [19] => el [20] => ee [21] => aaa [22] => aap [23] => aal [24] => aae [25] => apa [26] => app [27] => apl [28] => ape [29] => ala [30] => alp [31] => all [32] => ale [33] => aea [34] => aep [35] => ael [36] => aee [37] => paa [38] => pap [39] => pal [40] => pae [41] => ppa [42] => ppp [43] => ppl [44] => ppe [45] => pla [46] => plp [47] => pll [48] => ple [49] => pea [50] => pep [51] => pel [52] => pee [53] => laa [54] => lap [55] => lal [56] => lae [57] => lpa [58] => lpp [59] => lpl [60] => lpe [61] => lla [62] => llp [63] => lll [64] => lle [65] => lea [66] => lep [67] => lel [68] => lee [69] => eaa [70] => eap [71] => eal [72] => eae [73] => epa [74] => epp [75] => epl [76] => epe [77] => ela [78] => elp [79] => ell [80] => ele [81] => eea [82] => eep [83] => eel [84] => eee [85]

The world apple contains 1 A, 1 L, and 1 E, yet it includes results like "aa", "ll", "ee", "aaa", "lll", "eee". I do not want these included in my results.

Another issue I am having is I only need 1 instance of a combination of letters (regardless of order) for a specific size. So for instance: when it generates 3 letter combinations I only need "ple" and not "pel", "lpe", "lep", "epl" or "elp", the same for 4 letters, 5, etc.

I am not sure if I am even approaching this correctly or if I am even explaining what I mean properly.

Any help is greatly appreciated.

Answer

What you are looking for IMO is a power set:

$ cat a.php
<?php
$result = array_values(array_unique(str_split('apples')));

function getPowerSet($str_array) {
    $set_size = count($str_array);
    $pow_set_size = pow(2, $set_size);
    $return = array();
    for($counter = 0; $counter < $pow_set_size; $counter++) {
      $tmp_str = "";
      for($j = 0; $j < $set_size; $j++) {
          if($counter & (1 << $j)) {
              $tmp_str .= "$str_array[$j]";
          }
      }
      $return[] = $tmp_str;
    }
   return $return;
}
print_r(getPowerSet($result));
?>
$ php a.php
Array
(
    [0] =>
    [1] => a
    [2] => p
    [3] => ap
    [4] => l
    [5] => al
    [6] => pl
    [7] => apl
    [8] => e
    [9] => ae
    [10] => pe
    [11] => ape
    [12] => le
    [13] => ale
    [14] => ple
    [15] => aple
    [16] => s
    [17] => as
    [18] => ps
    [19] => aps
    [20] => ls
    [21] => als
    [22] => pls
    [23] => apls
    [24] => es
    [25] => aes
    [26] => pes
    [27] => apes
    [28] => les
    [29] => ales
    [30] => ples
    [31] => aples
)

If you do want letters to repeat, for examples 2 'p's in apples, then make a small change:

$result = str_split('apples');

Then the result would be:

$ php index.php
Array
(
    [0] => 
    [1] => a
    [2] => p
    [3] => ap
    [4] => p
    [5] => ap
    [6] => pp
    [7] => app
    [8] => l
    [9] => al
    [10] => pl
    [11] => apl
    [12] => pl
    [13] => apl
    [14] => ppl
    [15] => appl
    [16] => e
    [17] => ae
    [18] => pe
    [19] => ape
    [20] => pe
    [21] => ape
    [22] => ppe
    [23] => appe
    [24] => le
    [25] => ale
    [26] => ple
    [27] => aple
    [28] => ple
    [29] => aple
    [30] => pple
    [31] => apple
    [32] => s
    [33] => as
    [34] => ps
    [35] => aps
    [36] => ps
    [37] => aps
    [38] => pps
    [39] => apps
    [40] => ls
    [41] => als
    [42] => pls
    [43] => apls
    [44] => pls
    [45] => apls
    [46] => ppls
    [47] => appls
    [48] => es
    [49] => aes
    [50] => pes
    [51] => apes
    [52] => pes
    [53] => apes
    [54] => ppes
    [55] => appes
    [56] => les
    [57] => ales
    [58] => ples
    [59] => aples
    [60] => ples
    [61] => aples
    [62] => pples
    [63] => apples
)

Read more about the algorithm here: http://www.geeksforgeeks.org/power-set/