duandushang5148
2017-06-12 08:42 阅读 31
已采纳

在PHP中生成独特的组合

I have a requirement to generate unique combinations from the given data set (n numbers) with each combination contains r values.

Basically looking to implement C(n,r)=n!(r!(n−r)!) formula in PHP.

Input data set {A,B,C,D} and need an unique combination of 3 values like below:

C(n,r)=C(4,3) = 4!/(3!(4−3)!)
= 4

ABC ACD BCD BDA

(CDA,CAB,BCA etc are duplicates and should be truncated from output).

But my code below

<?php
function sampling($chars, $size, $combinations = array()) {

    # if it's the first iteration, the first set 
    # of combinations is the same as the set of characters
    if (empty($combinations)) {
        $combinations = $chars;
    }

    # we're done if we're at size 1
    if ($size == 1) {
        return $combinations;
    }

    # initialise array to put new values in
    $new_combinations = array();

    # loop through existing combinations and character set to create strings
    foreach ($combinations as $combination) {
        foreach ($chars as $char) {
            if($combination != $char)
            $new_combinations[] = $combination . $char;
        }
    }

    # call same function again for the next iteration
    return sampling($chars, $size - 1, $new_combinations);

}
?>

returns below 64 arrays with duplicates

{ [0]=> string(3) "aaa" [1]=> string(3) "aab" [2]=> string(3) "aac" [3]=> string(3) "aad" [4]=> string(3) "aba" [5]=> string(3) "abb" [6]=> string(3) "abc" [7]=> string(3) "abd" [8]=> string(3) "aca" [9]=> string(3) "acb" [10]=> string(3) "acc" [11]=> string(3) "acd" [12]=> string(3) "ada" [13]=> string(3) "adb" [14]=> string(3) "adc" [15]=> string(3) "add" [16]=> string(3) "baa" [17]=> string(3) "bab" [18]=> string(3) "bac" [19]=> string(3) "bad" [20]=> string(3) "bba" [21]=> string(3) "bbb" [22]=> string(3) "bbc" [23]=> string(3) "bbd" [24]=> string(3) "bca" [25]=> string(3) "bcb" [26]=> string(3) "bcc" [27]=> string(3) "bcd" [28]=> string(3) "bda" [29]=> string(3) "bdb" [30]=> string(3) "bdc" [31]=> string(3) "bdd" [32]=> string(3) "caa" [33]=> string(3) "cab" [34]=> string(3) "cac" [35]=> string(3) "cad" [36]=> string(3) "cba" [37]=> string(3) "cbb" [38]=> string(3) "cbc" [39]=> string(3) "cbd" [40]=> string(3) "cca" [41]=> string(3) "ccb" [42]=> string(3) "ccc" [43]=> string(3) "ccd" [44]=> string(3) "cda" [45]=> string(3) "cdb" [46]=> string(3) "cdc" [47]=> string(3) "cdd" [48]=> string(3) "daa" [49]=> string(3) "dab" [50]=> string(3) "dac" [51]=> string(3) "dad" [52]=> string(3) "dba" [53]=> string(3) "dbb" [54]=> string(3) "dbc" [55]=> string(3) "dbd" [56]=> string(3) "dca" [57]=> string(3) "dcb" [58]=> string(3) "dcc" [59]=> string(3) "dcd" [60]=> string(3) "dda" [61]=> string(3) "ddb" [62]=> string(3) "ddc" [63]=> string(3) "ddd" }

Thanks in advance !!!

  • 点赞
  • 写回答
  • 关注问题
  • 收藏
  • 复制链接分享

1条回答 默认 最新

  • 已采纳
    douzhuo8871 douzhuo8871 2017-06-12 08:59

    Say you have a set of 4 items and you want a random subset of 3 of them. You can do the following:

    $myset = [ "A","B","C", "D" ];    
    
    function randomSubset($set, $size) {
        $array = array_pad(array_pad([],$size,1),count($set),0); //Get an array like [ 1,1,1,0 ];
        shuffle($array);
        return array_intersect_key($set, array_filter($array));
     }
    
     print_r(randomSubset($myset,3));
    

    See it at a sandbox: http://sandbox.onlinephpfunctions.com/code/a68f3b2f1abc285424ccadbaab8a12fc4928bb8d

    Now if you need all subsets of size N you can do some recursive magic:

    function allSubsets($set, $size) {     
        $subsets = [];
        if ($size == 1) {
            return array_map(function ($v) { return [$v]; },$set);
        }
        foreach (allSubsets($set,$size-1) as $subset) {
            foreach ($set as $element) {
                if (!in_array($element,$subset)) {
                    $newSet = array_merge($subset,[$element]);
                    sort($newSet);
                    if (!in_array($newSet,$subsets)) {
                        $subsets[] = array_merge($subset,[$element]);
                    }
                }
            }
        }
        return $subsets;
    
    }
    
     $myset = [ "A","B","C", "D", "E" ];   
     print_r(allSubsets($myset,3));
    

    Sandboxed: http://sandbox.onlinephpfunctions.com/code/01b55f0c1eb55ee82a67175d2551c164ffb2bf87

    点赞 评论 复制链接分享

相关推荐