1

php: Given a list of non repetitive strings, like

  $strings=array("asd","qwerty","123");// or more 

I'd like to get all non repetitive combinations (no matter the order) like

  asd       
  asd   qwerty  
  asd   123 
  asd   qwerty  123
  qwerty        
  qwerty    123 
  123       

I'm looking for the most efficient algorithm possible and in a single function

5
  • will the list always be an array or will there be individual variables? Oct 27, 2016 at 21:22
  • the list always will be an array like array("str1","str2","str3","str4","str5",...)
    – Miky
    Oct 27, 2016 at 21:42
  • Just to clarify - when you say non repetitive ... no matter the order, do you mean that the same values in a different order would be a repetition - so skip? Oct 27, 2016 at 21:47
  • exacty, but I'd prefer to not simply "skip" them, but to not cycle them ("avoid")
    – Miky
    Oct 27, 2016 at 22:01
  • Miky, what have you tried so far? Oct 27, 2016 at 22:56

2 Answers 2

0

The main idea is that number of combinations (if all strings are different) is n^2 - 1, where n = count of strings. Thus we can use binary representation of i-th combination to build our unique combination.

In code it looks like this:

$someArray = ['abc', 'def', 'foo', 'bar'];
$combinations = pow(2, count($someArray)) - 1;

$result = [];

for ($i = 0; $i < $combinations; $i++) {

    $result[$i] = [];

    for ($j = 0; $j < count($someArray); $j++) {
       // here we check if j-th bit of i is equal to 1
       if (($i >> $j) & 1 == 1) {
           $result[$i][] = $someArray[$j];
       }
    }
}
2
  • near the perfection! It only has a "" value more, and not the "all strings" value
    – Miky
    Oct 27, 2016 at 22:37
  • well I did a mistake. Could be easily fixed by for ($i = 1; $i <= $combinations; $i++)
    – lamik
    Oct 27, 2016 at 22:46
0

Not attempting for fastest but in terms of just a solution to start with, give this a try:

$strings=array("asd","qwerty","123");// or more 
$sortstrings=natsort(array_unique($strings)); // sort and remove duplicates 
$new_arr=array();
foreach ($strings as $str)
{
   foreach($new_arr as $new)
   {
      $newstr="$new$str";
      if (!in_array("$newstr",$new_arr))
         $new_arr[]="$newstr";
   }   
   if (!in_array("$str",$new_arr))
      $new_arr[]="$str";
}
1
  • I think you forgot ! in if statement, but anyway I get only "asd,qwerty,123"
    – Miky
    Oct 27, 2016 at 22:22

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.