1

I need to find out what is the best algorithm to generate a list of all combinations of an array in php.

I want all possible combinations of elements in the original Array. The duplicate question wants only permutations. The difference is that I want to include, for example, "22", while "22" is not in an element in the Array of permutations of this array.

Here is an example :

Input : 1, 2, 3

Then the output will be

Output : 1, 2, 3, 11, 12, 13, 21, 22, 23, 31, 32, 33, 111, 112, 113, 121, 123 ... until 333.

This question is different from Finding the subsets of an array in PHP, because this question wants all combinations of the array up to a certain length, not all permutations of the array up to a certain length. In particular, the linked question will for example never return "11" or "332" while this question wants to get these values as output as well.

Community
  • 1
  • 1
Aldry Wijaya
  • 425
  • 2
  • 4
  • 13
  • so, you want to list all power sets of an array? – Filip Haglund Jul 27 '14 at 12:54
  • yeah something like that. I need all any list of combined string from input until all of the string is already used. – Aldry Wijaya Jul 27 '14 at 12:55
  • Recursion is your friend. – Abhishek Bansal Jul 27 '14 at 13:16
  • tell me how. I already try recursive way, but still stuck. – Aldry Wijaya Jul 27 '14 at 13:19
  • 2
    To those who marked this question as duplicate - **it is not**. If you take the data set the OP has and pass it through the function in the duplicate question, you will NOT get the result the OP wants. Please do not jump the gun and close valid good questions just because its title/content might seem identical... – raidenace Jul 27 '14 at 13:27
  • The so-called "duplicate" question does not take any element twice. Here this is allowed. Damn! was almost finished with the code. – Abhishek Bansal Jul 27 '14 at 13:29
  • for the one who mark this question as duplicate,, he is really idiot – Aldry Wijaya Jul 27 '14 at 13:36
  • http://ideone.com/Zgcfcc. It is a psuedo code but you should get an idea. – Abhishek Bansal Jul 27 '14 at 13:40
  • 1
    @AldryWijaya - whooo, you need to chill dude. There is no need for any name calling. I am sure those who marked this as duplicate are neither idiots nor did they have any bad intentions. – raidenace Jul 27 '14 at 13:41
  • @user1990169 : I already try with that code, but seems very unclean and didnt effective. But thanks to try give me a help. – Aldry Wijaya Jul 27 '14 at 13:48
  • 1
    OP wants all possible combinations of elements in the original Array. The duplicate question wants only permutations. The difference is that OP wants to include, for example, "22", while "22" is not in an element in the Array of permutations of this array. – Sumurai8 Jul 27 '14 at 14:02

1 Answers1

2

This problem can be solved by writing a recursive function, where you make an array with combinations up to a certain length based on the array of combinations of a shorter length. There is a special case for the length of 1. In that case, the array of combinations is the same as the original array. For all other lengths we calculate the combination array for strings up to 1 less than the current length, and add all the combinations of the current length.

function combi( $arr, $length ) {
  if( $length == 1 ) {
    return $arr;
  } else {
    $shorter = combi( $arr, $length - 1 );

    $new = Array();
    foreach( $shorter as $prefix ) {
      if( strlen( $prefix ) == $length - 1 ) {
        foreach( $arr as $suffix ) {
          $new[] = $prefix . $suffix;
        }
      }
    }

    return array_merge( $shorter, $new );
  }
}

$a = Array( "1", "2", "3" );

var_dump( combi( $a, count( $a ) ) );

This might not be the fastest approach, since you will be looping through an ever growing list, while most of the elements become irrelevant for generating the new strings. Besides that, if your input is anything else than an array of strings, you end up with a mixed array of strings and whatever the type of element is that you started of with.

This ideone shows this code working.

Sumurai8
  • 20,333
  • 11
  • 66
  • 100