<?php

/* how can you get all the combinations of given string.

 */

print_r(get_string_combinations("cat bat bad"));

function get_string_combinations($strng) {
    $words = explode(' ',$strng);
    $elements = pow(2, count($words))-1;

    $result = array();

    for ($i = 1; $i<=$elements; $i++){
        $bin = decbin($i);
        $padded_bin = str_pad($bin, count($words), "0", STR_PAD_LEFT);

        $res = array();
        for ($k=0; $k<count($words); $k++){
            //append element, if binary position says "1";
            if ($padded_bin[$k]==1){
                $res[] = $words[$k];
            }
        }

        sort($res);
        $result[] = implode("_", $res);
    }
    sort($result);
    return $result;
}
?>